Skip to main content
Talentd

Arranging Coins - Solution & Explanation

EasyMathBinary Search11 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

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.

Approach 1: Approach 1: Greedy Iterative Solution

This approach involves sequentially counting how many coins are required to form a complete row one row at a time. While the number of available coins is greater than or equal to coins needed for the next row, continue adding rows and reducing the count of available coins accordingly.

The solution involves a while loop that continues to subtract sequential numbers from n. Each time a subtraction is successful, the count of complete rows (k) is incremented. The loop terminates when n is less than the number of coins needed for the next row.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(√n), as the sum of the first k natural numbers grows quadratically.
Space Complexity: O(1), constant space is used.

Try this approach in the editor →

Approach 2: Approach 2: Binary Search

Using a binary search, optimize the process of finding the maximum k where the sum of the first k natural numbers is less than or equal to n. Calculate mid values and determine if they result in a possible sum being less or equal to n and adjust the search space accordingly.

The C code employs long integers for intermediate calculations to avoid overflow. The binary search algorithm adjusts the search range based on whether the calculated sum of coins (for k = mid) is greater or less than n.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Greedy Iterative Solution

Time Complexity: O(√n), as the sum of the first k natural numbers grows quadratically.
Space Complexity: O(1), constant space is used.

Approach 2: Binary Search

Time Complexity: O(log n)
Space Complexity: O(1)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Iterative SolutionO(sqrt(n))O(1)Best for quickly deriving the idea by simulating rows; simple implementation and easy to reason about.
Binary SearchO(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.

Video Solution

Arranging Coins - Leetcode 441 - Python • NeetCode • 50,478 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Arranging Coins easy or hard?
Arranging Coins is classified as an Easy problem on LeetCode. The basic greedy solution is straightforward, while the binary search optimization introduces a small algorithmic insight that often appears in beginner interview practice.
Arranging Coins Python or Java solution?
A typical Python or Java solution either iteratively subtracts row sizes or performs binary search using the formula k(k+1)/2. Both implementations run in constant space, while binary search achieves O(log n) time for large inputs.
How to solve Arranging Coins in O(log n)?
Use binary search on the number of possible rows k. Check whether k(k+1)/2 is less than or equal to n to determine if k rows can be formed. Adjust the search range accordingly until the largest valid k is found, resulting in O(log n) time and O(1) space.
What is the best approach for Arranging Coins?
Binary search is generally considered the best approach. It finds the largest k such that k(k+1)/2 <= n by searching the answer space instead of checking rows sequentially. This reduces the time complexity to O(log n) while using constant O(1) space.
What data structure is used in Arranging Coins?
No specialized data structure is required. The problem primarily relies on arithmetic calculations and optionally binary search over an integer range. The focus is on mathematical insight rather than arrays, hash maps, or trees.
What is the time complexity of Arranging Coins?
The greedy iterative approach runs in O(sqrt(n)) time because the number of rows grows roughly with the square root of n. A binary search optimization reduces the complexity to O(log n) by searching for the maximum valid row count. Both approaches use O(1) space.
Is Arranging Coins asked at Google, Amazon, or Meta?
Arranging Coins appears frequently in technical interviews because it tests mathematical reasoning and binary search. Variants of the problem have appeared in interviews at companies like Amazon and Google, especially for entry-level or early interview rounds.

Ready to solve this problem?

Practice Arranging Coins with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer