LeetCode 69 - Sqrt(x)

LeetCode Problem 69

Difficulty: 🟢 Easy
Topics: Math, Binary Search

Solution

Problem Understanding

The problem asks us to compute the integer square root of a non negative integer x. More specifically, we need to return the largest integer k such that:

$$k^2 \leq x$$

This means we are not looking for the exact decimal square root. Instead, we must round down to the nearest integer. For example, the square root of 8 is approximately 2.828, but since we round down, the answer becomes 2.

The input is a single integer x, where:

$$0 \leq x \leq 2^{31} - 1$$

The output is another non negative integer representing the floor value of the square root.

An important restriction is that we cannot use built in exponentiation or square root functions. That means methods like math.sqrt(x), pow(x, 0.5), or x ** 0.5 are prohibited. We must derive the result algorithmically.

The constraints tell us that x can be as large as 2,147,483,647, which is over two billion. This immediately suggests that naive iteration could become inefficient. A solution that checks every number from 1 upward may take far too many operations for large inputs.

There are several important edge cases to think about upfront:

• If x = 0, the square root is exactly 0.
• If x = 1, the square root is exactly 1.
• If x is a perfect square, such as 4, 9, or 16, we should return the exact root.
• If x is not a perfect square, such as 8 or 15, we must return the largest integer whose square is still less than x.
• Very large inputs near 2^31 - 1 could create integer overflow problems in some languages when computing mid * mid, particularly in languages with fixed size integers.

Because of these constraints and edge cases, we need an efficient and careful approach.

Approaches

Brute Force Approach

A straightforward solution is to try every integer starting from 0 and keep checking its square until the square becomes larger than x.

For example, if x = 8:

• 0² = 0
• 1² = 1
• 2² = 4
• 3² = 9

At this point, 3² exceeds 8, so the answer must be 2.

This method is correct because we examine numbers in increasing order and stop exactly when we pass the valid range. The previous number is guaranteed to be the largest valid integer.

However, this approach becomes inefficient for large inputs. In the worst case, we may need to check approximately:

$$\sqrt{x}$$

numbers. Since x can exceed two billion, this becomes unnecessarily expensive.

Optimal Approach, Binary Search

The key observation is that the answer space is sorted.

If we pick some number mid:

• If mid² < x, then all smaller numbers are also valid candidates.
• If mid² > x, then all larger numbers are invalid.
• If mid² == x, we found the exact square root.

This monotonic behavior makes the problem a perfect candidate for binary search.

Instead of checking every number, we repeatedly divide the search space in half. We search between 0 and x, narrowing the range until we determine the largest valid integer whose square does not exceed x.

Since binary search cuts the search interval in half every step, the runtime becomes logarithmic.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(√x)	O(1)	Incrementally checks every possible root
Optimal	O(log x)	O(1)	Uses binary search on the answer space

Algorithm Walkthrough

Optimal Algorithm, Binary Search

1. Handle small edge cases immediately.

If x is 0 or 1, return x directly because the square root is trivially the number itself. 2. Define the search boundaries.

Initialize:

• left = 1
• right = x

We know the square root must lie somewhere within this range. 3. Track the best valid answer.

Create a variable answer = 0.

This stores the largest number found so far whose square is less than or equal to x. 4. Compute the middle point.

At each iteration:

$$mid = left + (right - left) // 2$$

This avoids overflow issues in some languages. 5. Compare mid² with x.

There are three possibilities:

• If mid² == x, return mid immediately because we found the exact square root.
• If mid² < x, mid is a valid candidate. Save it in answer and search the right half to see if a larger valid root exists.
• If mid² > x, mid is too large, so search the left half.

6. Continue shrinking the search space.

Repeat until left > right. 7. Return the stored answer.

If no exact square root exists, answer contains the largest valid integer whose square is less than x.

Why it works

The algorithm works because the square function is monotonic for non negative integers. If n² is too small, then every smaller number is also too small. If n² is too large, every larger number must also be too large. Binary search exploits this ordered property and guarantees that we never discard the correct answer. By storing the latest valid candidate, we ensure that even when the square root is irrational, we still return the correct floor value.

Python Solution

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

        left, right = 1, x
        answer = 0

        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid

            if square == x:
                return mid
            elif square < x:
                answer = mid
                left = mid + 1
            else:
                right = mid - 1

        return answer

The implementation starts by handling the smallest edge cases. If x is less than 2, we immediately return it because both 0 and 1 are their own square roots.

