How do you solve Sqrt(x) on LeetCode?

Sqrt(x) (LeetCode #69) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(1) space complexity. Key insight: Binary search is a powerful technique for problems involving sorted data or ranges.

What is the brute force solution for Sqrt(x)?

The brute force approach for Sqrt(x) is Brute Force, with O(n) time complexity and O(1) space complexity. The brute force approach involves checking every integer from 0 up to x to see if its square equals x. This is simple but inefficient, especially for large values of x. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Sqrt(x)?

Sqrt(x) uses the following concepts: Math, Binary Search. The recommended patterns to study are: Binary Search, Mathematical Properties.

What are the interview tips for Sqrt(x)?

Always clarify the problem constraints and edge cases before diving into coding. Explain your thought process clearly while coding; it shows your understanding. Practice writing both brute force and optimal solutions to strengthen your problem-solving skills.

What are common mistakes when solving Sqrt(x)?

Not considering edge cases like x = 0 or x = 1. Confusing the conditions for updating left and right pointers in binary search.

#69

Sqrt(x)

Easy

MathBinary SearchBinary SearchMathematical Properties

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(log n)
Space	O(1)	O(1)

💡

Intuition

Time O(log n)Space O(1)

Using binary search allows us to efficiently narrow down the possible range of integers whose squares could equal x. This significantly reduces the number of checks needed.

⚙️

Algorithm

6 steps

1Step 1: Initialize left to 0 and right to x.
2Step 2: While left is less than or equal to right, calculate mid as (left + right) // 2.
3Step 3: If mid * mid equals x, return mid.
4Step 4: If mid * mid is less than x, move left to mid + 1.
5Step 5: If mid * mid is greater than x, move right to mid - 1.
6Step 6: Return right as the integer square root of x.

solution.py11 lines

1def mySqrt(x):
2    left, right = 0, x
3    while left <= right:
4        mid = (left + right) // 2
5        if mid * mid == x:
6            return mid
7        elif mid * mid < x:
8            left = mid + 1
9        else:
10            right = mid - 1
11    return right

ℹ

Complexity note: The time complexity is O(log n) due to the binary search approach, which halves the search space with each iteration. The space complexity is O(1) since we only use a few variables.

1Binary search is a powerful technique for problems involving sorted data or ranges.
2Understanding the properties of squares helps in narrowing down the search space.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.