58. Valid Perfect Square
🔗 LeetCode Problem: 367. Valid Perfect Square
📊 Difficulty: Easy
🏷️ Topics: Math, Binary Search
Problem Statement
Given a positive integer num, return true if num is a perfect square or false otherwise.
A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.
You must not use any built-in library function, such as sqrt.
Example 1:
Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.
Example 2:
Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.
Constraints:
- 1 <= num <= 2^31 - 1
🎨 Visual Understanding
The Problem Visualized
Perfect Squares:
1 = 1²
4 = 2²
9 = 3²
16 = 4²
25 = 5²
36 = 6²
...
Non-Perfect Squares:
2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, ...
Example: num = 16
Check: Is there an integer k such that k² = 16?
Try k = 1: 1² = 1 ≠ 16
Try k = 2: 2² = 4 ≠ 16
Try k = 3: 3² = 9 ≠ 16
Try k = 4: 4² = 16 ✓ MATCH!
Answer: true
Example: num = 14
Check: Is there an integer k such that k² = 14?
Try k = 3: 3² = 9 < 14
Try k = 4: 4² = 16 > 14
No exact match between 3 and 4
Answer: false
🚨 CRITICAL INSIGHT - Why Binary Search Works
The Key Pattern!
We need to find if there EXISTS an integer k where k² = num
Think of the search space:
Numbers: 0 1 2 3 4 5 6 7 8 9 10
Squares: 0 1 4 9 16 25 36 49 64 81 100
For num = 16:
0² = 0 < 16
1² = 1 < 16
2² = 4 < 16
3² = 9 < 16
4² = 16 = 16 ✓ FOUND!
5² = 25 > 16
...
Pattern: [< < < < = > > > ...]
[Too Small | Match | Too Large]
This is SORTED and MONOTONIC!
= Perfect for Binary Search!
Why This is Binary Search on Answer Space
Search Space:
Range [0, num] for potential square root
Each candidate k has a property:
k² < num (too small)
k² = num (perfect match!) ✓
k² > num (too large)
The Goal:
Find if ANY k exists where k² = num
= Search for EXACT match
= Classic Binary Search!
Key Insight:
If k² < num, try larger k (search right)
If k² > num, try smaller k (search left)
If k² = num, found it! ✓
Can eliminate half at each step!
Example: num = 16, range [0, 16]
Check mid = 8:
8² = 64 > 16
Too large, search left [0, 7]
Check mid = 3:
3² = 9 < 16
Too small, search right [4, 7]
Check mid = 5:
5² = 25 > 16
Too large, search left [4, 4]
Check mid = 4:
4² = 16 = 16 ✓
Perfect square! Return true
Connection to Sqrt(x) Problem
Valid Perfect Square vs Sqrt(x):
Sqrt(x):
Find: floor(√num)
Return: largest k where k² ≤ num
Always returns a value
Valid Perfect Square:
Find: does √num exist as integer?
Check: does k² = num for some k?
Returns: true/false
They're related:
num is perfect square IF floor(√num)² = num
But binary search approach differs slightly:
Sqrt: Track best, search for larger
Perfect Square: Search for exact match
🎯 Approach 1: Linear Search (Brute Force)
The Most Natural Thinking 💭
Core Logic:
Start from 1 and check each number:
If i² = num, return true
If i² > num, return false (won't find it beyond this)
Implementation
public boolean isPerfectSquare(int num) {
if (num == 1) return true; // 1 is a perfect square
// Check each number starting from 1
for (long i = 1; i <= num; i++) {
long square = i * i;
if (square == num) {
return true; // Found perfect square
}
if (square > num) {
return false; // Exceeded num, won't find it
}
}
return false; // Should never reach here
}
⏰ Time: O(√num) - Check up to √num numbers
💾 Space: O(1) - Only variables
Why This Works:
We check 1², 2², 3², ... until we find match or exceed num
Since squares grow quickly, this is at most √num iterations
❌ Problem: Too slow for large num! If num = 2^31-1, too many checks!
🎯 Approach 2: Binary Search (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
The search space is SORTED:
1² < 2² < 3² < 4² < ...
We're looking for EXACT match:
k² = num
This is classic binary search:
If k² < num: search right
If k² > num: search left
If k² = num: found it!
The Strategy:
Binary search on range [1, num]:
Calculate mid²:
If mid² = num: Perfect square! Return true
If mid² < num: Search right half
If mid² > num: Search left half
If loop ends without finding: Return false
Implementation
public boolean isPerfectSquare(int num) {
if (num == 1) return true; // Edge case
long left = 1;
long right = num;
while (left <= right) {
long mid = left + (right - left) / 2;
long square = mid * mid; // Use long to avoid overflow
if (square == num) {
return true; // Perfect square found!
}
if (square < num) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return false; // No perfect square root found
}
⏰ Time: O(log num) - Binary search
💾 Space: O(1) - Only variables
🔍 Dry Run
Example 1: num = 16
Goal: Find if there exists k where k² = 16
Initial: left = 1, right = 16
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
↑ ↑
left right
Iteration 1:
mid = 1 + (16 - 1) / 2 = 8
square = 8 × 8 = 64
64 > 16, too large
right = 7
[1, 2, 3, 4, 5, 6, 7, 8, 9, ...]
↑ ↑
left right
Iteration 2:
mid = 1 + (7 - 1) / 2 = 4
square = 4 × 4 = 16
16 == 16 ✓
return true
Answer: true ✓
Example 2: num = 14
Goal: Find if there exists k where k² = 14
Initial: left = 1, right = 14
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
↑ ↑
left right
Iteration 1:
mid = 1 + (14 - 1) / 2 = 7
square = 7 × 7 = 49
49 > 14, too large
right = 6
[1, 2, 3, 4, 5, 6, 7, ...]
↑ ↑
left right
Iteration 2:
mid = 1 + (6 - 1) / 2 = 3
square = 3 × 3 = 9
9 < 14, too small
left = 4
[1, 2, 3, 4, 5, 6, 7, ...]
↑ ↑
left right
Iteration 3:
mid = 4 + (6 - 4) / 2 = 5
square = 5 × 5 = 25
25 > 14, too large
right = 4
[1, 2, 3, 4, 5, 6, 7, ...]
↑
left/right
Iteration 4:
mid = 4 + (4 - 4) / 2 = 4
square = 4 × 4 = 16
16 > 14, too large
right = 3
[1, 2, 3, 4, 5, 6, 7, ...]
↑ ↑
right left
Loop ends (left > right)
return false
Answer: false ✓
No integer k exists where k² = 14
Example 3: num = 1
Edge case: num == 1
return true ✓
1 = 1² (perfect square)
Example 4: num = 25
Initial: left = 1, right = 25
Iteration 1:
mid = 13
square = 169 > 25
right = 12
Iteration 2:
mid = 6
square = 36 > 25
right = 5
Iteration 3:
mid = 3
square = 9 < 25
left = 4
Iteration 4:
mid = 4
square = 16 < 25
left = 5
Iteration 5:
mid = 5
square = 25 = 25 ✓
return true
Answer: true ✓
🎯 Why This Works - Deep Dive
The Search Space:
═══════════════════════════════════════════════════════════════
Range: [1, num]
Can we optimize?
Yes! For num > 4, √num < num/2
So we could search [1, num/2]
But optimization is minor:
Binary search on [1, num] is already O(log num)
Binary search on [1, num/2] is O(log num/2) ≈ O(log num)
For simplicity, use [1, num]
The Three Cases:
═══════════════════════════════════════════════════════════════
1. mid² = num: FOUND! Return true immediately
2. mid² < num: Answer is to the right (larger k)
3. mid² > num: Answer is to the left (smaller k)
Loop Termination:
═══════════════════════════════════════════════════════════════
Standard binary search: left <= right
When loop ends (left > right):
We've checked all candidates
No exact match found
Return false
Unlike Sqrt(x):
Sqrt: Always has answer (floor)
Perfect Square: Might not have answer (false)
Overflow Prevention:
═══════════════════════════════════════════════════════════════
Critical: Use long for mid and square
Why?
num can be up to 2^31 - 1
mid can be up to num
mid × mid can overflow int range
Example:
num = 2,147,395,600
mid = 46,340
mid × mid as int: OVERFLOW!
mid × mid as long: Correct ✓
Use long for both mid and square!
Comparison with Sqrt(x)
Sqrt(x) Problem:
═══════════════════════════════════════════════════════════════
Goal: Find floor(√num)
Return: Integer (always)
Logic: Track best valid, search for larger
Loop: while (left <= right)
When valid: result = mid, left = mid + 1
Return: result
Valid Perfect Square:
═══════════════════════════════════════════════════════════════
Goal: Check if √num is integer
Return: Boolean (true/false)
Logic: Search for exact match
Loop: while (left <= right)
When match: return true immediately
Return: false if no match
Both use binary search, but:
Sqrt tracks best approximation
Perfect Square searches exact match
⚠️ Common Mistakes to Avoid
Mistake 1: Not using long
// ❌ WRONG - Integer overflow
int mid = (left + right) / 2;
int square = mid * mid;
if (square == num) { ... }
// ✓ CORRECT - Use long
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square == num) { ... }
Why it's critical:
For num near 2^31:
mid can be ~46340
mid * mid as int: OVERFLOW (negative!)
Comparison breaks completely!
Use long throughout:
long mid, long square
Prevents all overflow issues ✓
Mistake 2: Using Math.sqrt()
// ❌ WRONG - Problem says not to use library
double root = Math.sqrt(num);
return (int) root * (int) root == num;
// ✓ CORRECT - Binary search
// (Our solution)
Mistake 3: Wrong range
// ❌ WRONG - Misses edge case
long left = 2; // Should be 1
long right = num;
// ✓ CORRECT
long left = 1; // Handles num = 1
Mistake 4: Not handling num = 1
// ❌ WRONG - Fails for num = 1
long left = 2; // Skips 1!
// ✓ CORRECT - Special case or start from 1
if (num == 1) return true;
long left = 1;
Mistake 5: Inefficient optimization
// ⚠️ UNNECESSARY COMPLEXITY
if (num < 2) return true;
long right = num / 2; // Optimize upper bound
// ✓ SIMPLER - Binary search is fast anyway
long right = num; // Simple and works
🎯 Pattern Recognition
Problem Type: Binary Search - Mathematical/Exact Match
Core Pattern: Search for Exact Value in Monotonic Space
When to Apply:
✓ Mathematical computation without library
✓ Looking for EXACT match (not approximate)
✓ Monotonic property: values increase/decrease
✓ Can check if candidate is valid
✓ Need O(log n) time
Recognition Keywords:
- "Perfect square"
- "Product of integer with itself"
- "Must not use built-in"
- Boolean return (true/false)
- Exact match required
Similar Problems:
- Sqrt(x) (LC 69) - Related but finds floor
- Pow(x, n) (LC 50) - Binary search for power
- First Bad Version (LC 278) - Find transition
- Guess Number Higher or Lower (LC 374)
Key Difference from Sqrt(x):
┌────────────────────────────────────────────┐
│ Sqrt(x): │
│ - Returns floor(√num) │
│ - Always has answer │
│ - Tracks best approximation │
│ │
│ Valid Perfect Square (This Problem): │
│ - Returns true/false │
│ - Might not have answer │
│ - Searches for exact match │
└────────────────────────────────────────────┘
Search for exact, not approximate!
🧠 Interview Strategy
Step 1: "Need to check if num = k² for some integer k"
Step 2: "Binary search on range [1, num]"
Step 3: "Search for EXACT match (not approximate)"
Step 4: "If found, return true. If loop ends, return false"
Step 5: "Use long to prevent overflow"
Key Points to Mention:
- Binary search on RANGE, not array
- Looking for EXACT match
- Three cases: equal, less than, greater than
- Return true immediately when found
- Return false if loop ends (no match)
- Use long for mid and square (overflow)
- Handle edge case num = 1
- Time: O(log num), Space: O(1)
- Can't use Math.sqrt()
Why This Approach?
"I need to check if there's an integer whose square equals num.
The search space [1, num] has the property that squares are
monotonically increasing, making it perfect for binary search.
I'm looking for an exact match, not an approximation. If I find
a candidate where mid squared equals num, I return true immediately.
If the binary search completes without finding a match, I return
false. The critical detail is using long to prevent overflow when
calculating mid squared for large values."
Overflow Handling:
"When num is large, mid can be around 46000. Squaring this overflows
integer range. So I use long for both mid and square to safely handle
values up to 2^31 - 1."
Difference from Sqrt:
"Unlike finding the square root where we track the best approximation,
here we're looking for an EXACT match. Either a perfect square root
exists, or it doesn't. So we can return as soon as we find a match,
or return false if we exhaust the search space."
📝 Quick Revision Notes
🎯 Core Concept:
Valid Perfect Square: Check if num = k² for some integer k using binary search on range [1, num]. Search for EXACT match. When match found: return true. When loop ends: return false. Critical: Use long for overflow!
⚡ Quick Implementation:
class Test {
public boolean isPerfectSquare(int x) {
int left = 0; // since in question, 0 is also in range of inputs
int right = x;
while (left <= right) {
int mid = left + (right - left) / 2;
long product = (long) mid * mid;
if(product == x) {
return true;
} else if(product < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(t.isPerfectSquare(16));
System.out.println(t.isPerfectSquare(14));
}
}
🔑 Key Insights:
- Pattern: Binary Search - Exact Match
- Goal: Check if k² = num for some k
- Monotonic: 1² < 2² < 3² < ... (sorted)
- Three Cases: =, <, > (standard BS)
- Return True: When exact match found
- Return False: When loop ends (no match)
- Overflow: Use
long midandlong square← CRITICAL! - Edge Case: num = 1 handled separately
- Loop:
left <= right(standard BS) - Time: O(log num), Space: O(1)
🎪 Memory Aid:
"Search for EXACT, use LONG for the test!"
Think: "k² = num? Binary search says YES or NO!"
💡 The Key Insight:
When mid² = num:
return true (found it!)
When mid² < num:
left = mid + 1 (search right)
When mid² > num:
right = mid - 1 (search left)
Loop ends:
return false (no match)
⚠️ Critical Details:
1. Edge case: if (num == 1) return true
2. Use long: long left, long right, long mid
3. Overflow: long square = mid * mid
4. Exact: if (square == num) return true
5. Loop: while (left <= right)
6. Default: return false after loop
🔥 The Overflow Issue:
For num near 2^31:
mid can be ~46340
mid × mid as int: OVERFLOW!
mid × mid as long: Correct ✓
Example:
mid = 46341
As int: mid * mid = negative (overflow!)
As long: mid * mid = 2,147,488,281 ✓
Solution: Use long everywhere!
long left, long right, long mid, long square
🎯 Difference from Sqrt(x):
Sqrt(x):
Goal: Find floor(√num)
Track best valid answer
When valid: result = mid, search right
Return: result (always has value)
Valid Perfect Square:
Goal: Check if √num is integer
Search for exact match
When match: return true immediately
Return: false if no match
Both: Use binary search, handle overflow
Sqrt: Approximation (floor)
Perfect: Exact match (true/false)
💡 Quick Check:
Perfect square if: k² = num for integer k
Examples:
16 = 4² ✓ true
14 ≠ k² for any integer k ✗ false
25 = 5² ✓ true
26 ≠ k² for any integer k ✗ false
🧪 Edge Cases
Case 1: num = 1
Input: 1
Output: true
1 = 1²
Case 2: Small perfect square
Input: num = 4
Output: true
4 = 2²
Case 3: Small non-perfect square
Input: num = 5
Output: false
2² = 4 < 5, 3² = 9 > 5
Case 4: Large perfect square
Input: num = 2147395600
Output: true
46340² = 2147395600
Case 5: Large non-perfect square
Input: num = 2147483647 (2^31 - 1)
Output: false
46340² < 2147483647 < 46341²
Case 6: Another perfect square
Input: num = 100
Output: true
10² = 100
All handled correctly with long! ✓
🎓 Mathematical Insight
Perfect Squares Pattern:
═══════════════════════════════════════════════════════════════
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
1² 2² 3² 4² 5² 6² 7² 8² 9² 10²
Gaps between consecutive perfect squares:
4 - 1 = 3
9 - 4 = 5
16 - 9 = 7
25 - 16 = 9
...
Gaps increase by 2 each time!
This is why linear search is O(√n):
Only √n perfect squares ≤ n
And why binary search is O(log n):
Search space shrinks exponentially
Related Patterns
- Sqrt(x) (LC 69) - Finds floor instead of checking exact
- Pow(x, n) (LC 50) - Binary search for exponentiation
- First Bad Version (LC 278) - Find transition point
- Guess Number Higher or Lower (LC 374) - Similar search
Happy practicing! 🎯
Note: This is a variation of the Sqrt(x) problem, but looking for exact match instead of floor! The overflow prevention is the key detail!