LeetCode 69 – Sqrt(x)

Sqrt(x) is a binary search problem that never mentions a sorted array, and that is the whole lesson. Binary search is not a technique for arrays — it is a technique for any monotonic predicate, and recognising one when there is no array in sight is what this problem tests. It also has an overflow bug so common it is effectively the point of the exercise.

The problem

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. No built-in exponent or square-root functions.

x = 4          -> 2
x = 8          -> 2      2.828... truncated
x = 0          -> 0
x = 1          -> 1
x = 2147483647 -> 46340

Where is the sorted array?

There is not one, and looking for it is the wrong instinct. What there is instead is a question with a monotonic answer:

is k*k <= x ?

k:      0     1     2     3     4     5    ...
k*k<=8: yes   yes   yes   no    no    no

              answer is the last yes

The predicate flips from true to false exactly once and never flips back, because squaring is increasing on non-negative integers. Any predicate with that shape can be binary searched over its domain, array or no array. Say that sentence — "the candidates are ordered and the predicate is monotonic, so I can binary search the answer space" — and the problem is essentially solved.

This reframing has a name worth knowing: binary searching the answer. It is how you attack Koko Eating Bananas (875), Split Array Largest Sum (410) and Capacity To Ship Packages (1011), none of which look like search problems either.

The overflow, which is the actual test

The natural condition is mid * mid <= x. For x near Integer.MAX_VALUE, mid reaches around 1.07 billion during the search and mid * mid overflows into a negative number. A negative is <= x, so the search moves the wrong way and the answer is wrong — with no exception and no crash.

mid * mid <= x           overflows for large mid
(long) mid * mid <= x    fine
mid <= x / mid           fine, and no cast -- but needs mid != 0

The division form is the neat one because it never leaves int range at all. It costs a guard against dividing by zero, which the loop bounds below can simply avoid.

The same bug lurks in the midpoint itself: (lo + hi) / 2 overflows when both are large. lo + (hi - lo) / 2 is the standard fix and it is worth writing reflexively — this was a real bug in the JDK's own binary search for nine years.

Java

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;            // 0 and 1 are their own roots

        int lo = 1, hi = x / 2;         // for x >= 2 the root never exceeds x/2
        int best = 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;         // not (lo + hi) / 2 -- overflow

            if (mid <= x / mid) {                 // i.e. mid*mid <= x, without overflowing
                best = mid;                       // a candidate; look for a bigger one
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return best;
    }
}

hi = x / 2 is a genuine bound rather than a guess: for x >= 4, (x/2)² >= x, so the root cannot be larger. Starting from x also works and costs one extra iteration; being able to justify a tighter bound is worth the sentence.

Carrying best instead of reasoning about where lo and hi land is deliberate. The off-by-one at the end of a binary search — is the answer hi, or lo - 1? — is where these get written wrong under pressure. Recording the last value that satisfied the predicate is unambiguous and costs one variable.

Python

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x

        lo, hi, best = 1, x // 2, 1

        while lo <= hi:
            mid = (lo + hi) // 2          # Python ints are unbounded; no overflow here
            if mid * mid <= x:
                best = mid
                lo = mid + 1
            else:
                hi = mid - 1

        return best

Python's arbitrary-precision integers make both overflow concerns disappear, so mid * mid and (lo + hi) // 2 are safe. Say that explicitly rather than writing the Java-shaped code out of habit — knowing why a guard is unnecessary in one language and mandatory in another is the useful version of that knowledge.

Newton's method, if asked to go faster

    def mySqrtNewton(self, x: int) -> int:
        if x < 2:
            return x

        guess = x
        while guess * guess > x:
            guess = (guess + x // guess) // 2     # converges quadratically

        return guess

Each iteration roughly doubles the number of correct digits, so it converges in a handful of steps rather than about 31. The termination argument is the subtle part: with integer division the sequence decreases while guess² > x and cannot overshoot below the true floor, which is why the loop condition is sufficient and no epsilon is involved.

Offer it as a follow-up, not as the opening answer. Binary search is what the question is asking about, and leading with Newton reads as reciting rather than reasoning.

Complexity

Note that O(√x) is exponential in the size of the input, since x is written in about log x bits. That distinction — the value versus the number of digits — is the same one behind pseudo-polynomial time in knapsack, and mentioning it lands well.

What the interviewer is checking

• That you recognise a monotonic predicate and binary search it without an array present.
• lo + (hi - lo) / 2 for the midpoint.
• That mid * mid overflows, and a fix — long or division.
• x = 0 and x = 1, which the loop bounds must not break on.
• The largest input, which is where the overflow actually bites.
• That the answer is the floor, and how you avoid the closing off-by-one.
• Bonus: Newton's method, and why it terminates on integers.