Sqrt(x) LeetCode Solution: Binary Search on the Answer Space

Sqrt x leetcode (#69) asks you to compute the integer square root of a non-negative integer without using any built-in math library. It sounds like a math problem, but the optimal solution is pure binary search — and it introduces one of the most reusable patterns in all of LeetCode.

The key insight is that you are not searching through an array. You are searching through the answer space itself: the range [0, x]. You are looking for the largest integer mid where mid * mid <= x. This is the "binary search on answer space" pattern in its simplest, most distilled form.

Once you see Sqrt(x) this way, you will recognize the same pattern in Koko Eating Bananas (#875), Capacity to Ship Packages Within D Days (#1011), and dozens of other binary search problems. In this walkthrough, you will learn the approach, implement it safely, and trace through a concrete example.

Given a non-negative integer x, return the integer square root of x — specifically, the largest integer whose square is less than or equal to x. In mathematical terms, return floor(sqrt(x)). You are not allowed to use any built-in exponent functions or operators like pow or sqrt.

For example, sqrt(4) returns 2 because 2 * 2 = 4 exactly. But sqrt(8) returns 2 as well, because 2 * 2 = 4 <= 8, while 3 * 3 = 9 > 8. The answer is the floor, not a rounded value. The constraint is x in [0, 2^31 - 1], which means you need to handle very large inputs carefully.

The sqrt without library constraint is what forces you to think algorithmically. You could try every integer from 0 upward until i * i exceeds x, but that is O(sqrt(x)) time. Binary search brings it down to O(log x) — a massive improvement for large inputs.

The binary search sqrt approach works by defining your search space as [0, x]. At each step, compute mid and check whether mid * mid is less than, equal to, or greater than x. If mid * mid <= x, then mid is a valid candidate — but a larger answer might exist, so you move right. If mid * mid > x, then mid is too big, so you move left.

This is exactly the standard binary search template adapted for the answer space. Instead of searching for a target value in a sorted array, you are searching for the largest integer that satisfies a condition. The condition here is mid * mid <= x, but the structure is identical to any binary search problem.

The time complexity is O(log x) because you halve the search space with each iteration. The space complexity is O(1) — just a few integer variables. For x up to 2^31 - 1, that is roughly 31 iterations at most, which is extremely efficient.

The implementation follows the standard binary search template. Initialize left = 0 and right = x. While left <= right, compute mid = left + (right - left) / 2 (integer division). Compare mid with x / mid to avoid overflow. If mid <= x / mid, record mid as the current answer and move left = mid + 1 to search for a potentially larger value. Otherwise, set right = mid - 1.

Here is the structure in plain English. Set answer = 0. While left <= right: compute mid. If mid <= x / mid, then answer = mid and left = mid + 1. Else right = mid - 1. Return answer. The variable answer always holds the last valid candidate, which is the floor of the square root.

The division trick (mid <= x / mid instead of mid * mid <= x) is critical for languages with fixed-width integers. In Python this is less of a concern due to arbitrary precision, but in Java, C++, and JavaScript with 32-bit constraints, mid * mid can overflow. The division approach is universally safe and is the version interviewers expect.

Let us trace through x = 8 step by step. The search space starts as [0, 8] and answer = 0.

Iteration 1: left = 0, right = 8, mid = 4. Check 4 <= 8 / 4 = 2. Since 4 > 2, mid is too large. Set right = 3. Iteration 2: left = 0, right = 3, mid = 1. Check 1 <= 8 / 1 = 8. Since 1 <= 8, this is valid. Set answer = 1, left = 2. Iteration 3: left = 2, right = 3, mid = 2. Check 2 <= 8 / 2 = 4. Since 2 <= 4, this is valid. Set answer = 2, left = 3. Iteration 4: left = 3, right = 3, mid = 3. Check 3 <= 8 / 3 = 2. Since 3 > 2, mid is too large. Set right = 2.

Now left (3) > right (2), so the loop ends. The answer is 2, which is correct because 2 * 2 = 4 <= 8 and 3 * 3 = 9 > 8. The entire search took only 4 iterations to find the answer in a range of 9 possible values.

Several edge cases deserve attention. When x = 0, the answer is 0. When x = 1, the answer is 1. These are trivial but forgetting them in an interview setting can cost you time. Perfect squares like x = 16 or x = 25 should return exactly 4 and 5 respectively — your binary search will find mid * mid == x in these cases.

The most important edge case is overflow with very large x. When x approaches 2^31 - 1 (2,147,483,647), computing mid * mid can exceed the maximum 32-bit integer. For example, if mid = 46341, then mid * mid = 2,147,488,281 which overflows a 32-bit signed integer. The division trick avoids this entirely.

Another subtle edge case: when x = 2, the answer is 1 (since 1*1 = 1 <= 2 but 2*2 = 4 > 2). This confirms that your binary search correctly returns the floor rather than rounding. Always test your solution with x = 0, 1, 2, a perfect square, and a large value near the constraint boundary.

Sqrt(x) is the gateway problem for binary search on the answer space. The pattern is always the same: define a range of possible answers, pick the midpoint, check whether it satisfies the condition, and narrow the range. The only thing that changes from problem to problem is the condition you check.

In Sqrt(x), the condition is mid * mid <= x. In Koko Eating Bananas (#875), the condition is whether Koko can finish all piles at speed mid within h hours. In Capacity to Ship Packages (#1011), the condition is whether you can ship all packages with capacity mid within d days. The binary search skeleton stays the same.

Mastering this pattern on Sqrt(x) — the simplest possible version — gives you a template you can apply to a dozen harder problems. Review this pattern regularly with YeetCode flashcards so the template is automatic when you see a new "binary search on answer space" problem in an interview.