Approach: Binary search on row count

def arrangeCoins(n):
    lo, hi = 0, n
    while lo <= hi:
        mid = (lo + hi) // 2
        need = mid * (mid + 1) // 2
        if need <= n: lo = mid + 1
        else: hi = mid - 1
    return hi

Complexity: O(log n) time, O(1) space.

Full Solution — all languages

class Solution:
    def arrangeCoins(self, n):
        lo, hi = 0, n
        while lo <= hi:
            mid = (lo + hi) // 2
            need = mid * (mid + 1) // 2
            if need <= n:
                lo = mid + 1
            else:
                hi = mid - 1
        return hi

import java.util.*;
class Solution {
    public int arrangeCoins(int n) {
        long lo = 0, hi = n;
        while (lo <= hi) {
            long mid = (lo + hi) / 2;
            long need = mid * (mid + 1) / 2;
            if (need <= n) lo = mid + 1;
            else hi = mid - 1;
        }
        return (int) hi;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: int arrangeCoins(int n) {
        long long lo = 0, hi = n;
        while (lo <= hi) {
            long long mid = (lo + hi) / 2;
            long long need = mid * (mid + 1) / 2;
            if (need <= n) lo = mid + 1;
            else hi = mid - 1;
        }
        return (int) hi;
    }
};

/**
 * @param {number} n
 * @return {number}
 */ var arrangeCoins = function(n) {
    let lo = 0, hi = n;
    while (lo <= hi) {
        const mid = Math.floor((lo + hi) / 2);
        const need = mid * (mid + 1) / 2;
        if (need <= n) lo = mid + 1;
        else hi = mid - 1;
    }
    return hi;
};

Arranging Coins

Example 1

Example 2

Example 3

Constraints