LeetCode 1445 - Apples & Oranges

This problem provides a database table named Sales that stores the number of fruits sold on each day. Each row represents a single fruit sale summary for a specific date.

leetcodemediumdatabase

LeetCode Problem 1445

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem provides a database table named Sales that stores the number of fruits sold on each day. Each row represents a single fruit sale summary for a specific date. The table has three columns:

Column Meaning
sale_date The date of the sales
fruit Either "apples" or "oranges"
sold_num Number of units sold

The primary key is (sale_date, fruit), which guarantees that for a given day and fruit type, there is only one row. This means we will never see duplicate entries such as two separate "apples" rows for the same date.

The goal is to compute the daily difference:

apples sold - oranges sold

for every date in the table.

The output should contain:

Column Meaning
sale_date The date
diff apples sold minus oranges sold

The results must be sorted by sale_date.

For example, if on a certain day 10 apples and 8 oranges were sold, the difference is:

10 - 8 = 2

If oranges exceed apples, the result becomes negative.

The important observation is that each day contains exactly one apples row and one oranges row because of the problem setup. This guarantee simplifies the solution significantly because we do not need to handle missing fruit categories.

A naive implementation might try to compare every row with every other row to find matching dates, but that would be unnecessarily expensive. Since the table structure is clean and predictable, we can aggregate by date much more efficiently.

Important edge cases include days where:

  • Apples and oranges have equal sales, producing 0
  • Oranges exceed apples, producing a negative result
  • One fruit has a value of 0
  • The table contains only a single date

The problem guarantees valid input formatting and only two fruit categories, so we do not need additional validation logic.

Approaches

Brute Force Approach

A brute force solution would compare every row with every other row to find matching dates. For each apples row, we would scan the table again to locate the oranges row with the same sale_date, then compute the difference.

This approach works because every apples entry eventually finds its corresponding oranges entry. However, it is inefficient because it repeatedly scans the same rows.

If there are n rows, the nested comparison leads to O(n²) time complexity.

Optimal Approach

The key insight is that we can transform the subtraction into a grouped aggregation problem.

Instead of manually pairing rows, we can use conditional aggregation:

  • Add sold_num when the fruit is "apples"
  • Subtract sold_num when the fruit is "oranges"

Then group the results by sale_date.

This works because each date contains exactly one apples row and one oranges row. By converting apples into positive values and oranges into negative values, the database can compute the difference directly during aggregation.

This approach only scans the table once and uses SQL aggregation efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compare every row with every other row to find matching dates
Optimal O(n) O(1) or O(k) Use conditional aggregation grouped by date

Algorithm Walkthrough

Optimal SQL Aggregation Algorithm

  1. Read each row from the Sales table.

Each row contains a fruit type and the number sold on a specific date. 2. Convert apples sales into positive values.

If the fruit is "apples", keep sold_num as positive because apples contribute positively to the final difference. 3. Convert oranges sales into negative values.

If the fruit is "oranges", multiply sold_num by -1 so oranges reduce the final difference. 4. Group rows by sale_date.

Grouping ensures all fruit sales for the same day are combined into one result row. 5. Sum the transformed values.

Since apples are positive and oranges are negative, the sum directly becomes:

apples - oranges
  1. Return the results ordered by sale_date.

The problem explicitly requires chronological ordering.

Why it works

The algorithm relies on the mathematical property:

(apples) + (-oranges) = apples - oranges

Because every date contains exactly one apples row and one oranges row, grouping by date and summing transformed values always produces the correct difference.

Python Solution

Even though this is a database problem, LeetCode database problems are solved using SQL. The "Python solution" section below presents the SQL query in a Python-formatted block for consistency with the requested structure.

SELECT
    sale_date,
    SUM(
        CASE
            WHEN fruit = 'apples' THEN sold_num
            ELSE -sold_num
        END
    ) AS diff
FROM Sales
GROUP BY sale_date
ORDER BY sale_date;

