Problem Overview

You are given a non-negative integer c.

Your task is to determine whether there exist two integers a and b such that:

a^2+b^2=c

If such integers exist → return true
Otherwise → return false

This problem is frequently asked in interviews because it tests:

• Two Pointers

• Math reasoning

• Optimization

• Search space reduction

Example

Input:

c = 5

Possible values:

1² + 2² = 1 + 4 = 5

Output:

true

Another example:

Input:

c = 3

No possible pair exists:

0² + 1² = 1
1² + 1² = 2

Output:

false

Approach 1: Brute Force

Idea

Try every possible pair (a, b).

For each value of a:

• Try all possible values of b

• Check whether:

a^2+b^2=c

Disadvantages

• Extremely slow

• Time Complexity becomes O(n²)

• Impossible to handle large constraints efficiently

Since:

0 <= c <= 2^31 - 1

Brute force is unacceptable.

Best Approach: Two Pointers

Core Idea

Notice:

• a² increases when a increases

• b² decreases when b decreases

This means we can intelligently search instead of checking all pairs.

Two Pointer Strategy

Start with:

• a = 0

• b = sqrt(c)

Why?

Because:

• Smallest possible square is 0²

• Largest possible square is sqrt(c)²

Now calculate:

sum=a^2+b^2

Then:

• If sum == c
  → we found a valid pair ✅

• If sum < c
  → we need a larger value
  → increase a

• If sum > c
  → we need a smaller value
  → decrease b

This works exactly like binary-style narrowing.

Step-by-Step Example

Input

c = 5

Initialize:

a = 0
b = 2

Because:

sqrt(5) = 2

Iteration 1

sum = 0² + 2² = 4

4 < 5

So we increase a.

a = 1

Iteration 2

sum = 1² + 2² = 5

Found the answer ✅

Return:

true

Why This Works

At every step:

• Increasing a makes the sum bigger

• Decreasing b makes the sum smaller

So we eliminate impossible states efficiently without checking everything.

This gives a very fast solution.

Time and Space Complexity

Time Complexity

O(sqrt(c))

Because each pointer moves at most sqrt(c) times.

Space Complexity

O(1)

No extra data structures are used.

Final Code (Two Pointers)

class Solution {
public:
    bool judgeSquareSum(int c) {
        
        long long a = 0;
        long long b = sqrt(c);

        while (a <= b) {
            long long sum = a*a + b*b;

            if (sum == c) {
                return true;
            }
            else if (sum < c) {
                a++;
            }

            else {
                b--;
            }
        }

        return false;
    }
};

Key Interview Insight 💡

The important observation is:

• The search space is sorted implicitly

• One pointer increases the sum

• The other decreases the sum

That makes the Two Pointers technique the optimal solution for this problem.