Valid Perfect Square solution and explanation
Google
9 more videos on this problem
Valid Perfect Square - Leetcode 367 - PythonNeetCode · 8:44 · 45K views
Valid Perfect Square | Leetcode #367Techdose · 9:00 · 16K views
Valid Perfect Square - Leetcode 367 - Binary Search (Python)Greg Hogg · 7:30 · 9K views
Valid Perfect Square | LeetCode 367 | Coding Interview TutorialTerrible Whiteboard · 8:12 · 3K views
Valid Perfect Square (LeetCode 367) | Binary Search and Mathematical Sequence | FunNikhil Lohia · 13:50 · 2K views
367. Valid Perfect Square | Binary Search Series | Leetcode Easy | LEETCODEcode Explainer · 6:45 · 2K views
Leetcode 367. Valid Perfect Square [Java]if else statement · 3:00 · 1K views
Valid Perfect Square | Leetcode 367 PythonPersistent Programmer · 8:35 · 1K views
367 Valid Perfect Square LeetCode (Google Interview Question) JavaScriptdev alex · 5:33 · 862 views
Leetcode 367 Valid Perfect Square (Java) - BINARY SEARCHTheAnalyticGuy · 4:28 · 824 views
The problem
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 <= 231 - 1
Approach overview
Problem Overview: You receive a positive integer num. The task is to determine whether it is a perfect square without calling built-in square root functions such as sqrt(). A number is a perfect square if some integer x satisfies x * x = num.
Approach 1: Binary Search (O(log n) time, O(1) space)
This problem fits naturally with binary search. Any perfect square x² that equals num must have x between 1 and num. Search this range and repeatedly test the midpoint. Compute mid * mid and compare it with num. If the square is equal, you found the integer root. If it is smaller, move the left boundary to mid + 1. If it is larger, move the right boundary to mid - 1. Each iteration cuts the search range in half, which gives O(log n) time complexity. The algorithm stores only a few integer variables, so the space complexity stays O(1). This approach is reliable and avoids floating-point precision issues.
Careful handling of multiplication prevents overflow in languages with fixed integer sizes. Using mid <= num / mid instead of mid * mid <= num avoids exceeding integer limits in C++ or Java. This pattern appears frequently in integer square root problems and is common in interview settings when math constraints are involved.
Approach 2: Newton's Iteration Method (O(log n) time, O(1) space)
Newton's method computes square roots using iterative approximation. Start with an initial guess x = num. Repeatedly update it using the formula x = (x + num / x) / 2. Each iteration rapidly converges toward the integer square root. Stop when x * x <= num. If the final value squared equals num, the number is a perfect square.
The key advantage is fast convergence. Newton's method reduces the error exponentially, so the number of iterations is roughly O(log n) but usually much smaller in practice. The algorithm uses only integer variables, keeping space complexity at O(1). This method is common in numerical computing and sometimes appears in interviews that test deeper math intuition.
Recommended for interviews: Binary search is the most expected solution. It demonstrates control over search boundaries, integer overflow handling, and logarithmic reasoning. Newton's method is an excellent follow-up optimization that shows mathematical insight. Many candidates first present binary search to establish correctness, then discuss Newton's iteration as a faster numerical approach.
Approach 1: Binary Search Approach
The binary search method utilizes the principle that for a number n to be a perfect square, there exists an integer x such that x * x = n. By searching between 1 and n, binary search will narrow down the possibilities by checking the middle value, squaring it, and adjusting the search range based on whether the squared value is less than, greater than, or equal to n. This ensures a time complexity of O(log n).
class Solution:
def isPerfectSquare(self, num: int) -> bool:
left, right = 1, num
while left <= right:
mid = left + (right - left) // 2
square = mid * mid
if square == num:
return True
elif square < num:
left = mid + 1
else:
right = mid - 1
return Falseclass Solution {
public boolean isPerfectSquare(int num) {
long left = 1, right = num;
while (left <= right) {
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square == num) return true;
if (square < num) left = mid + 1;
else right = mid - 1;
}
return false;
}
}class Solution {
public:
bool isPerfectSquare(int num) {
long left = 1, right = num;
while (left <= right) {
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square == num) return true;
if (square < num) left = mid + 1;
else right = mid - 1;
}
return false;
}
};var isPerfectSquare = function(num) {
let left = 1, right = num;
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
let square = mid * mid;
if (square === num) return true;
if (square < num) left = mid + 1;
else right = mid - 1;
}
return false;
};#include <stdbool.h>
bool isPerfectSquare(int num) {
int left = 1, right = num;
while (left <= right) {
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square == num) return true;
if (square < num) left = mid + 1;
else right = mid - 1;
}
return false;
}public class Solution {
public bool IsPerfectSquare(int num) {
long left = 1, right = num;
while (left <= right) {
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square == num) return true;
if (square < num) left = mid + 1;
else right = mid - 1;
}
return false;
}
}Using Python, the integer division is applied to find the mid-point, comparing squares to adjust the search interval efficaciously.
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 2: Newton's Iteration Method
Newton's method is an iterative numerical approach to approximate solutions to functions. For finding a square root, the function is designed around n = x^2. By iteratively refining the guess x using x = (x + n/x) / 2, the method converges to an integer square root if one exists. This method can be faster than binary search with careful tuning.
class Solution:
def isPerfectSquare(self, num: int) -> bool:
if num < 2:
return True
x = num // 2
while x * x > num:
x = (x + num // x) // 2
return x * x == numclass Solution {
public boolean isPerfectSquare(int num) {
if (num < 2) return true;
long x = num / 2;
while (x * x > num) {
x = (x + num / x) / 2;
}
return x * x == num;
}
}class Solution {
public:
bool isPerfectSquare(int num) {
if (num < 2) return true;
long x = num / 2;
while (x * x > num) {
x = (x + num / x) / 2;
}
return x * x == num;
}
};var isPerfectSquare = function(num) {
if (num < 2) return true;
let x = Math.floor(num / 2);
while (x * x > num) {
x = Math.floor((x + num / x) / 2);
}
return x * x === num;
};#include <stdbool.h>
bool isPerfectSquare(int num) {
if (num < 2) return true;
long x = num / 2;
while (x * x > num) {
x = (x + num / x) / 2;
}
return x * x == num;
}public class Solution {
public bool IsPerfectSquare(int num) {
if (num < 2) return true;
long x = num / 2;
while (x * x > num) {
x = (x + num / x) / 2;
}
return x * x == num;
}
}Python simplifies the math calculations maintaining precision, iterate refining guesses to converge to a square root integer if existant via Newton's formula.
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 3: Binary Search
We can use binary search to solve this problem. Define the left boundary l = 1 and the right boundary r = num of the binary search, then find the smallest integer x that satisfies x^2 geq num in the range [l, r]. Finally, if x^2 = num, then num is a perfect square.
The time complexity is O(log n), where n is the given number. The space complexity is O(1).
function isPerfectSquare(num: number): boolean {
let [l, r] = [1, num];
while (l < r) {
const mid = (l + r) >> 1;
if (mid >= num / mid) {
r = mid;
} else {
l = mid + 1;
}
}
return l * l === num;
}func isPerfectSquare(num int) bool {
l := sort.Search(num, func(i int) bool { return i*i >= num })
return l*l == num
}impl Solution {
pub fn is_perfect_square(num: i32) -> bool {
let mut l = 1;
let mut r = num as i64;
while l < r {
let mid = (l + r) / 2;
if mid * mid >= (num as i64) {
r = mid;
} else {
l = mid + 1;
}
}
l * l == (num as i64)
}
}Approach 4: Mathematics
Since 1 + 3 + 5 + cdots + (2n - 1) = n^2, we can gradually subtract 1, 3, 5, cdots from num. If num finally equals 0, then num is a perfect square.
The time complexity is O(\sqrt n), and the space complexity is O(1).
function isPerfectSquare(num: number): boolean {
let i = 1;
while (num > 0) {
num -= i;
i += 2;
}
return num === 0;
}func isPerfectSquare(num int) bool {
for i := 1; num > 0; i += 2 {
num -= i
}
return num == 0
}impl Solution {
pub fn is_perfect_square(mut num: i32) -> bool {
let mut i = 1;
while num > 0 {
num -= i;
i += 2;
}
num == 0
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time Complexity: O(log n) |
| Newton's Iteration Method | Time Complexity: O(log n) |
| Binary Search | – |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search | O(log n) | O(1) | General case when checking if an integer square root exists without using built-in functions |
| Newton's Iteration Method | O(log n) | O(1) | When you want faster convergence and a math-based optimization for square root calculation |
Frequently asked questions
Is Valid Perfect Square easy or hard?
Valid Perfect Square is classified as an Easy problem on LeetCode with an acceptance rate around 45%. The challenge is recognizing that binary search can be applied to integers even when the input is not an array.
How to solve Valid Perfect Square in O(log n)?
Use binary search on the range from 1 to num. Compute mid * mid and compare it with num to decide whether to move left or right in the search range. If a value squared equals num, it is a perfect square. This halves the search space every step, producing O(log n) time complexity.
What is the best approach for Valid Perfect Square?
Binary Search is the most common approach. It searches the possible integer root range and checks whether mid * mid equals the given number. The method runs in O(log n) time and O(1) space and avoids floating point precision issues. Newton's Iteration is another efficient alternative but appears less frequently in interviews.
What data structure is used in Valid Perfect Square?
No complex data structure is required. The problem relies mainly on mathematical reasoning and the binary search algorithm. A few integer variables track the search boundaries and midpoint.
What is the time complexity of Valid Perfect Square?
The optimal solutions run in O(log n) time. Binary Search halves the search space each iteration while Newton's Method rapidly converges to the square root approximation. Both approaches use constant O(1) extra space.
Valid Perfect Square Python or Java solution approach?
Both Python and Java implementations typically use binary search. The algorithm repeatedly checks mid * mid against the target number while adjusting the search range. Some implementations use num / mid instead of mid * mid to prevent integer overflow in Java.
Is Valid Perfect Square asked at Google, Amazon, or Meta?
This problem appears in interview preparation lists for companies such as Google, Amazon, and Microsoft because it tests binary search reasoning and integer overflow handling. Variants of integer square root and perfect square validation frequently appear in technical screens.