Back to main article
LC 69 Last True Easy

Sqrt(x)

Find the largest integer whose square does not exceed x. The Last True pattern — condition is true for small values and flips false for large ones.

Problem

What are we solving?

Problem Statement

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. You must not use any built-in exponent or sqrt functions. Must run in O(log x).

Example 1 — perfect square
Input:x = 4
Output:2
Example 2 — floor result
Input:x = 8
Output:2  (since √8 ≈ 2.82, floor = 2)
Intuition

Last True: find the largest valid candidate

The condition mid * mid <= x is true for small values of mid and false for large values. This is the reverse of First True — the boolean pattern is T T T T F F F and we want the last T.

x = 8 · search space: mid = 1 to 8
condition: mid² <= 8
1²=1T
2²=4T*
3²=9F
4²=16F
5²=25F
6²=36F
7²=49F
8²=64F
Last T = mid 2 (2²=4 ≤ 8, 3²=9 > 8). Floor of √8 is 2. ✓

Last True vs First True: in First True when the condition is true we move the right pointer left to find an earlier true. In Last True when the condition is true we move the left pointer right to find a later true. The boundary variable always saves the current best answer.

!

Overflow danger in Java: mid * mid can overflow int when x is close to Integer.MAX_VALUE (~2.1 billion). Cast mid to long before squaring. In Python, integers have arbitrary precision so this is never an issue.

Step-by-step walkthrough

x = 8, answer = 2

1
left=1, right=8 → mid=4, 4²=16

16 <= 8? No → condition FALSE. Go left: right=3.

2
left=1, right=3 → mid=2, 2²=4

4 <= 8? Yes → condition TRUE. Save boundary=2, go right: left=3.

3
left=3, right=3 → mid=3, 3²=9

9 <= 8? No → condition FALSE. Go left: right=2.

4
left=3 > right=2 → loop ends

Return boundary=2. ✓

Solution

Clean implementation

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;

        int left = 1, right = x, boundary = 1;

        while (left <= right) {
            long mid = left + (long)(right - left) / 2; // long to avoid overflow

            if (mid * mid <= x) {
                // condition TRUE: valid floor sqrt — save and search right for larger
                boundary = (int) mid;
                left = (int) mid + 1;
            } else {
                // condition FALSE: too large, go left
                right = (int) mid - 1;
            }
        }

        return boundary;
    }
}
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0

        left, right, boundary = 1, x, 1

        while left <= right:
            mid = left + (right - left) // 2

            if mid * mid <= x:
                # condition TRUE: valid — save and search right for larger
                boundary = mid
                left = mid + 1
            else:
                # condition FALSE: too large, go left
                right = mid - 1

        return boundary

Complexity

Time
O(log x)
Binary search over the range 1 to x.
Space
O(1)
Three integer/long variables. No extra structures.
→

Last True template difference from First True: The only change is the direction we move when the condition is true. First True: right = mid - 1. Last True: left = mid + 1. Everything else — the loop condition, the boundary variable, the false branch — is identical.

↑ Pattern map