This problem asks you to find how many full rows can be formed in a staircase pattern using n coins. A direct simulation is inefficient for large n, so the optimal approach is to perform a binary search over the possible number of rows. By checking the total coins required for a candidate row count, you can quickly narrow down the correct number of complete rows and handle large values without overflow.
Problem Statement
You have a total of n coins and want to arrange them into a staircase shape. Each row i must contain exactly i coins. The staircase may have a partially completed last row.
Given an integer n, return the number of complete rows that can be formed. For example, if n = 5, the staircase rows would be [1,2,2], and the answer is 2 because the third row is incomplete.
Examples
Example 1
Input: n = 5
Output: 2
Because the 3rd row is incomplete, we return 2.
Example 2
Input: n = 8
Output: 3
Because the 4th row is incomplete, we return 3.
Constraints
- 1 <= n <= 231 - 1
Solution Approach
Mathematical Summation Check
Use the formula for the sum of the first k natural numbers, k*(k+1)/2, to check if k rows can be fully formed. Increment k until the total exceeds n. This approach directly ties to the problem's staircase pattern but is slower for very large n.
Binary Search Over Row Count
Set low = 0 and high = n, and perform binary search to find the largest k where k*(k+1)/2 <= n. Adjust mid and narrow the search based on whether the total coins fit. This uses the primary pattern of binary search over the answer space, avoiding iterative summation.
Quadratic Formula Optimization
Solve k*(k+1)/2 <= n directly using the quadratic formula: k = floor((-1 + sqrt(1 + 8*n)) / 2). This provides an O(1) solution, but it requires careful handling of integer precision and is prone to overflow if not implemented properly.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity ranges from O(log n) for binary search to O(1) for the quadratic formula solution. Space complexity is O(1) for all approaches since no additional data structures are required.
What Interviewers Usually Probe
- Asks for a solution that scales beyond naive iteration
- Hints at using math formulas to check row completion
- Checks if candidate considered binary search over row numbers
Common Pitfalls or Variants
Common pitfalls
- Off-by-one errors when counting complete rows
- Overflow when computing k*(k+1)/2 for large n
- Confusing total coins with row index, leading to incorrect binary search bounds
Follow-up variants
- Return the total number of coins used in complete rows instead of row count
- Find the first incomplete row's index
- Compute the minimum n required to form exactly k complete rows
How GhostInterview Helps
- Provides a step-by-step derivation for the binary search over valid answer space
- Highlights edge cases where the last row is incomplete
- Calculates correct row counts efficiently without simulating each row
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main strategy to solve Arranging Coins efficiently?
Use binary search over the number of rows or the quadratic formula to find the maximum k such that k*(k+1)/2 <= n.
Why not simply iterate row by row?
Iterating row by row is inefficient for large n and may exceed time limits; binary search or formula approaches scale properly.
How do I handle large n without overflow?
Use long integers or carefully apply the quadratic formula to avoid k*(k+1)/2 exceeding integer limits.
Can this problem be solved in O(1) time?
Yes, applying the quadratic formula directly computes the maximum complete rows in constant time.
How does the binary search pattern apply here?
Binary search checks candidate row counts against the total coins, efficiently narrowing down the largest valid number of complete rows.
Need direct help with Arranging Coins instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Arranging Coins from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Given n, efficiently find the nth digit in the infinite integer sequence using a binary search over valid positions.
Open problem page#483 Smallest Good BaseFind the smallest good base of an integer n using binary search over the valid answer space.
Open problem page#497 Random Point in Non-overlapping RectanglesDesign an algorithm to pick random points within non-overlapping rectangles using binary search and reservoir sampling.
Open problem page