LeetCode 1742 - Maximum Number of Balls in a Box

LeetCode Problem 1742

Difficulty: 🟢 Easy
Topics: Hash Table, Math, Counting

Solution

Problem Understanding

The problem describes a scenario in which you have a sequence of balls numbered consecutively from lowLimit to highLimit, inclusive. Each ball must be placed into a box, where the box number is determined by the sum of the digits of the ball’s number. For example, ball 321 goes into box 3 + 2 + 1 = 6. The task is to determine which box ends up containing the most balls and return the number of balls in that box.

The input consists of two integers, lowLimit and highLimit. The difference between them, plus one, gives the total number of balls. The expected output is a single integer representing the maximum number of balls found in any box after all balls have been placed.

The constraints indicate that the numbers are relatively small (1 <= lowLimit <= highLimit <= 10^5), so a brute-force solution that iterates through every ball and calculates the digit sum is feasible. The problem also guarantees that lowLimit and highLimit are positive and well-ordered, so we do not need to handle invalid ranges.

Edge cases include when lowLimit == highLimit (only one ball exists), or when all numbers fall into the same box due to low digit sums. Another subtle case is when the sums of digits increase slowly, causing some boxes to remain empty.

Approaches

The brute-force approach is straightforward: iterate through each number from lowLimit to highLimit, compute the sum of its digits, and increment a counter for that box in a hash map or array. After processing all balls, simply find the maximum count among all boxes. This approach is correct because each ball is handled independently, but computing the sum of digits for every number repeatedly may be slightly inefficient.

The key optimization arises from recognizing that the sum of digits of consecutive numbers changes predictably. When moving from x to x + 1, the sum of digits increases by 1 unless there is a carry (e.g., from 19 to 20). While this observation could allow a digit-sum “incremental update,” the constraints are small enough that the brute-force approach with a simple hash map is already efficient and easy to implement.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * d)	O(k)	n = highLimit - lowLimit + 1, d = number of digits, k = max possible box number
Optimal	O(n * d)	O(k)	Same as brute force for this input range; uses a hash map to track counts

Algorithm Walkthrough

1. Initialize a hash map (or dictionary) to store counts of balls per box. The keys represent box numbers (sum of digits) and the values represent the count of balls in each box.
2. Iterate over all numbers from lowLimit to highLimit.
3. For each number, calculate the sum of its digits. This sum is the box number.
4. Increment the count for this box in the hash map.
5. After all numbers have been processed, find the maximum value in the hash map.
6. Return this maximum value, which represents the number of balls in the box with the most balls.

Why it works: Each ball is placed into a box exactly according to the sum of its digits. Counting each placement guarantees that the box with the maximum count correctly reflects the box with the most balls.

Python Solution

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        from collections import defaultdict

        box_counts = defaultdict(int)

        for number in range(lowLimit, highLimit + 1):
            box_number = sum(int(digit) for digit in str(number))
            box_counts[box_number] += 1

        return max(box_counts.values())

In this implementation, we use a defaultdict to automatically handle boxes that have not yet been encountered. For each number, we convert it to a string and sum its digits to determine the box number, then increment the count. Finally, max returns the highest ball count.

Go Solution

func countBalls(lowLimit int, highLimit int) int {
    boxCounts := make(map[int]int)
    maxCount := 0

    for num := lowLimit; num <= highLimit; num++ {
        n := num
        sum := 0
        for n > 0 {
            sum += n % 10
            n /= 10
        }
        boxCounts[sum]++
        if boxCounts[sum] > maxCount {
            maxCount = boxCounts[sum]
        }
    }

    return maxCount
}

In Go, we use a map[int]int for counting. The digit sum is computed using modulo and division to avoid string conversion. We also maintain a running maxCount to avoid iterating over the map at the end.

Worked Examples

Example 1: lowLimit = 1, highLimit = 10

Number	Digit Sum (Box)	Count Update	Box Counts
1	1	+1	{1:1}
2	2	+1	{1:1, 2:1}
3	3	+1	{1:1,2:1,3:1}
4	4	+1	{1:1,2:1,3:1,4:1}
5	5	+1	{1:1,2:1,3:1,4:1,5:1}
6	6	+1	{1:1,...,6:1}
7	7	+1	...
8	8	+1	...
9	9	+1	...
10	1	+1	{1:2,...}

Maximum count = 2 for box 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * d)	n = highLimit - lowLimit + 1, d = number of digits per number; summing digits requires O(d)
Space	O(k)	k = maximum possible box number (digit sum), store count for each box

The solution scales linearly with the number of balls, and space scales with the number of distinct digit sums, which is at most 45 for numbers <= 99999.

Test Cases

# Basic examples
assert Solution().countBalls(1, 10) == 2  # Box 1 has 2 balls
assert Solution().countBalls(5, 15) == 2  # Boxes 5 and 6 have 2 balls
assert Solution().countBalls(19, 28) == 2  # Box 10 has 2 balls

# Edge cases
assert Solution().countBalls(1, 1) == 1  # Single ball, single box
assert Solution().countBalls(10, 10) == 1  # Single ball with sum 1
assert Solution().countBalls(1, 100000) >= 1  # Large range, ensure no crash

Test	Why
1 to 10	Simple incremental test with overlap in box 1
5 to 15	Overlapping boxes, verifying counts across ranges
19 to 28	Boxes with two-digit sums
1 to 1	Minimal input, single ball
10 to 10	Minimal input with sum > 1
1 to 100000	Stress test for large inputs

Edge Cases

First, the case where lowLimit equals highLimit tests the algorithm's ability to handle a single ball. The implementation correctly counts it in the appropriate box and returns 1.

Second, ranges where all numbers have the same digit sum could potentially stress the counting logic. The algorithm uses a hash map, so all balls accumulate correctly.

Third, very large ranges, near the upper constraint of 10^5, test performance. The algorithm remains efficient because iterating 10^5 numbers with small digit sums is computationally feasible. Additionally, Go’s integer arithmetic prevents overflow issues.