LeetCode 1715 - Count Apples and Oranges

LeetCode Problem 1715

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to compute the total number of apples and oranges across all boxes, taking into account that some boxes may contain a chest. The Boxes table gives us the count of apples and oranges in each box, and optionally the chest_id if a chest is present in that box. The Chests table gives the count of apples and oranges contained in each chest.

The output is a single row with two columns: apple_count and orange_count, representing the sum of all apples and oranges in every box, including the contents of chests when present.

Key points to note are that not every box contains a chest (chest_id can be null) and not every chest may be used (chest_id in the Chests table may not appear in Boxes). We also need to sum correctly even when multiple boxes refer to the same chest.

Edge cases include boxes with no chest, boxes with chest_id pointing to a chest, and boxes whose chest_id might not exist (though problem constraints likely ensure referential integrity). The problem guarantees that box_id and chest_id are unique identifiers for their respective tables.

Approaches

The brute-force approach would be to iterate through all boxes, and for each box that contains a chest, perform a nested search on the Chests table to retrieve the corresponding counts. This approach is correct but inefficient because it could result in an O(n*m) time complexity where n is the number of boxes and m is the number of chests.

The optimal approach leverages a SQL LEFT JOIN between Boxes and Chests on chest_id. By doing this join, we can directly add the apples and oranges from the chest to the corresponding box in one pass. Using SQL aggregate functions (SUM) ensures the total is computed efficiently in O(n) time relative to the number of rows in the Boxes table.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n*m)	O(1)	Nested lookup of chest for each box, slow for large datasets
Optimal	O(n)	O(1)	Use SQL LEFT JOIN to sum box and chest contents directly

Algorithm Walkthrough

1. Perform a LEFT JOIN of Boxes to Chests on chest_id. This ensures every box appears in the result even if it does not have a chest.
2. In the joined result, for each row, compute the total apples as box.apple_count + IFNULL(chest.apple_count, 0) and total oranges as box.orange_count + IFNULL(chest.orange_count, 0). This handles boxes without chests correctly by treating null as zero.
3. Use SQL SUM() on these computed totals to get the final total apples and oranges.
4. Return the result as a single row with columns apple_count and orange_count.

Why it works: By joining boxes to their respective chests and summing, each box contributes its own apples and oranges, and if a chest is present, its contents are included. The LEFT JOIN guarantees that boxes without a chest are still counted.

Python Solution

import sqlite3
from typing import Tuple

def countApplesAndOranges(conn: sqlite3.Connection) -> Tuple[int, int]:
    cursor = conn.cursor()
    query = """
    SELECT
        SUM(b.apple_count + IFNULL(c.apple_count, 0)) AS apple_count,
        SUM(b.orange_count + IFNULL(c.orange_count, 0)) AS orange_count
    FROM Boxes b
    LEFT JOIN Chests c
    ON b.chest_id = c.chest_id
    """
    cursor.execute(query)
    result = cursor.fetchone()
    return result[0], result[1]

The Python solution executes the SQL query on the provided database connection. The LEFT JOIN ensures every box is included, and IFNULL handles the absence of a chest by using zero. The SUM aggregates the total counts for all boxes including the chest contents.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
)

func countApplesAndOranges(db *sql.DB) (int, int, error) {
    query := `
    SELECT
        SUM(b.apple_count + IFNULL(c.apple_count, 0)) AS apple_count,
        SUM(b.orange_count + IFNULL(c.orange_count, 0)) AS orange_count
    FROM Boxes b
    LEFT JOIN Chests c
    ON b.chest_id = c.chest_id
    `
    row := db.QueryRow(query)
    var appleCount, orangeCount int
    err := row.Scan(&appleCount, &orangeCount)
    if err != nil {
        return 0, 0, err
    }
    return appleCount, orangeCount, nil
}

In Go, the query logic is the same as in Python. We use QueryRow and Scan to extract the single row of results. Error handling is important in Go to catch any issues executing the query.

Worked Examples

Using the problem's example:

box_id	chest_id	box_apples	box_oranges	chest_apples	chest_oranges	total_apples	total_oranges
2	null	6	15	0	0	6	15
18	14	4	15	20	10	24	25
19	3	8	4	19	4	27	8
12	2	19	20	8	8	27	28
20	6	12	9	5	6	17	15
8	6	9	9	5	6	14	15
3	14	16	7	20	10	36	17

Final totals: 151 apples, 123 oranges.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each box is processed once, join and sum are O(n) in SQL
Space	O(1)	Aggregation does not require storing individual rows in memory

The SQL engine efficiently handles joins and aggregation internally, so our algorithm scales linearly with the number of boxes.

Test Cases

# test cases
assert countApplesAndOranges(conn) == (151, 123)  # Provided example
# Edge case: no boxes
assert countApplesAndOranges(empty_conn) == (0, 0)
# Edge case: boxes without chests
assert countApplesAndOranges(boxes_no_chests_conn) == (sum_apples, sum_oranges)
# Edge case: boxes all reference the same chest
assert countApplesAndOranges(boxes_same_chest_conn) == (sum_apples, sum_oranges)

Test	Why
Provided example	Verifies correctness on typical input with mixed boxes and chests
No boxes	Verifies that empty tables return zero
Boxes without chests	Ensures boxes without chests are counted correctly
Boxes referencing same chest	Checks repeated chest aggregation is handled correctly

Edge Cases

One important edge case is when Boxes has no rows. The algorithm correctly handles this because SQL SUM on an empty table returns NULL, which is interpreted as zero when fetching results.

Another edge case is boxes that do not have a chest (chest_id is null). The LEFT JOIN ensures these rows are included, and IFNULL guarantees that null chest values contribute zero to the sum.

A third edge case is multiple boxes referencing the same chest. Our implementation correctly sums the chest contents for each box that references it, as the SQL join duplicates the chest row for each referencing box, ensuring all counts are included.