Maximum Number of Balls in a Box - Video Solutions

Problem Overview: You are given a range of ball numbers from lowLimit to highLimit. Each ball goes into a box identified by the sum of its digits. For example, ball 321 goes to box 3 + 2 + 1 = 6. After placing every ball, the task is to return the maximum number of balls in any single box.

The key observation: the box number is simply the digit sum of the ball number. So the problem reduces to counting how many times each digit sum appears while iterating through the range.

Approach 1: Counting with Frequency Map (Time: O(n * d), Space: O(k))

Iterate from lowLimit to highLimit. For each number, compute its digit sum by repeatedly extracting digits with num % 10 and dividing by 10. Store the count of each box using a hash map where the key is the digit sum and the value is the number of balls in that box. After processing every number, return the maximum value in the map. This approach uses a hash table for flexible counting and works well when the possible digit sums are not tightly bounded.

The runtime is O(n * d), where n is the number of balls and d is the number of digits per number (at most 5 for this problem). Space complexity is O(k), where k is the number of unique digit sums.

Approach 2: Optimized Counting with Array (Time: O(n * d), Space: O(1))

Digit sums have a small upper bound. For example, the maximum possible sum for a five-digit number is 9 + 9 + 9 + 9 + 9 = 45. Instead of a hash map, use a fixed-size array where the index represents the digit sum and the value stores the ball count. Iterate through the range, compute the digit sum, and increment the corresponding index.

This converts the frequency structure from a dynamic map to a simple array lookup, which is faster in practice due to constant-time indexing and lower overhead. The algorithm still performs digit extraction using simple math operations and uses a counting technique to track frequencies.

The time complexity remains O(n * d), but space becomes effectively O(1) because the array size is constant (around 46 possible sums).

Recommended for interviews: The array-based counting solution is what interviewers typically expect. It shows you recognized that the digit sum range is small and replaced the hash map with a constant-size frequency array. Starting with the map approach demonstrates correct reasoning, while the optimized array version shows you can reduce overhead by analyzing constraints.