What is the time complexity of Valid Perfect Square?

The optimal solution has a time complexity of O(log n).

What data structures are used to solve Valid Perfect Square?

This problem uses Math, Binary Search. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Valid Perfect Square?

Insight 1: Binary search can efficiently find the potential integer root because the range of possible roots is from 1 to num. Insight 2: The square of the potential root can quickly become large, exceeding the integer limit. Thus, it is better to use long datatype in languages like Java and C++ to avoid integer overflow during the multiplication.

Which companies ask LeetCode 367. Valid Perfect Square in interviews?

This problem is frequently asked at LinkedIn, SAP.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Valid Perfect Square - LeetCode 367 Solution

Valid Perfect Square - Complete Solution Guide

Valid Perfect Square is LeetCode problem 367, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 n

Detailed Explanation

The problem asks us to determine if a given positive integer `num` is a perfect square. A perfect square is an integer that can be obtained by squaring another integer. For instance, 16 is a perfect square because 4 * 4 = 16. We need to solve this without using any built-in square root functions.

Solution Approach

The provided solutions employ a binary search algorithm to efficiently search for a potential integer root of the given number. The algorithm narrows down the search space by repeatedly dividing the interval in half. The Python, Java and C++ solutions utilize a standard binary search implementation. The C version instead uses a linear, incremental search.

Step-by-Step Algorithm

Step 1: Initialize `low` to 1 and `high` to `num`. These represent the lower and upper bounds of our search space for the potential integer root.
Step 2: While `low` is less than or equal to `high`, calculate the middle value `mid` as `(low + high) // 2` (or `left + (right - left) / 2` in Java/C++ to prevent potential overflow).
Step 3: Calculate the square of `mid` as `square = mid * mid`.
Step 4: Compare `square` with `num`:
Step 5: If `square` is equal to `num`, then `num` is a perfect square, so return `True`.
Step 6: If `square` is less than `num`, then the potential root is larger, so update `low` to `mid + 1`.
Step 7: If `square` is greater than `num`, then the potential root is smaller, so update `high` to `mid - 1`.
Step 8: If the loop finishes without finding a perfect square (i.e., `low` becomes greater than `high`), then `num` is not a perfect square, so return `False`.

Key Insights

Insight 1: Binary search can efficiently find the potential integer root because the range of possible roots is from 1 to num.
Insight 2: The square of the potential root can quickly become large, exceeding the integer limit. Thus, it is better to use long datatype in languages like Java and C++ to avoid integer overflow during the multiplication.
Insight 3: Integer division (// in Python, division in Java/C++) truncates, so mid can only ever be an integer. This is critical to the approach working.
Insight 4: In the C solution, it uses an incremental search. While easier to understand, it's less efficient than binary search for larger numbers. Using `long long` is essential to avoid overflow.

Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(1)

Topics

This problem involves: Math, Binary Search.

Companies

Asked at: LinkedIn, SAP.

Valid Perfect Square | LeetCode 367

Easy

Math Binary Search

Time: O(log n)Space: O(1)

Solution Code

Available in:

class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 1;
        long right = num;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            if (square == num) {
                return true;
            } else if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 367: Valid Perfect Square - Detailed explanation and solution approaches.

Topics

Math Binary Search

Companies

LinkedInSAP

Stats

Difficulty:Easy

Languages:4

Companies:2

Problem #:367

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Initialize `low` to 1 and `high` to `num`. These represent the lower and upper bounds of our search space for the potential integer root.
2
Step 2: While `low` is less than or equal to `high`, calculate the middle value `mid` as `(low + high) // 2` (or `left + (right - left) / 2` in Java/C++ to prevent potential overflow).
3
Step 3: Calculate the square of `mid` as `square = mid * mid`.
4
Step 4: Compare `square` with `num`:
5
Step 5: If `square` is equal to `num`, then `num` is a perfect square, so return `True`.
6
Step 6: If `square` is less than `num`, then the potential root is larger, so update `low` to `mid + 1`.
7
Step 7: If `square` is greater than `num`, then the potential root is smaller, so update `high` to `mid - 1`.
8
Step 8: If the loop finishes without finding a perfect square (i.e., `low` becomes greater than `high`), then `num` is not a perfect square, so return `False`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log n)

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

Binary search has a logarithmic time complexity due to the halving of the search space. The algorithm uses a fixed number of variables, resulting in constant space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Newton's Method

Newton's method (or Newton-Raphson method) is an iterative method for finding the roots of a real-valued function. We can use it to approximate the square root of the number and then check if the square of the integer part of the approximation equals the original number.

Time: Approximately O(log n), although it can vary depending on the initial guess and desired precision. It often converges faster than binary search in practice.Space: O(1)

Trade-offs: Newton's method can be faster than binary search in some cases, but it might require more careful handling of floating-point precision and convergence conditions.

Incremental Search

Iterate from i = 1 until i * i >= num. If i * i == num, then num is a perfect square. This approach is used in the C solution.

Time: O(sqrt(n)). Linear up to the square root of n.Space: O(1)

Trade-offs: Simpler to understand but less efficient for large numbers than the binary search approach.

✨

Key Insights

1Insight 1: Binary search can efficiently find the potential integer root because the range of possible roots is from 1 to num.
2Insight 2: The square of the potential root can quickly become large, exceeding the integer limit. Thus, it is better to use long datatype in languages like Java and C++ to avoid integer overflow during the multiplication.
3Insight 3: Integer division (// in Python, division in Java/C++) truncates, so mid can only ever be an integer. This is critical to the approach working.
4Insight 4: In the C solution, it uses an incremental search. While easier to understand, it's less efficient than binary search for larger numbers. Using `long long` is essential to avoid overflow.

📚

Key Terms Explained

For Students

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Edge case 1: `num = 1`. The algorithm correctly identifies 1 as a perfect square since the loop will execute with low = 1, high = 1, mid = 1, and square = 1.
Edge case 2: `num` is a large number close to the maximum integer limit. This is where the `long` data type becomes important in Java and C++ to prevent integer overflow when calculating `mid * mid`.
Edge case 3: When `num` is not a perfect square, the algorithm should correctly return `False`. The loop terminates when `low` becomes greater than `high`, indicating that no perfect square was found within the search range.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Using integer multiplication without considering potential overflow, especially when `num` is a large integer. Using a `long` data type in Java and C++ is a simple fix.

✗Common mistake 2: Incorrectly initializing the `low` and `high` pointers in the binary search. `low` should start at 1 (not 0, as 0*0 would always be zero), and `high` should start at `num`.

✗Common mistake 3: Not handling the case where the number is not a perfect square. The loop should terminate correctly and return `False` in such cases.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Image processing. Determining the dimensions of a square image if the number of pixels is known.

🏦Real-world scenario 2: Game development. Calculating distances or performing collision detection, where perfect squares might be involved in simplified calculations.

🎮Real-world scenario 3: Cryptography. In some cryptographic algorithms, checking for perfect squares can be a part of number-theoretic operations.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 8, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

Can binary search be applied to non-sorted arrays?

Binary search requires a monotonic property, not necessarily sorted data. It can be applied to any search space where you can determine if the answer is in the left or right half. Examples include searching rotated arrays or finding minimum in optimization problems.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Valid Perfect Square"?

For this easy-level Math problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether binary search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?