LeetCode 441: Arranging Coins

Problem Restatement

We are given n coins.

We want to arrange them into a staircase shape.

The staircase must follow this rule:

Row	Number of Coins
1st row	1
2nd row	2
3rd row	3
...	...

Each row must contain exactly one more coin than the previous row.

We need to return the number of complete rows that can be formed.

The last row may be incomplete, and incomplete rows do not count.

The official problem asks for the number of complete staircase rows that can be formed using exactly n coins. (leetcode.com)

Input and Output

Item	Meaning
Input	Integer n
Output	Number of complete rows
Row sizes	1, 2, 3, ...
Incomplete row	Does not count

Example function shape:

def arrangeCoins(n: int) -> int:
    ...

Examples

Example 1:

n = 5

We build rows:

row 1 -> 1 coin
row 2 -> 2 coins
row 3 -> needs 3 coins

After the first two rows:

1 + 2 = 3

We have:

5 - 3 = 2

coins left, which is not enough for row 3.

So the answer is:

2

Example 2:

n = 8

We build:

1 + 2 + 3 = 6

Two coins remain:

8 - 6 = 2

which is not enough for row 4.

Answer:

3

Example 3:

n = 1

We can build one row:

1

Answer:

1

First Thought: Simulate Row by Row

We can repeatedly subtract row sizes.

Start with:

row = 1

Then:

n -= row
row += 1

until we cannot build the next row.

This works.

However, the problem has a direct mathematical structure.

Key Insight

To build k complete rows, we need:

1 + 2 + 3 + ... + k

coins.

This sum is the triangular number formula:

$$ 1+2+3+\cdots+k=\frac{k(k+1)}{2} $$

So we need the largest integer k such that:

$$ \frac{k(k+1)}{2}\le n $$

This is a monotonic condition:

k	Coins Needed
Larger k	Needs more coins
Smaller k	Needs fewer coins

Because the condition changes only once from true to false, binary search works perfectly.

Algorithm

Binary search on the answer.

The number of complete rows must lie between:

0 and n

For a candidate mid, compute:

$$ \frac{mid(mid+1)}{2} $$

If this value is less than or equal to n, then mid complete rows are possible.

Move right to search for a larger answer.

Otherwise, move left.

At the end, return the largest valid k.

Correctness

For any integer k, the number of coins required to build k complete rows is:

$$ \frac{k(k+1)}{2} $$

This value increases as k increases.

Therefore:

Condition	Meaning
required(k) <= n	k rows are possible
required(k) > n	k rows are impossible

So the set of valid k values forms a prefix:

valid, valid, valid, ..., invalid, invalid

Binary search correctly finds the largest valid k.

Whenever the midpoint satisfies the inequality, the answer is at least that large, so searching right preserves correctness.

Whenever the midpoint fails the inequality, the answer must be smaller, so searching left preserves correctness.

When the search ends, the returned value is the maximum number of complete rows that can be formed.

Complexity

Metric	Value	Why
Time	O(log n)	Binary search halves the range each step
Space	O(1)	Only a few variables are used

Implementation

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left = 0
        right = n

        while left <= right:
            mid = (left + right) // 2

            coins_needed = mid * (mid + 1) // 2

            if coins_needed <= n:
                left = mid + 1
            else:
                right = mid - 1

        return right

Code Explanation

We search between:

left = 0
right = n

The midpoint candidate is:

mid = (left + right) // 2

The number of coins needed for mid rows is:

$$ \frac{mid(mid+1)}{2} $$

implemented as:

coins_needed = mid * (mid + 1) // 2

If enough coins exist:

if coins_needed <= n:

then mid is valid, and we try larger values:

left = mid + 1

Otherwise, mid is too large:

right = mid - 1

When the loop finishes, right stores the largest valid row count.

Testing

def run_tests():
    s = Solution()

    assert s.arrangeCoins(1) == 1

    assert s.arrangeCoins(5) == 2

    assert s.arrangeCoins(8) == 3

    assert s.arrangeCoins(3) == 2

    assert s.arrangeCoins(6) == 3

    assert s.arrangeCoins(10) == 4

    assert s.arrangeCoins(0) == 0

    assert s.arrangeCoins(2147483647) == 65535

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
1	Smallest non-zero case
5	Incomplete third row
8	Standard example
3	Exact triangular number
6	Exact larger triangular number
10	Another exact staircase
0	No coins
Large input	Checks overflow safety and efficiency