Arranging Coins - Leetcode 441 - Python
Arranging Coins - Video Solution
Watch 10 video solutions for Arranging Coins, a easy level problem involving Math, Binary Search. This walkthrough by NeetCode has 50,478 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 - 1
Approach Overview
Problem 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.
Complexity Analysis
| 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. |