Domain 2MediumMEDIUM

Apples & Oranges

Count valid fruits from two lists based on a weight threshold using generator expressions for optimal space complexity.

Domain: medium•Updated: 2026-09-16
#filtering#list#O(N)#O(1)

Problem Breakdown

The objective is to simulate an SQL aggregation query in Python. We are given two datasets (apples and oranges) representing rows from tables, each containing a numerical attribute (weight). The task requires filtering these records based on a condition (e.g., weight > threshold) and calculating the total count of valid items across both sets. This mimics executing SELECT COUNT(*) FROM ... WHERE column >= value.

Intuition

The problem is fundamentally about set-based aggregation rather than row-by-row iteration in an inefficient manner. In SQL, this would be handled by a single pass over unioned tables with a filter clause. In Python, we replicate this using generator expressions within sum(), which evaluate conditions lazily without constructing intermediate lists of filtered data. This approach ensures that the time complexity remains linear relative to input size (O(N+M)O(N+M)) while maintaining constant auxiliary space usage for processing logic.

Approach

  1. Define Inputs: Create a function accepting two integer lists (apples, oranges) and an optional threshold value (defaulting to 10).
  2. Filter Logic: For each list, iterate through elements using a generator expression that checks the weight condition immediately during iteration.
  3. Handle Nulls: Include a check for None values within the generator to handle potential SQL-derived NULL data gracefully without raising errors or crashing on empty/null inputs.
  4. Aggregate Counts: Sum the boolean results (True=1, False=0) from both generators and return their combined total as an integer.

Complexity Analysis

  • Time Complexity: O(N+M)O(N + M) where NN is the number of apples and MM is the number of oranges. We traverse each list exactly once to evaluate the condition for every element. This is optimal because we must inspect every item at least once to determine validity.
  • Space Complexity: O(1)O(1) auxiliary space if generator expressions are used, as they do not store intermediate lists in memory (unlike filter() or list comprehensions). The input storage itself takes O(N+M)O(N+M) but is considered external data provided by the caller.

Solution

from typing import List

def count_fruits(apples: List[int], oranges: List[int], threshold: int = 10) -> int:
    """
    Counts the total number of apples and oranges that meet a weight threshold.
    
    Args:
        apples (List[int]): Weights of available apples.
        oranges (List[int]): Weights of available oranges.
        threshold (int): Minimum weight required for fruit to be counted. Defaults to 10.

    Returns:
        int: Total count of valid fruits combined from both lists.
    """
    
    # Use generator expressions inside sum() to avoid creating intermediate lists, 
    # keeping space complexity O(1) auxiliary (excluding input storage).
    # The 'if weight is not None' check handles potential SQL NULL values robustly.
    valid_apples_count = sum(weight > threshold for weight in apples if weight is not None)
    valid_oranges_count = sum(weight > threshold for weight in oranges if weight is not None)

    return valid_apples_count + valid_oranges_count

Edge Cases Handled

  • Empty Lists: If apples or oranges are empty, the generator yields no values. The sum() function returns 0 immediately for that category, resulting in a correct total count based on available data.
  • No Valid Items: If all weights fall below the threshold, every boolean check evaluates to False (0), and sum() correctly returns 0 without iterating unnecessarily beyond necessary checks.
  • Null/None Values: The explicit check (if weight is not None) prevents potential runtime errors if input data contains nulls common in SQL contexts or loose typing scenarios, ensuring the function remains robust against dirty data inputs.