Arranging Coins LeetCode

Key takeaways:

  • The "Arranging Coins" problem involves determining how many complete rows of coins can be formed in a staircase pattern.

  • Each row requires one more coin than the previous row, following a triangular sequence.

  • A binary search approach efficiently computes the solution with a time complexity of O(logn).

  • Real-world applications include budget allocation, resource distribution, and game level design.

  • The problem demonstrates the use of mathematical reasoning and algorithmic efficiency in practical scenarios.

What is the Arranging Coins problem?

The “Arranging Coins” problem on LeetCode involves taking a given number of coins and arranging them in a staircase pattern. In this staircase, each row has an additional coin compared to the row above it. The goal is to determine the maximum number of complete rows we can form using the coins available.

For instance, if the total number of coins is 5:

  • Row 1 would contain 1 coin.

  • Row 2 would contain 2 coins.

  • Row 3 would need 3 coins, but only 2 remain, making it incomplete.

This concept can be applied to several real-world scenarios:

  • Budget allocation: Distributing a fixed budget (analogous to coins) across projects where each subsequent project requires incrementally more funds. The goal is to determine how many projects can be fully funded.

  • Resource distribution: Allocating resources like bandwidth or memory blocks, where each subsequent request requires a greater allocation. This helps decide how many requests can be entirely fulfilled.

  • Pyramid games or levels: Calculating the number of levels or tiers that can be completed in a game given a fixed amount of points or currency, where each level requires progressively more resources.

These examples highlight how the problem's logic can be extended beyond coins to various practical applications.

Problem statement

Given an integer n representing the total number of coins, calculate the maximum number of complete rows you can form in a staircase pattern. Each subsequent row requires one more coin than the previous row, forming a triangular sequence.

Key points to keep in mind:

  • You have a single, fixed pile of coins to work with.

  • Each complete row requires increasing coins (1, 2, 3, …).

  • The last row may be incomplete if there aren’t enough coins left.

Your output should be an integer representing the maximum number of complete rows.

Constraints:

  • 1 <= n <= 231 - 1

Let’s take a look at a few examples to get a better understanding of the problem statement:

canvasAnimation-image
1 of 3

Knowledge test

Let’s take a moment to ensure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem.

1

What is the goal of the “Arranging Coins” problem?

A)

To calculate how many coins can fit into a specific number of rows.

B)

To determine the maximum number of complete rows that can be formed using a given number of coins.

C)

To arrange coins in a pyramid shape.

D)

To find the total number of coins required to form a complete staircase.

Question 1 of 30 attempted

Solution

The solution to this problem utilizes the binary search pattern to efficiently determine the maximum number of complete rows that can be formed with the given number of coins. Binary search helps narrow the possible values quickly by reducing the search space by half in each iteration. This approach ensures we find the optimal number of rows in an optimal number of steps, leveraging the properties of triangular numbers.

Here’s how the algorithm works:

  1. Initialize two pointers—left and right—to represent the range of possible values for the number of complete rows. The left pointer is set to 0, and the right pointer is set to n (the total number of coins).

  2. Perform a binary search until the left pointer is less than or equal to the right pointer. In each iteration, calculate the middle value mid using the formula:

  1. Next, the total number of coins required to form mid rows are computed using the triangular number formula:

  1. If the total coins required for mid rows (coinsNeeded) is equal to n, the maximum number of complete rows has been found, and mid is returned.

  2. If coinsNeeded is less than n, more coins are needed to form additional rows, so the left pointer is adjusted to mid + 1 to search in the higher half of the range.

  3. If coinsNeeded is greater than n, fewer rows are needed, so the right pointer is adjusted to mid - 1 to search in the lower half.

  4. Once the loop exits, the right pointer will point to the maximum number of complete rows that can be formed so right is returned.

Let’s look at the following illustration to get a better understanding of the solution:

canvasAnimation-image
1 of 10

Let’s look at the code for this solution below:

def arrangeCoins(n):
left = 0 # Initialize left pointer for the search space
right = n # Initialize right pointer for the search space
while left <= right:
mid = left + (right - left) // 2 # Calculate the middle index
coins_needed = (mid * (mid + 1)) // 2 # Number of coins needed for 'mid' rows
if coins_needed == n:
return mid # If the coins match exactly, return the number of rows
elif coins_needed < n:
left = mid + 1 # Need more coins, shift left pointer to search higher values
else:
right = mid - 1 # Too many coins, shift right pointer to search lower values
return right # Return the highest possible index for complete rows
#driver
def main():
# Test cases
test_cases = [
(7, 3), # Example case where 7 coins can form 3 complete rows
(15, 5), # Edge case where no coins are available
(1, 1), # Edge case where only one coin is available
(8, 3), # Case where 8 coins can form 3 complete rows
(10, 4) # Case where 10 coins can form 4 complete rows
]
for idx, (n, expected) in enumerate(test_cases):
result = arrangeCoins(n)
print(f"Test case {idx + 1}: n = {n} ----> Expected: {expected}, Got: {result}")
assert result == expected, f"Test case {idx + 1} failed!"
print("All test cases passed!")
if __name__ == "__main__":
main()
Arranging Coins in Python

Now that we have a solution for this LeetCode problem, let’s analyze its time and space complexity to understand how efficiently it scales with larger inputs. 

Time complexity

The time complexity of this algorithm is O(log n)O(log\ n), employing binary search to determine the maximum number of complete rows achievable with a given number of coins, reducing the search space by half at each iteration.

Space complexity

The space complexity of this algorithm is O(1)O(1)as it utilizes a constant amount of additional space that remains unaffected by the input size, using few variables for computation and comparison within the function.

Practice resources for LeetCode problems

To further strengthen your coding skills and boost your technical interview preparation, here are some LeetCode problems to practice:

Also, you can explore these courses designed specifically to help you ace technical interviews:

Moreover, if you’re confident in your preparation, consider trying Educative’s AI-powered mock interviewsMock interviews are excellent for building confidence, sharpening problem-solving skills, and identifying areas to improve before the actual interview.

Frequently asked questions

Haven’t found what you were looking for? Contact Us


What happens if the number of coins is less than the required number for the first few rows?

If there aren’t enough coins to complete the first few rows, the algorithm will return the maximum number of complete rows that can be formed with the available coins. The last row may be incomplete, but the rows before it will be fully formed.


Why use binary search over brute force?

Brute force would iterate through all possible rows up to n, resulting in O(n​) complexity, which is less efficient compared to O(logn). Binary search is particularly useful for large inputs due to its logarithmic scaling.


How does the algorithm handle large values of n?

It uses integer arithmetic, ensuring no overflow occurs, and efficiently reduces the search space to determine the number of rows.


How can the "Arranging Coins” problem be solved without iteration?

The problem can be solved using a mathematical formula derived from the constraint k(k+1) ≤ 2N. By manipulating this equation, the maximum number of complete rows can be computed directly using a closed-form expression. This approach eliminates the need for iteration, providing a constant time and space solution.


What happens in distributed systems?

If coin counts are distributed across systems, synchronizing counts and ensuring accurate results might add latency, but the binary search logic would remain unchanged.


Free Resources

Copyright ©2025 Educative, Inc. All rights reserved