Arranging Coins solution and explanation
Google
9 more videos on this problem
Arranging Coins - Leetcode 441 - PythonNeetCode · 12:53 · 50K views
Arranging Coins | LeetCode 441 | C++, Java, PythonKnowledge Center · 16:10 · 12K views
Arranging Coins | LeetCode 441 | Programming TutorialsProgramming Tutorials · 11:10 · 4K views
Arranging Coins | Leetcode - 441Algorithms Made Easy · 2:57 · 3K views
Arranging coins | Leet code 441 | Theory explained + Python code | July code challengeSai Anish Malla · 11:19 · 1K views
Leetcode 441 Arranging CoinsRen Zhang · 3:53 · 550 views
441. Arranging Coins #leetcode #leetcodequestionandanswers #java #javainterviewquestionsCodeVia · 2:19 · 227 views
Arranging Coins - LeetCode 441 - Java Solutionalgobest - Computer Science · 2:40 · 110 views
LeetCode 441 | Arranging Coins | Python Binary Search Solution Explained | AlgoYogiAlgo Yogi · 20:02 · 106 views
441. Arranging Coins - Daily Leetcode (Day 61)yeetcode · 1:48 · 100 views
The problem
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.
def arrangeCoins(n):
k = 0
while n >= k + 1:
k += 1
n -= k
return k
n = 8
print(arrangeCoins(n)) # Output: 3class Solution {
public int arrangeCoins(int n) {
int k = 0;
while (n >= k + 1) {
k++;
n -= k;
}
return k;
}
public static void main(String[] args) {
Solution solution = new Solution();
int n = 8;
System.out.println(solution.arrangeCoins(n)); // Output: 3
}
}#include <iostream>
using namespace std;
int arrangeCoins(int n) {
int k = 0;
while (n >= k + 1) {
k++;
n -= k;
}
return k;
}
int main() {
int n = 8;
cout << arrangeCoins(n) << endl; // Output: 3
return 0;
}function arrangeCoins(n) {
let k = 0;
while (n >= k + 1) {
k++;
n -= k;
}
return k;
}
let n = 8;
console.log(arrangeCoins(n)); // Output: 3#include <stdio.h>
int arrangeCoins(int n) {
int k = 0;
while (n >= k + 1) {
k++;
n -= k;
}
return k;
}
int main() {
int n = 5;
printf("%d\n", arrangeCoins(n)); // Output: 2
return 0;
}using System;
public class Solution {
public int ArrangeCoins(int n) {
int k = 0;
while (n >= k + 1) {
k++;
n -= k;
}
return k;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int n = 8;
Console.WriteLine(solution.ArrangeCoins(n)); // Output: 3
}
}Using similar logic in Python, the approach iterates over possible complete rows by checking and deducting the number of coins needed for the next row from n.
Time Complexity: O(√n)
Space Complexity: O(1)
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.
def arrangeCoins(n):
left, right = 0, n
while left <= right:
mid = (left + right) // 2
current = mid * (mid + 1) // 2
if current == n:
return mid
if current > n:
right = mid - 1
else:
left = mid + 1
return right
n = 8
print(arrangeCoins(n)) # Output: 3class Solution {
public int arrangeCoins(int n) {
long left = 0, right = n;
while (left <= right) {
long mid = left + (right - left) / 2;
long current = mid * (mid + 1) / 2;
if (current == n) return (int)mid;
if (current > n) right = mid - 1;
else left = mid + 1;
}
return (int)right;
}
public static void main(String[] args) {
Solution solution = new Solution();
int n = 8;
System.out.println(solution.arrangeCoins(n)); // Output: 3
}
}#include <iostream>
using namespace std;
int arrangeCoins(int n) {
long left = 0, right = n;
while (left <= right) {
long mid = left + (right - left) / 2;
long current = mid * (mid + 1) / 2;
if (current == n) return mid;
if (current > n) right = mid - 1;
else left = mid + 1;
}
return right;
}
int main() {
int n = 8;
cout << arrangeCoins(n) << endl; // Output: 3
return 0;
}function arrangeCoins(n) {
let left = 0, right = n;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
let current = mid * (mid + 1) / 2;
if (current === n) return mid;
if (current > n) right = mid - 1;
else left = mid + 1;
}
return right;
}
let n = 8;
console.log(arrangeCoins(n)); // Output: 3#include <stdio.h>
#include <math.h>
int arrangeCoins(int n) {
long left = 0, right = n;
long mid, current;
while (left <= right) {
mid = left + (right - left) / 2;
current = mid * (mid + 1) / 2;
if (current == n) return mid;
if (current > n) right = mid - 1;
else left = mid + 1;
}
return right;
}
int main() {
int n = 5;
printf("%d\n", arrangeCoins(n)); // Output: 2
return 0;
}using System;
public class Solution {
public int ArrangeCoins(int n) {
long left = 0, right = n;
while (left <= right) {
long mid = left + (right - left) / 2;
long current = mid * (mid + 1) / 2;
if (current == n) return (int)mid;
if (current > n) right = mid - 1;
else left = mid + 1;
}
return (int)right;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int n = 8;
Console.WriteLine(solution.ArrangeCoins(n)); // Output: 3
}
}The Python solution utilizes binary search to explore possible values for k, stopping at the largest k where the complete sum of first k natural numbers does not exceed n.
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 3: Default Approach
func arrangeCoins(n int) int {
left, right := 1, n
for left < right {
mid := (left + right + 1) >> 1
if (1+mid)*mid/2 <= n {
left = mid
} else {
right = mid - 1
}
}
return left
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Iterative Solution | Time Complexity: O(√n) |
| Approach 2: Binary Search | Time Complexity: O(log n) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Iterative Solution | O(sqrt(n)) | O(1) | Best for quickly deriving the idea by simulating rows; simple implementation and easy to reason about. |
| Binary Search | O(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. |
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.