EasyNo. 0069

Sqrt(x) — LeetCode 69 Python Solution

Topics
Math, Binary Search
On a study list
Top Interview 150
Reading time
2 min

The problem

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

Example

Input
x = 4
Output
2
Explanation
The square root of 4 is 2, so we return 2.

Python solution

PythonSolution
class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x
        while l < r:
            mid = (l + r + 1) >> 1
            if mid > x // mid:
                r = mid - 1
            else:
                l = mid
        return l

Complexity

Time
O(log x)
Space · auxiliary
O(1)

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 69. Sqrt(x) is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0367Valid Perfect SquareEasy
0400Nth DigitMedium
0441Arranging CoinsEasy
0483Smallest Good BaseHard
0497Random Point in Non-overlapping RectanglesMedium
0528Random Pick with WeightMedium

Frequently asked questions

How hard is LeetCode 69. Sqrt(x)?

LeetCode 69. Sqrt(x) is rated Easy on LeetCode.

What is the time complexity of LeetCode 69. Sqrt(x)?

The Python solution on this page runs in O(log x).

What is the space complexity of LeetCode 69. Sqrt(x)?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 69. Sqrt(x) cover?

LeetCode 69. Sqrt(x) is tagged Math and Binary Search on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.