Maximum Number of Balls in a Box - Solution & Explanation
Problem Statement
You are working in a ball factory where you have n balls numbered from lowLimit up to highLimit inclusive (i.e., n == highLimit - lowLimit + 1), and an infinite number of boxes numbered from 1 to infinity.
Your job at this factory is to put each ball in the box with a number equal to the sum of digits of the ball's number. For example, the ball number 321 will be put in the box number 3 + 2 + 1 = 6 and the ball number 10 will be put in the box number 1 + 0 = 1.
Given two integers lowLimit and highLimit, return the number of balls in the box with the most balls.
Example 1:
Input: lowLimit = 1, highLimit = 10 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 ... Ball Count: 2 1 1 1 1 1 1 1 1 0 0 ... Box 1 has the most number of balls with 2 balls.
Example 2:
Input: lowLimit = 5, highLimit = 15 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 ... Ball Count: 1 1 1 1 2 2 1 1 1 0 0 ... Boxes 5 and 6 have the most number of balls with 2 balls in each.
Example 3:
Input: lowLimit = 19, highLimit = 28 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 12 ... Ball Count: 0 1 1 1 1 1 1 1 1 2 0 0 ... Box 10 has the most number of balls with 2 balls.
Constraints:
1 <= lowLimit <= highLimit <= 105
Approach Overview
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.
Approach 1: Counting with Frequency Map
In this approach, we'll use a hashmap (or dictionary) to count balls in boxes. The key for the hashmap will be the sum of digits (box number), and the value will be the count of balls in that box. We will iterate from `lowLimit` to `highLimit`, calculate the sum of digits for each number, and increment the count for the corresponding box in our hashmap. Finally, we'll find the maximum count in the hashmap, which gives us our answer.
The function countBalls computes the number of balls in the fullest box. It uses a helper function sum_of_digits to calculate the sum of digits of a ball number. A dictionary box_count is used to maintain the count of balls in each box. By iterating over each ball number from lowLimit to highLimit, we calculate the box number, increment its count, and finally return the maximum value in the dictionary, which represents the fullest box.
Complexity
Time Complexity: O(n * d), where n is the number of balls (highLimit - lowLimit + 1) and d is the number of digits in the largest ball number.
Space Complexity: O(k), where k is the number of different box numbers used (typically constrained by the maximum digit sum).
Approach 2: Optimized Counting with Array
In this approach, knowing the constraints, we recognize that the possible sum of digits cannot exceed 45 for this input range (100,000). Therefore, we can use a fixed size array (length 46) opposed to a hashmap for easier and faster access and modification. This method allows us to avoid dictionary lookups and reduce overhead.
In this simpler array-based Python solution, the function sum_of_digits leverages string conversion for brevity. It maintains an array box_count of length 46, iterating over each number, calculating the box number, and incrementing the respective index in the array. Finally, it returns the maximum value found in the array.
Complexity
Time Complexity: O(n * d), where n is the number of balls, and d is the digits per ball.
Space Complexity: O(1), with the fixed-size array only needing constant space.
Approach 3: Array + Simulation
Observing the problem's data range, the maximum number of balls does not exceed 10^5, so the maximum sum of the digits of each number is less than 50. Therefore, we can directly create an array cnt of length 50 to count the number of occurrences of each digit sum.
The answer is the maximum value in the array cnt.
The time complexity is O(n times log_{10}m). Here, n = highLimit - lowLimit + 1, and m = highLimit.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Counting with Frequency Map | Time Complexity: O(n * d), where n is the number of balls (highLimit - lowLimit + 1) and d is the number of digits in the largest ball number. |
| Optimized Counting with Array | Time Complexity: O(n * d), where n is the number of balls, and d is the digits per ball. |
| Array + Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting with Frequency Map | O(n * d) | O(k) | General solution when the range of keys is unknown or large |
| Optimized Counting with Array | O(n * d) | O(1) | Best choice when digit sum range is small and predictable |
Video Solution
1742. Maximum Number of Balls in a Box (Leetcode Easy) • Programming Live with Larry • 1,586 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Number of Balls in a Box easy or hard?
Maximum Number of Balls in a Box Python/Java solution
How to solve Maximum Number of Balls in a Box in O(n)?
What is the best approach for Maximum Number of Balls in a Box?
Is Maximum Number of Balls in a Box asked at Google/Amazon/Meta?
What data structure is used in Maximum Number of Balls in a Box?
What is the time complexity of Maximum Number of Balls in a Box?
Ready to solve this problem?
Practice Maximum Number of Balls in a Box with our built-in code editor and test cases.
Practice on FleetCode