Sqrt(x)

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Find squareroot of a given number without using built-in function

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Can be treated as a sorted array problem

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Binary Search
• Two Pointers

Time & Space Complexity

• Time: $O(logn)$ → Reason: Reducing the search space by half on each iteration
• Space: $O(1)$ → Reason: Not storing anything except pointers

Code

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 1, x
        
        while l <= r:
            m = (l+r) // 2
            if m * m == x:
                return m
            elif m * m > x:
                r = m - 1
            else:
                l = m + 1
        # return l if l * l < x else l - 1
        return r

Common Mistakes / Things I Got Stuck On

• Complicated return statement