Next, we initialize the binary search range from 1 to x. While the search interval remains valid, we calculate the midpoint and compute its square.

If the square exactly matches x, we return the midpoint immediately because we found the precise square root.

When the square is smaller than x, the midpoint becomes a valid candidate, so we store it in answer. However, we continue searching to the right because a larger valid square root may still exist.

When the square exceeds x, the midpoint is too large, so we shrink the search space to the left half.

If the loop finishes without an exact match, the stored answer is returned. This guarantees the correct floor value of the square root.

Go Solution

func mySqrt(x int) int {
    if x < 2 {
        return x
    }

    left, right := 1, x
    answer := 0

    for left <= right {
        mid := left + (right-left)/2
        square := mid * mid

        if square == x {
            return mid
        } else if square < x {
            answer = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return answer
}

The Go implementation follows the same binary search logic as the Python solution. One important consideration in Go is integer overflow. Although LeetCode's constraints fit safely within Go's int on supported systems, using:

mid := left + (right-left)/2

is still preferred because it avoids potential overflow that could happen with (left + right) / 2 in languages with strict integer limits.

Other than syntax differences, the logic remains identical.

Worked Examples

Example 1

Input: x = 4

We search for the largest integer whose square is less than or equal to 4.

Iteration	Left	Right	Mid	Mid²	Action
1	1	4	2	4	Exact match, return 2

Output: 2

Since 2² = 4, we found the exact square root immediately.

Example 2

Input: x = 8

Iteration	Left	Right	Mid	Mid²	Answer	Action
1	1	8	4	16	0	Too large, move left
2	1	3	2	4	2	Valid candidate, search right
3	3	3	3	9	2	Too large, move left

The loop ends because left > right.

Output: 2

The stored answer = 2 is returned because:

$$2^2 = 4 \leq 8$$

and

$$3^2 = 9 > 8$$

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log x)	Binary search halves the search range each iteration
Space	O(1)	Only a constant amount of extra memory is used

The time complexity is logarithmic because each iteration eliminates half of the remaining search space. Even for very large values close to 2^31 - 1, the number of iterations remains small.

The space complexity is constant because the algorithm only stores a few integer variables, regardless of input size.

Test Cases

solution = Solution()

assert solution.mySqrt(0) == 0  # smallest input
assert solution.mySqrt(1) == 1  # smallest perfect square
assert solution.mySqrt(4) == 2  # perfect square
assert solution.mySqrt(8) == 2  # non-perfect square, round down
assert solution.mySqrt(9) == 3  # another perfect square
assert solution.mySqrt(15) == 3  # floor result
assert solution.mySqrt(16) == 4  # exact square root
assert solution.mySqrt(24) == 4  # floor result
assert solution.mySqrt(25) == 5  # perfect square
assert solution.mySqrt(26) == 5  # just above perfect square
assert solution.mySqrt(2147395599) == 46339  # near upper boundary
assert solution.mySqrt(2147483647) == 46340  # maximum constraint

Test	Why
x = 0	Validates smallest possible input
x = 1	Confirms handling of trivial square root
x = 4	Tests exact perfect square
x = 8	Ensures floor rounding works
x = 9	Another exact square root
x = 15	Confirms non perfect square behavior
x = 16	Tests exact match again
x = 24	Verifies floor result near square boundary
x = 25	Perfect square larger than small inputs
x = 26	Ensures correct rounding after square boundary
x = 2147395599	Tests near integer square limit
x = 2147483647	Validates maximum allowed input

Edge Cases

Input is 0

The smallest possible input is 0. A naive implementation might accidentally enter the binary search loop and perform unnecessary work. Since the square root of 0 is exactly 0, the implementation immediately returns x when x < 2.

Input is 1

1 is another special case because its square root is exactly itself. Without explicit handling, the algorithm would still work, but the early return avoids unnecessary iterations and simplifies correctness.

Non Perfect Squares

Inputs like 8, 15, or 26 are important because the true square root is not an integer. A buggy implementation might incorrectly round upward or fail to track the last valid candidate. This implementation solves that problem by storing answer whenever mid² < x. That ensures we always return the correct floor value.

Very Large Inputs

Values close to 2^31 - 1 can expose overflow issues when computing mid * mid. Some languages may overflow if not handled carefully. The binary search midpoint calculation:

left + (right - left) / 2

avoids midpoint overflow, and the constraints ensure multiplication remains manageable in Python and Go.