What pattern does Sqrt(x) use?

The Pattern: Modified Binary Search (Search for Integer Square Root) The Heuristic: When searching for an integer value satisfying a monotonic condition (like mid*mid <= x), use binary search to narrow the range by comparing mid^2 to x, adjusting boundaries accordingly until convergence.

Sqrt(x) - LeetCode Solution & Explanation

Q: What is the time complexity of Sqrt(x)?

O(log x). Each iteration halves the search space between left and right, leading to logarithmic time relative to x.

Problem

Given a non-negative integer x, return the integer part of the square root of x (i.e., floor of the square root).

0 ≤ x ≤ 2³¹ - 1

Example

Input: x = 8

Output: 2

The exact square root of 8 is approximately 2.8284. The algorithm uses a binary search between 0 and 8 to find the integer part. It checks midpoints and their squares, narrowing the search space. When the search completes, it returns 2, the floor of the square root.

Approach

Straightforward Solution

A naive approach would be to iterate from 0 up to x, checking each number's square until exceeding x. This is O(x) time, which is inefficient for large x.

Core Observation

The square root of a number x lies between 0 and x (inclusive). The function f(mid) = mid * mid is monotonic increasing for mid >= 0, allowing binary search to efficiently find the integer square root.

Path to Optimal

Recognizing the monotonic nature of mid^2 allows the use of binary search. By repeatedly halving the search space and comparing mid^2 to x, the algorithm quickly converges to the integer square root in O(log x) time.

Optimal Approach

Use a binary search with pointers left = 0 and right = x. Calculate mid = (left + right) // 2 and mid^2. If mid^2 equals x, return mid immediately. If mid^2 < x, move left to mid + 1 to search higher values. Otherwise, move right to mid - 1 to search lower values. When the loop ends, right points to the floor of the square root.

Time

O(log x)

Each iteration halves the search space between left and right, leading to logarithmic time relative to x.

Space

O(1)

Only a fixed number of variables (left, right, mid, sq) are used, requiring constant auxiliary space.

Solution

1class Solution:
  def mySqrt(self, x: int) -> int:
      
      left, right = 0, x
5
      while left <= right:
          
          mid = (left + right) // 2
          sq = mid * mid
10
          if sq == x:
              return mid
          elif sq < x:
              left = mid + 1
          else:
              right = mid - 1
17
      return right

Step-by-Step Solution

1

Initialize Binary Search Boundaries

4	`left, right = 0, x`

Objective

To set the initial search range for the integer square root between 0 and x.

Key Insight

The square root of x cannot be greater than x itself, so initializing left to 0 and right to x covers the entire possible range. This sets the stage for a binary search that will efficiently narrow down the correct integer root.

Interview Quick-Check

Core Logic

Setting left = 0 and right = x ensures the search space includes all possible integer square roots.

2

Perform Binary Search to Narrow Down Integer Square Root

6while left <= right:
  mid = (left + right) // 2
  sq = mid * mid
  if sq == x:
      return mid
  elif sq < x:
      left = mid + 1
  else:
      right = mid - 1

Objective

To iteratively adjust the search boundaries based on the square of the midpoint until the integer square root is found.

Key Insight

By calculating mid = (left + right) // 2 and comparing mid^2 to x, the algorithm exploits the monotonic property of the square function. If mid^2 equals x, the exact root is found. If mid^2 is less than x, the root must be higher, so left moves up. If mid^2 is greater, the root must be lower, so right moves down. This process efficiently converges to the floor of the square root.

Interview Quick-Check

Core Logic

The binary search loop maintains the invariant that the integer square root lies between left and right, adjusting boundaries based on mid^2 comparisons.

State & Boundaries

The loop condition left <= right ensures all candidates are considered, and the search terminates when left surpasses right.

Common Pitfalls & Bugs

Incorrectly updating left or right (e.g., not adding or subtracting 1) can cause infinite loops or missed candidates.

3

Return the Floor of the Square Root After Search Completion

18	`return right`

Objective

To return the greatest integer whose square is less than or equal to x after the binary search loop ends.

Key Insight

When the loop terminates, left has moved beyond the integer square root, while right points to the correct floor value. Returning right ensures the function returns the integer part of the square root, satisfying the problem's requirement.

Interview Quick-Check

Core Logic

Returning right after the loop correctly returns the floor of the square root because right is the last valid candidate.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 11 Critical

if sq == x:

Check whether mid squared equals x.

If mid squared equals x, an exact integer square root has been found and the search can terminate immediately.

Line 18 Critical

return right

Return right as the integer square root of x.

When the loop terminates, right points to the greatest integer whose square does not exceed x, which by definition is the floor of the square root.

Line 4 Core

left, right = 0, x

Initialize the binary search boundaries with left = 0 and right = x.

Setting the search range to [0, x] ensures every possible integer square root candidate is included, since the square root of x cannot exceed x.

Line 9 Core

sq = mid * mid

Compute the square of the midpoint value.

Squaring the midpoint allows comparison with x, leveraging the monotonic growth of the square function.

Line 12 Core

return mid

Return mid when an exact square root is found.

Returning mid immediately avoids unnecessary iterations once the perfect square root has been identified.

Line 13 Core

elif sq < x:

Determine that the search must continue in the right half of the interval.

If mid squared is less than x, the true square root must lie strictly to the right of mid because all values up to mid produce squares that are too small.

Line 14 Core

left = mid + 1

Move the left boundary to mid + 1 to search higher values.

Advancing left to mid + 1 discards mid and all smaller candidates, restricting the search to larger values.

Line 15 Core

else:

Determine that the search must continue in the left half of the interval.

If mid squared exceeds x, mid is too large to be the square root, so the correct value must lie among smaller candidates.

Line 16 Core

right = mid - 1

Move the right boundary to mid - 1 to search lower values.

Decreasing right to mid - 1 removes mid and all larger values from consideration, narrowing the search to smaller candidates.

Line 6 Core

while left <= right:

Start the binary search loop while left is less than or equal to right.

Binary search continues while the search interval contains candidate values, maintaining the invariant that the integer square root lies within [left, right].

Line 8 Core

mid = (left + right) // 2

Calculate the midpoint of the current search interval.

Computing the midpoint splits the search space roughly in half, enabling logarithmic convergence toward the correct square root.

Test Your Understanding

Why does the algorithm return 'right' after the binary search loop instead of 'left'?

Because when the loop ends, 'left' is positioned just beyond the integer square root, while 'right' points to the greatest integer whose square is less than or equal to x, which is the correct floor value.

Don't just read it. Drill it.

Reconstruct Sqrt(x) from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Sqrt(x) drill

or drill a free problem

6	`while left <= right:`
8	`mid = (left + right) // 2`
9	`sq = mid * mid`
11	`if sq == x:`
12	`return mid`
13	`elif sq < x:`
14	`left = mid + 1`
15	`else:`
16	`right = mid - 1`

1	`class Solution:`
2	`def mySqrt(self, x: int) -> int:`
3
4	`left, right = 0, x`
5
6	`while left <= right:`
7
8	`mid = (left + right) // 2`
9	`sq = mid * mid`
10
11	`if sq == x:`
12	`return mid`
13	`elif sq < x:`
14	`left = mid + 1`
15	`else:`
16	`right = mid - 1`
17
18	`return right`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Binary Search Boundaries

Perform Binary Search to Narrow Down Integer Square Root

Return the Floor of the Square Root After Search Completion

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.