Watch 10 video solutions for Valid Perfect Square, a easy level problem involving Math, Binary Search. This walkthrough by NeetCode has 44,252 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 - 1Problem 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 | 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 |