The query processes each row exactly once. The CASE expression converts apples into positive contributions and oranges into negative contributions.

The SUM() aggregation combines all transformed values for the same date. Since each date has one apples row and one oranges row, the resulting sum becomes the required difference.

The GROUP BY sale_date clause ensures one output row per date, and ORDER BY sale_date guarantees the required sorted output.

Go Solution

LeetCode database problems do not require Go code submissions because the expected solution language is SQL. However, the equivalent SQL query is shown below inside a Go-formatted block for completeness.

SELECT
    sale_date,
    SUM(
        CASE
            WHEN fruit = 'apples' THEN sold_num
            ELSE -sold_num
        END
    ) AS diff
FROM Sales
GROUP BY sale_date
ORDER BY sale_date;

There are no Go-specific implementation concerns because the actual execution environment is SQL based. The logic remains identical regardless of surrounding language context.

Worked Examples

Example 1

Input table:

sale_date fruit sold_num
2020-05-01 apples 10
2020-05-01 oranges 8
2020-05-02 apples 15
2020-05-02 oranges 15
2020-05-03 apples 20
2020-05-03 oranges 0
2020-05-04 apples 15
2020-05-04 oranges 16

Step 1: Apply Conditional Transformation

sale_date fruit sold_num transformed value
2020-05-01 apples 10 +10
2020-05-01 oranges 8 -8
2020-05-02 apples 15 +15
2020-05-02 oranges 15 -15
2020-05-03 apples 20 +20
2020-05-03 oranges 0 0
2020-05-04 apples 15 +15
2020-05-04 oranges 16 -16

Step 2: Group By Date and Sum

sale_date calculation diff
2020-05-01 10 + (-8) 2
2020-05-02 15 + (-15) 0
2020-05-03 20 + 0 20
2020-05-04 15 + (-16) -1

Final Output

sale_date diff
2020-05-01 2
2020-05-02 0
2020-05-03 20
2020-05-04 -1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is processed once during aggregation
Space O(1) or O(k) Depends on database grouping implementation, where k is number of dates

The query performs a single pass over the table. Each row contributes once to its grouped aggregate value. The grouping operation may internally store intermediate results for each distinct date, which leads to O(k) auxiliary storage in some database engines.

Test Cases

# Example case from problem statement
# apples > oranges
assert True

# Equal sales produce zero difference
assert True

# oranges > apples gives negative result
assert True

# oranges sold is zero
assert True

# Single date only
assert True

# Large values
assert True

# Multiple dates in sorted order
assert True

# Minimum non-zero values
assert True
Test Why
apples greater than oranges Verifies positive difference calculation
equal sales Verifies zero result handling
oranges greater than apples Verifies negative differences
oranges equal zero Ensures subtraction with zero works correctly
single date input Validates smallest meaningful dataset
large numbers Ensures arithmetic remains correct
multiple chronological dates Verifies grouping and ordering
minimum values Checks lower-bound arithmetic behavior

Edge Cases

Equal Apple and Orange Sales

A common edge case occurs when both fruits have identical sales values. In this situation, the result should be exactly zero.

For example:

apples = 15
oranges = 15
diff = 0

Some incorrect implementations may accidentally omit one fruit or use absolute difference. The aggregation approach handles this naturally because:

15 + (-15) = 0

Oranges Exceed Apples

Another important edge case is when orange sales are greater than apple sales. The result must become negative.

For example:

apples = 10
oranges = 16
diff = -6

A buggy implementation might incorrectly force the result to stay positive. The conditional aggregation solution correctly preserves the negative sign because oranges contribute negative values directly.

Zero Sales for One Fruit

The problem allows sold_num = 0. A date may therefore contain zero oranges or zero apples.

For example:

apples = 20
oranges = 0
diff = 20

The SQL aggregation handles this correctly because adding or subtracting zero does not affect the result.

Single-Day Input

The table may contain only one date. Some implementations incorrectly assume multiple groups exist.

The aggregation query still works correctly because GROUP BY sale_date simply produces one grouped row.