Problem Description

You are given a non-negative integer c. Your task is to determine whether there exist two integers a and b such that a² + b² = c.

In other words, you need to check if the given number c can be expressed as the sum of two perfect squares. The integers a and b can be any non-negative integers, including zero.

For example:

• If c = 5, the answer is true because 1² + 2² = 1 + 4 = 5
• If c = 3, the answer is false because there are no two integers whose squares sum to 3

The solution uses a two-pointer technique. It starts with a = 0 and b = √c (rounded down to the nearest integer). Then it checks if a² + b² equals c. If the sum is less than c, it increases a. If the sum is greater than c, it decreases b. This process continues until either a valid pair is found or a becomes greater than b, indicating no such pair exists.

Intuition

The key insight is that if c can be expressed as a² + b², then both a and b must be at most √c. Why? Because if either value exceeds √c, then that value squared alone would be greater than c, making it impossible for the sum to equal c.

This gives us a bounded search space: a can range from 0 to √c, and similarly for b. However, checking all possible pairs would be inefficient.

Here's where the two-pointer technique becomes clever. We start with a = 0 (the minimum possible value) and b = √c (the maximum possible value). At each step, we calculate a² + b²:

• If the sum equals c, we've found our answer
• If the sum is less than c, we need to make it larger. Since b is already at its maximum useful value for the current a, we increase a
• If the sum is greater than c, we need to make it smaller, so we decrease b

This approach works because as we adjust the pointers, we systematically explore all potentially valid combinations. The beauty is that we never miss a valid pair - if we skip over some combination, it's because we've already determined it cannot possibly sum to c based on our current bounds.

The algorithm terminates when either we find a valid pair or when a > b, which means we've exhausted all possibilities. The condition a <= b is sufficient because if a valid pair (a, b) exists with a > b, then the pair (b, a) would also be valid and would have been checked earlier when b > a.

Learn more about Math, Two Pointers and Binary Search patterns.

Solution Approach

The implementation uses the two-pointer technique with mathematical bounds to efficiently search for valid pairs.

Step 1: Initialize the pointers

• Set a = 0 as the left pointer (minimum value)
• Set b = int(sqrt(c)) as the right pointer (maximum possible value)

Step 2: Search using two pointers

While a <= b, perform the following:

1. Calculate the sum s = a² + b²

2. Compare s with target value c:

   • If s == c: We've found a valid pair, return True
   • If s < c: The current sum is too small, so increment a by 1 to increase the sum
   • If s > c: The current sum is too large, so decrement b by 1 to decrease the sum

Step 3: Return result

If the loop completes without finding a valid pair (when a > b), return False.

Why this works:

The algorithm systematically explores the solution space by adjusting pointers based on the comparison result. Starting from the extremes (0 and √c), we narrow down the search range:

• When we increase a, we're exploring larger values for the smaller component
• When we decrease b, we're exploring smaller values for the larger component
• The condition a <= b ensures we don't check duplicate pairs (since a² + b² = b² + a²)

Time Complexity: O(√c) - In the worst case, we might need to move the pointers through all values from 0 to √c.

Space Complexity: O(1) - We only use a constant amount of extra space for the two pointers and the sum variable.

Example Walkthrough

Let's walk through the algorithm with c = 13 to see how the two-pointer technique finds that 13 = 2² + 3².

Initial Setup:

• a = 0 (left pointer starts at minimum)
• b = √13 = 3 (right pointer starts at maximum, rounded down)

Iteration 1:

• Calculate: a² + b² = 0² + 3² = 0 + 9 = 9
• Compare: 9 < 13 (sum is too small)
• Action: Increment a to 1

Iteration 2:

• Calculate: a² + b² = 1² + 3² = 1 + 9 = 10
• Compare: 10 < 13 (sum is still too small)
• Action: Increment a to 2

Iteration 3:

• Calculate: a² + b² = 2² + 3² = 4 + 9 = 13
• Compare: 13 == 13 (found exact match!)
• Action: Return True

The algorithm successfully finds that 13 can be expressed as 2² + 3².

Let's also see an example where no solution exists with c = 3:

Initial Setup:

• a = 0 (left pointer)
• b = √3 = 1 (right pointer, rounded down)

Iteration 1:

• Calculate: a² + b² = 0² + 1² = 0 + 1 = 1
• Compare: 1 < 3 (sum is too small)
• Action: Increment a to 1

Iteration 2:

• Calculate: a² + b² = 1² + 1² = 1 + 1 = 2
• Compare: 2 < 3 (sum is still too small)
• Action: Increment a to 2

Check loop condition:

• Now a = 2 and b = 1, so a > b
• Loop terminates, return False

The algorithm correctly determines that 3 cannot be expressed as the sum of two perfect squares.

Solution Implementation

Time and Space Complexity

The time complexity is O(√c), where c is the given non-negative integer. This is because the algorithm uses a two-pointer approach where a starts at 0 and b starts at int(sqrt(c)). In each iteration of the while loop, either a is incremented or b is decremented, moving the pointers closer together. The loop terminates when a > b. Since a can increase from 0 to at most √c and b can decrease from √c to 0, the total number of iterations is bounded by O(√c).

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for the variables a, b, and s, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow When Calculating Squares

The Problem: When calculating left * left + right * right, the intermediate values can cause integer overflow for large values of c. Even though Python handles arbitrary precision integers automatically, in languages like Java or C++, computing a² + b² directly can overflow when c is near the maximum integer value.

Example of the Issue:

# In languages with fixed integer sizes:
# If c = 2^31 - 1 (max int), and right = sqrt(c) ≈ 46340
# Then right * right could overflow before the comparison

Solution: Instead of computing the sum and comparing, rearrange the comparison to avoid overflow:

import math

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left = 0
        right = int(math.sqrt(c))
      
        while left <= right:
            # Avoid direct sum calculation to prevent overflow
            left_square = left * left
            right_square = right * right
          
            # Check if calculation would overflow (for other languages)
            # In Python, we can still use this safer approach
            if left_square > c - right_square:
                right -= 1
            elif left_square < c - right_square:
                left += 1
            else:
                return True
      
        return False

2. Incorrect Square Root Calculation

The Problem: Using floating-point square root without proper conversion to integer can lead to precision errors. For example, sqrt(c) might return a value slightly less than the actual integer square root due to floating-point representation.

Example of the Issue:

# Potential precision issue
import math
c = 4
right = math.sqrt(c)  # Returns 2.0 (float)
# If not handled properly, comparisons might fail

Solution: Always use int(math.sqrt(c)) or math.isqrt(c) (Python 3.8+) for exact integer square root:

import math

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left = 0
        # Use math.isqrt for exact integer square root (Python 3.8+)
        # or int(math.sqrt(c)) for earlier versions
        right = math.isqrt(c) if hasattr(math, 'isqrt') else int(math.sqrt(c))
      
        while left <= right:
            current_sum = left * left + right * right
          
            if current_sum == c:
                return True
            elif current_sum < c:
                left += 1
            else:
                right -= 1
      
        return False

3. Missing Edge Case: c = 0

The Problem: Not handling the special case where c = 0, which should return True since 0² + 0² = 0.

Solution: The current implementation handles this correctly since when c = 0, both left and right start at 0, and 0 + 0 = 0 returns True. However, it's good practice to be aware of this edge case and potentially add an early return for clarity:

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        # Early return for edge case
        if c == 0:
            return True
          
        left = 0
        right = int(math.sqrt(c))
      
        while left <= right:
            current_sum = left * left + right * right
          
            if current_sum == c:
                return True
            elif current_sum < c:
                left += 1
            else:
                right -= 1
      
        return False