Arranging Coins: Binary Search on Triangular Numbers

Arranging Coins is LeetCode 441. You have n coins and you want to build a staircase. The first row has 1 coin, the second row has 2 coins, the third row has 3 coins, and so on. Each row must be completely filled before you move to the next one, except possibly the last row. Your task is to return the number of complete rows in the staircase.

This is a clean example of binary search on the answer space, and it connects directly to the concept of triangular numbers.

Why this problem matters

At first glance, this looks like a simple counting problem. You could just keep subtracting 1, 2, 3, ... from n until you run out of coins. That works, but it runs in O(sqrt(n)) time because the number of complete rows grows with the square root of n.

The real value of this problem is that it teaches you to recognize when a search on the answer is possible. Instead of simulating the process row by row, you can jump directly to the answer using binary search, or even solve it in constant time with a math formula. If you have practiced Sqrt(x) or Koko Eating Bananas, you will recognize the same structural pattern here.

The key insight

To fill k complete rows, you need exactly k * (k + 1) / 2 coins. This is the k-th triangular number. You want the largest k where k * (k + 1) / 2 is <= n.

That condition is monotonic: for every k from 1 up to some point, the triangular number fits within n. After that point, it exceeds n. Monotonicity is what makes binary search work. You are searching for the rightmost k where the condition holds.

The solution

def arrangeCoins(n):
    lo, hi = 1, n

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        coins_needed = mid * (mid + 1) // 2

        if coins_needed <= n:
            lo = mid + 1
        else:
            hi = mid - 1

    return hi

lo = 1, hi = n. The smallest possible answer is 1 (when n >= 1). The largest possible answer is n itself, since row k needs k coins and the triangular sum only grows.

mid = lo + (hi - lo) // 2. Pick the middle candidate number of rows.

coins_needed = mid * (mid + 1) // 2. This is the triangular number formula. It tells you exactly how many coins you need to completely fill mid rows.

if coins_needed is <= n: lo = mid + 1. The current mid works. You have enough coins for mid complete rows. But maybe you can fit even more rows, so search to the right.

else: hi = mid - 1. You do not have enough coins for mid rows. Every larger value also fails. Move hi below mid.

Return hi. When the loop exits, hi is the last value of k where the triangular sum fits within n.

You can also solve this in O(1) time using the quadratic formula. The equation k * (k + 1) / 2 = n rearranges to k^2 + k - 2n = 0. Applying the quadratic formula and taking the positive root:

def arrangeCoins_math(n):
    return int((-1 + (1 + 8 * n) ** 0.5) / 2)

Visual walkthrough

Let's trace the binary search for n = 8. The candidate answers are k = 1 through k = 8. For each k, the label shows how many total coins k complete rows would need.

Three iterations to find the answer. The binary search quickly zeroes in on k = 3, where 3 complete rows use 6 coins and the 4th row would need 10 total, which exceeds 8.

Complexity analysis

Binary search halves the candidate range each iteration. Since the range is at most n, you do at most O(log n) iterations. Each iteration does a constant amount of work (one multiplication, one comparison).

Math formula computes the answer directly with a square root and a few arithmetic operations, all in constant time. The tradeoff is that you need to trust floating-point precision for large n.

Both approaches use O(1) space, just a few variables.

Edge cases

• n = 1: One coin fills exactly one row. The answer is 1.
• n = 0: Zero coins, zero complete rows. Note: the binary search version with lo = 1 would return hi = 0 since the loop exits immediately. If you want to handle n = 0, either return 0 as a special case or start lo = 0.
• Triangular number (e.g., n = 6): When n is exactly a triangular number, the last row is perfectly filled. For n = 6, you get 3 complete rows with zero coins left over.
• Large n: For n near 2^31 - 1, mid * (mid + 1) can overflow a 32-bit integer. In Python this is not an issue due to arbitrary precision integers. In Java or C++, use long or check mid against n / mid to avoid overflow.
• Just one coin short (e.g., n = 9): 3 complete rows use 6 coins, leaving 3 for the 4th row which needs 4. Still returns 3. At n = 10, you get exactly 4 complete rows.

The building blocks

Binary search on the answer space. You are not searching through an array. You are searching through all possible values of k (number of complete rows) and checking a condition against each. The condition k * (k + 1) / 2 is <= n is monotonic, which is the only requirement for binary search to work. This same pattern appears in Sqrt(x), Koko Eating Bananas, and Split Array Largest Sum.

Triangular numbers. The formula k * (k + 1) / 2 is one of the most common closed-form sums in programming interviews. Knowing it lets you convert a summation loop into a single arithmetic expression, which is the key to both the binary search and the O(1) solutions here.

From understanding to recall

The logic is clear once you see it: binary search the number of rows, compare the triangular sum to n, return the rightmost fit. You can probably picture the whole solution right now.

But in an interview next month, the small decisions will trip you up. Is it lo = mid or lo = mid + 1? Do you return lo or hi? Is the formula k * (k + 1) / 2 or k * (k - 1) / 2? These details feel obvious today but become fuzzy under pressure.

Spaced repetition locks them in. You type the solution from scratch today, again tomorrow, then in a few days. After a handful of rounds, the boundary template and the triangular number formula become automatic. You write them without thinking.

Arranging Coins is an ideal SRS card: the code is about 8 lines, it reinforces the binary search on answer pattern, and it tests whether you remember the triangular number formula and the correct return value.

Related posts

• Sqrt(x) - The same binary search on answer pattern, searching for the largest integer whose square fits within x
• Valid Perfect Square - Another binary search on a mathematical condition, checking whether an exact match exists
• Search Insert Position - Binary search for a boundary in a sorted array, the foundational variant that these answer-space problems build on