0069.Sqrt(x)

Link: 69. Sqrt(x)- Easy
Track: Amazon Tag

Question

Restate

Edge Case

• x = 0, return 0
• x = 1, return 1

---

Method 1 - Binary Search
Method 2

Method 1 - Binary Search

Approach

Binary search on result

Complexity

• Time Complexity: O(logn)
• Space Complexity: O(1)

Code

class Solution:
    def mySqrt(self, x: int) -> int:
        # binary search
        if x < 2:
            return x
 
        left = 1
        right = x // 2
        res = 0
        while left <= right:
            mid = (left + right) // 2
            if mid <= x // mid: # in the correct range
                res = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return res

---

History

• Feb-21-2026 Hinted, forget edge case, (left + right) // 2
• Feb-18-2026 Peeked