LeetCode 441 - Arranging Coins

The problem asks us to determine how many complete rows of a coin staircase can be formed using exactly n coins. A staircase arrangement follows a very specific structure: - The first row contains 1 coin - The second row contains 2 coins - The third row contains 3 coins -…

leetcodeeasymathbinary-search

LeetCode Problem 441

Difficulty: 🟢 Easy
Topics: Math, Binary Search

Solution

Problem Understanding

The problem asks us to determine how many complete rows of a coin staircase can be formed using exactly n coins.

A staircase arrangement follows a very specific structure:

  • The first row contains 1 coin
  • The second row contains 2 coins
  • The third row contains 3 coins
  • Continuing in this pattern, the kth row contains exactly k coins

The staircase must be built row by row in order. If there are not enough remaining coins to fully complete the next row, construction stops, and we return the number of fully completed rows.

For example, if n = 5:

  • Row 1 uses 1 coin, remaining = 4
  • Row 2 uses 2 coins, remaining = 2
  • Row 3 requires 3 coins, but only 2 remain

Since the third row cannot be completed, the answer is 2.

The input is a single integer n, representing the total number of available coins. The output is an integer representing the maximum number of complete staircase rows.

The constraints are important:

1 <= n <= 2^31 - 1

This means n can be as large as 2,147,483,647. A straightforward simulation may still work for this range because the number of rows grows approximately as the square root of n, but the problem strongly suggests that we should think carefully about efficiency and possible mathematical optimization.

An important mathematical observation is that the total number of coins needed to build k complete rows is:

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

So the real goal is to find the largest integer k such that:

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

Several edge cases are important:

  • Very small inputs like n = 1
  • Inputs that form a perfect staircase exactly, such as n = 6
  • Inputs where the next row is only short by one coin, such as n = 5
  • Extremely large values near 2^31 - 1, where overflow can become a concern in some languages

The problem guarantees that n is always positive, so we never need to handle zero or negative inputs.

Approaches

Brute Force Approach

The most direct solution is to simulate building the staircase one row at a time.

We start with row 1, subtract its required number of coins from n, then move to row 2, and continue until we no longer have enough coins to complete the next row.

For example:

  • Subtract 1 coin
  • Subtract 2 coins
  • Subtract 3 coins
  • Continue while enough coins remain

The moment the remaining coins are less than the size of the next row, we stop and return the number of completed rows.

This approach is correct because it exactly mirrors the construction process described in the problem statement. Each successful subtraction corresponds to one fully completed row.

The time complexity is approximately O(sqrt(n)), because the number of rows that can be formed grows roughly with the square root of n.

Although this is fast enough for the given constraints, we can do better by using mathematics and binary search.

Optimal Approach

The key insight is that the number of coins required for k rows follows a known arithmetic series formula:

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

Instead of constructing rows one by one, we can search directly for the largest valid k satisfying:

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

This condition is monotonic:

  • If some k works, then all smaller values also work
  • If some k does not work, then all larger values also fail

That monotonic property makes binary search an ideal solution.

We search within the range [1, n]:

  • Compute a midpoint mid
  • Calculate how many coins are needed for mid rows
  • If the required coins are less than or equal to n, then mid is valid, so we try larger values
  • Otherwise, mid is too large, so we search smaller values

This reduces the time complexity to O(log n).

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(sqrt(n)) O(1) Simulates building rows one by one
Optimal O(log n) O(1) Uses binary search on the arithmetic series formula

Algorithm Walkthrough

  1. Initialize two pointers, left and right.

We search for the answer within the range [1, n]. The smallest possible answer is 1, and the largest possible answer cannot exceed n. 2. Start a binary search loop while left <= right.

This ensures every possible candidate value is checked systematically. 3. Compute the midpoint.

mid = (left + right) // 2

The midpoint represents a candidate number of complete rows. 4. Calculate the number of coins required for mid rows.

Use the arithmetic series formula:

$\text{coins}=\frac{mid(mid+1)}{2}$ 5. Compare the required coins with n.

  • If the required number is exactly n, we found the perfect staircase, so return mid
  • If the required number is less than n, then mid is valid, but a larger answer may exist
  • If the required number is greater than n, then mid is too large
  1. Adjust the search range accordingly.
  • Valid midpoint:
left = mid + 1
  • Invalid midpoint:
right = mid - 1
  1. Continue until the search space is exhausted.

At the end of the search, right will contain the largest valid number of complete rows.

Why it works

The binary search works because the function:

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

is strictly increasing. As k grows, the number of required coins always increases.

Therefore:

  • All valid values appear before all invalid values
  • Binary search can efficiently locate the boundary between them

