How do you solve Valid Perfect Square on LeetCode?

Valid Perfect Square (LeetCode #367) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(1) space complexity. Key insight: Binary search significantly reduces the number of checks needed.

What is the brute force solution for Valid Perfect Square?

The brute force approach for Valid Perfect Square is Brute Force, with O(n²) time complexity and O(1) space complexity. To determine if a number is a perfect square, we can check every integer from 1 up to the number itself, squaring each integer and seeing if it equals the target number. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Valid Perfect Square?

Valid Perfect Square uses the following concepts: Math, Binary Search. The recommended patterns to study are: Binary Search, Mathematical Properties.

What are the interview tips for Valid Perfect Square?

Always clarify the constraints and edge cases before diving into coding. Explain your thought process while coding to demonstrate your understanding. Practice writing both brute-force and optimal solutions to show your problem-solving skills.

What are common mistakes when solving Valid Perfect Square?

Not considering edge cases like 1, which is a perfect square. Confusing the use of integer division and floating-point division.

#367

Valid Perfect Square

Easy

MathBinary SearchBinary SearchMathematical Properties

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log n)
Space	O(1)	O(1)

💡

Intuition

Time O(log n)Space O(1)

Instead of checking every integer, we can use binary search to efficiently find the integer whose square might equal num. This reduces the number of checks significantly.

⚙️

Algorithm

6 steps

1Step 1: Initialize left to 1 and right to num.
2Step 2: While left is less than or equal to right, calculate mid as (left + right) / 2.
3Step 3: If mid * mid equals num, return true.
4Step 4: If mid * mid is less than num, move left to mid + 1.
5Step 5: If mid * mid is greater than num, move right to mid - 1.
6Step 6: If no perfect square is found, return false.

solution.py13 lines

1# Full working Python code
2
3def isPerfectSquare(num):
4    left, right = 1, num
5    while left <= right:
6        mid = (left + right) // 2
7        if mid * mid == num:
8            return True
9        elif mid * mid < num:
10            left = mid + 1
11        else:
12            right = mid - 1
13    return False

ℹ

Complexity note: The time complexity is O(log n) because we are halving the search space with each iteration of the binary search. The space complexity is O(1) as we only use a constant amount of space.

1Binary search significantly reduces the number of checks needed.
2Understanding the properties of perfect squares helps in optimizing the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.