Want Help Cracking FAANG?

(Then click this)

 ×
Back to Main Page

367. Valid Perfect Square - Leetcode Solution

Leetcode Problem Link Code Solution Link: Github Code Link

πŸ’‘ Step-by-Step Thought Process

  1. Understand the problem: Determine if a given number is a perfect square (i.e., the square of an integer).
  2. Initialize two pointers: left to 1 and right to the input number num.
  3. While left is less than or equal to right, compute the middle point m as the integer average of left and right.
  4. Calculate m_squared as m times m.
  5. If m_squared equals num, return True.
  6. If m_squared is less than num, adjust left to m + 1 to search the right half.
  7. If m_squared is greater than num, adjust right to m - 1 to search the left half.
  8. Return False if no perfect square is found.

Code Solution

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        l = 1
        r = num

        while l <= r:
            m = (l+r) // 2
            m_squared = m * m

            if num == m_squared:
                return True
            elif m_squared < num:
                l = m + 1
            else:
                r = m - 1
        
        return False # Time: O(log n), Space: O(1)

Detailed Explanation

Understanding the Problem: Valid Perfect Square

The β€œValid Perfect Square” problem asks whether a given positive integer num is a perfect square. In other words, we need to determine if there exists an integer x such that x * x == num.

Example:

  • num = 16 β†’ Output: true (since 4 * 4 = 16)
  • num = 14 β†’ Output: false

Why This Problem Matters

This problem helps you practice binary search in a mathematical context, reinforcing how to apply divide-and-conquer techniques outside of traditional array-based problems. It also encourages thinking about precision, overflow, and integer arithmetic.

Optimal Approach: Binary Search Over the Range of Integers

Since the square root of num must lie between 1 and num (inclusive), we can use binary search to check if there exists an integer whose square equals num. Instead of checking every integer sequentially, we divide the range in half with each step.

Steps:

  1. Initialize two pointers: left = 1 and right = num.
  2. While left <= right:
    • Compute the midpoint: mid = Math.floor((left + right) / 2).
    • Calculate mid * mid.
    • If mid * mid == num, return true.
    • If mid * mid < num, the square is too small β†’ move left = mid + 1.
    • If mid * mid > num, the square is too large β†’ move right = mid - 1.
  3. If the loop ends with no match, return false.

Example Walkthrough

Input: num = 25

  • left = 1, right = 25 β†’ mid = 13 β†’ 13Β² = 169 β†’ too big β†’ right = 12
  • mid = 6 β†’ 6Β² = 36 β†’ too big β†’ right = 5
  • mid = 3 β†’ 3Β² = 9 β†’ too small β†’ left = 4
  • mid = 4 β†’ 4Β² = 16 β†’ too small β†’ left = 5
  • mid = 5 β†’ 5Β² = 25 β†’ match found β†’ return true

Time and Space Complexity

Time Complexity: O(log n), because we divide the range of possible answers by 2 in each step.
Space Complexity: O(1), using only constant extra memory.

Edge Cases to Consider

  • num = 1 β†’ should return true
  • num = 0 β†’ problem typically restricts to positive integers, but should handle gracefully
  • Large numbers β†’ avoid integer overflow by using long integers or safe arithmetic in your language

Conclusion

The β€œValid Perfect Square” problem is a great demonstration of how binary search can be applied to numerical properties rather than sorted data structures. This technique is both time-efficient and elegant, making it ideal for problems where brute-force iteration is too slow.

Get Personalized Support at AlgoMap Bootcamp πŸ’‘