The algorithm always converges to the largest k satisfying:

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

which is exactly the definition of the problem.

Python Solution

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

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

            if required_coins == n:
                return mid

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

        return right

The implementation begins by setting up the binary search boundaries. The search space includes every possible number of staircase rows from 1 to n.

Inside the loop, the midpoint is treated as a candidate answer. The code computes how many coins would be required to build exactly that many rows.

If the required number matches n, the staircase is perfect, so the answer is returned immediately.

If fewer coins are required than available, the candidate is valid, and the algorithm attempts to find a larger valid value by moving the left boundary upward.

If too many coins are required, the midpoint is invalid, so the right boundary moves downward.

When the loop finishes, right stores the largest valid number of complete rows, which is returned.

Python integers automatically handle large values safely, so overflow is not a concern in this implementation.

Go Solution

func arrangeCoins(n int) int {
    left := 1
    right := n

    for left <= right {
        mid := left + (right-left)/2

        requiredCoins := int64(mid) * int64(mid+1) / 2

        if requiredCoins == int64(n) {
            return mid
        }

        if requiredCoins < int64(n) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return right
}

The Go implementation follows the same binary search logic as the Python version. The main difference is integer overflow handling.

Since mid * (mid + 1) may exceed the range of a 32-bit integer, the calculation is explicitly converted to int64 before multiplication. This prevents overflow for large input values near 2^31 - 1.

The midpoint calculation uses:

mid := left + (right-left)/2

which is a common overflow-safe binary search pattern.

Worked Examples

Example 1

Input:

n = 5

We want the largest k such that:

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

Iteration left right mid required_coins Action
1 1 5 3 6 Too large, move right
2 1 2 1 1 Valid, move left
3 2 2 2 3 Valid, move left

Loop ends because left = 3 and right = 2.

Return right = 2.

Final answer:

2

Example 2

Input:

n = 8

We want the largest k such that:

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

Iteration left right mid required_coins Action
1 1 8 4 10 Too large, move right
2 1 3 2 3 Valid, move left
3 3 3 3 6 Valid, move left

Loop ends because left = 4 and right = 3.

Return right = 3.

Final answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(log n) Binary search halves the search space each iteration
Space O(1) Only a few integer variables are used

The binary search repeatedly cuts the search range in half, which leads to logarithmic time complexity.

No additional data structures are allocated. The algorithm only stores a constant number of integer variables, so the space complexity is constant.

Test Cases

solution = Solution()

assert solution.arrangeCoins(1) == 1  # Smallest valid input
assert solution.arrangeCoins(2) == 1  # Second row incomplete
assert solution.arrangeCoins(3) == 2  # Exact staircase of 2 rows
assert solution.arrangeCoins(5) == 2  # Example 1
assert solution.arrangeCoins(6) == 3  # Exact staircase of 3 rows
assert solution.arrangeCoins(8) == 3  # Example 2
assert solution.arrangeCoins(10) == 4  # Exact staircase of 4 rows
assert solution.arrangeCoins(11) == 4  # One extra coin beyond perfect staircase
assert solution.arrangeCoins(15) == 5  # Larger exact staircase
assert solution.arrangeCoins(16) == 5  # Just above exact staircase
assert solution.arrangeCoins(2147483647) == 65535  # Maximum constraint value

Test Case Summary

Test Why
n = 1 Smallest possible input
n = 2 Incomplete second row
n = 3 Exact triangular number
n = 5 Provided example with incomplete row
n = 6 Perfect staircase formation
n = 8 Provided example
n = 10 Another exact triangular number
n = 11 Slightly above a perfect staircase
n = 15 Larger exact staircase
n = 16 Larger incomplete staircase
n = 2147483647 Maximum allowed input

Edge Cases

One important edge case is the smallest possible input, n = 1. A buggy implementation might incorrectly return 0 if the binary search boundaries are initialized improperly. In this solution, the search begins at 1, and the formula correctly identifies that one complete row can be built.

Another important edge case occurs when n is exactly a triangular number, such as n = 6 or n = 10. In these cases, the staircase can be completed perfectly with no leftover coins. The implementation handles this correctly because it immediately returns mid when the required number of coins exactly equals n.

A third critical edge case involves extremely large values close to the upper constraint limit. In Go, multiplying large integers can overflow a 32-bit integer type. The implementation avoids this issue by converting intermediate calculations to int64 before multiplication. This guarantees correctness even for n = 2147483647.

Another subtle edge case occurs when the answer lies immediately below an invalid midpoint. For example, with n = 5, the midpoint 3 requires 6 coins and is invalid, while 2 is the correct answer. Returning right after the loop guarantees that we return the largest valid value rather than the first invalid one.