You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.
Given the integer n, return the number of complete rows of the staircase you will build.
Example 1:
Input: n = 5 Output: 2 Explanation: Because the 3rd row is incomplete, we return 2.
Example 2:
Input: n = 8 Output: 3 Explanation: Because the 4th row is incomplete, we return 3.
Constraints:
1 <= n <= 231 - 1Problem Overview: You are given n coins and must arrange them into a staircase shape where the first row has 1 coin, the second has 2, the third has 3, and so on. The task is to return the number of complete rows that can be formed before you run out of coins.
Approach 1: Greedy Iterative Solution (Time: O(sqrt(n)), Space: O(1))
The simplest idea is to simulate building the staircase row by row. Start with row size 1, subtract that from n, then move to row size 2, and continue until the remaining coins are insufficient for the next row. Each iteration represents constructing one level of the staircase. Because the total coins required for k rows is k(k+1)/2, the number of iterations grows roughly with sqrt(n), making the loop efficient even for large inputs. This approach relies on simple arithmetic and iteration, making it easy to implement and a good baseline when reasoning about math-based problems.
Approach 2: Binary Search (Time: O(log n), Space: O(1))
The number of coins needed for k rows follows the formula k(k+1)/2. The goal is to find the largest k such that this value is less than or equal to n. Instead of checking sequentially, search the answer space using binary search. Set the range between 0 and n, compute the midpoint mid, and check whether mid(mid+1)/2 exceeds n. If it does, move left; otherwise move right and keep track of the best valid value. This converts the search for the correct row count into a logarithmic-time problem.
Binary search works well because the staircase function is monotonic: if k rows require too many coins, any larger value will also fail. That property guarantees correctness while reducing the number of checks dramatically compared to iterative subtraction.
Recommended for interviews: The greedy iterative approach clearly demonstrates the staircase concept and is easy to derive during discussion. However, interviewers usually expect the binary search optimization because it recognizes the monotonic mathematical relationship and reduces the runtime to O(log n). Showing both approaches proves you understand the problem structure and can improve a straightforward solution using algorithmic insight.
This approach involves sequentially counting how many coins are required to form a complete row one row at a time. While the number of available coins is greater than or equal to coins needed for the next row, continue adding rows and reducing the count of available coins accordingly.
The solution involves a while loop that continues to subtract sequential numbers from n. Each time a subtraction is successful, the count of complete rows (k) is incremented. The loop terminates when n is less than the number of coins needed for the next row.
Time Complexity: O(√n), as the sum of the first k natural numbers grows quadratically.
Space Complexity: O(1), constant space is used.
Using a binary search, optimize the process of finding the maximum k where the sum of the first k natural numbers is less than or equal to n. Calculate mid values and determine if they result in a possible sum being less or equal to n and adjust the search space accordingly.
The C code employs long integers for intermediate calculations to avoid overflow. The binary search algorithm adjusts the search range based on whether the calculated sum of coins (for k = mid) is greater or less than n.
Time Complexity: O(log n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Iterative Solution | Time Complexity: O(√n), as the sum of the first k natural numbers grows quadratically. |
| Approach 2: Binary Search | Time Complexity: O(log n) |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Iterative Solution | O(sqrt(n)) | O(1) | Best for quickly deriving the idea by simulating rows; simple implementation and easy to reason about. |
| Binary Search | O(log n) | O(1) | Preferred when optimizing performance; leverages the monotonic property of k(k+1)/2 to locate the maximum valid row count efficiently. |
Arranging Coins - Leetcode 441 - Python • NeetCode • 48,972 views views
Watch 9 more video solutions →Practice Arranging Coins with our built-in code editor and test cases.
Practice on FleetCode