Valid Perfect Square Leetcode Problem 367 [Python Solution]

In this blog post, we’ll tackle the Valid Perfect Square problem, which is LeetCode Problem 367. The task is to determine whether a given positive integer, num, is a perfect square.

A perfect square is an integer that is the square of another integer, meaning it can be expressed as the product of an integer with itself.

For example, 16 is a perfect square because it can be expressed as 4 * 4, which is the square of 4. On the other hand, 14 is not a perfect square because there is no integer whose square is equal to 14. The catch here is that we’re not allowed to use any built-in library functions, such as sqrt, to solve this problem.

Understanding Constraints

The problem specifies the following constraints:

• The input is a positive integer num.
• The input is within the range of 1 to 2^31 – 1. This means we need to come up with an efficient solution that can handle large inputs within this range.

Bruteforce Approach

One way to solve this problem is through a brute force approach.

We can start from 1 and go up to the square root of num, checking if the square of each number equals num.

If we find a match, we return True; otherwise, we return False.

Here’s a Python implementation of this approach:

def isPerfectSquare(num: int) -> bool:
    for i in range(1, num + 1):
        if i * i == num:
            return True
        if i * i > num:
            return False
    return False

This approach has a time complexity of O(√n) because we’re iterating through a range of values from 1 to the square root of num.

It’s a straightforward solution and works well for small inputs.

Efficient Approach with Binary Search

While the brute force approach is acceptable, there’s a more efficient solution using binary search.

Binary search is known for its time complexity of O(log n), which can significantly outperform the square root approach for large inputs.

In the binary search approach, we set the left bound to 1 and the right bound to num.

We then repeatedly calculate the midpoint and check if its square is equal to, greater than, or less than num.

Based on this comparison, we update our search boundaries until we either find the solution or exhaust all possibilities.

def isPerfectSquare(num: int) -> bool:
    left, right = 1, num

    while left <= right:
        mid = (left + right) // 2
        if mid * mid > num:
            right = mid - 1
        elif mid * mid < num:
            left = mid + 1
        else:
            return True

    return False

This binary search approach has a superior time complexity of O(log n) and is a more efficient solution for larger inputs.

Time and Space Complexity

• The brute force approach has a time complexity of O(√n).
• The binary search approach has a time complexity of O(log n).

Both solutions have a space complexity of O(1) because they use a constant amount of extra space.

Reasoning Behind Our Approach

The reasoning behind the efficient binary search approach is that it allows us to eliminate half of the possibilities at each step, making it much faster for large inputs.

By continually adjusting our search boundaries based on whether the midpoint’s square is greater or less than the target number, we approach the solution with fewer iterations.

Related Interview Questions By Company:

• Is Subsequence LeetCode
• Single Number LeetCode
• Word Pattern LeetCode

Related Interview Questions By Difficulty:

• Split Array Largest Sum LeetCode
• Arranging Coins LeetCode
• Squares Of A Sorted Array LeetCode

Related Interview Questions By Category:

• Island Perimeter LeetCode
• Design Browser History LeetCode
• N Queens II LeetCode

Conclusion

In this blog post, we’ve explored two approaches to solving the Valid Perfect Square problem on LeetCode.

We started with a brute force approach that checks for a perfect square by iterating through values from 1 to the square root of the input.

While this approach is straightforward and works for small inputs, we then introduced a more efficient binary search solution.

Binary search significantly reduces the number of iterations required to find a solution and has a time complexity of O(log n), making it ideal for handling large inputs.

If you found this blog post helpful, please consider liking and subscribing.

Your support means a lot to us.

If you have any questions, suggestions, or would like to see more problems solved, please feel free to comment.

Sharing this content with others who might find it useful is also appreciated.

For the original problem and to practice the solutions yourself, check out the Valid Perfect Square problem on LeetCode.

Happy coding!