Sum of Square Numbers: Two-Pointer Search for Perfect Squares

Imagine you have a ruler marked with perfect squares: 0, 1, 4, 9, 16, 25... You pick two marks and ask, "Do these two add up to my target number?" That is the core of LeetCode 633: Sum of Square Numbers. Given a non-negative integer c, you need to decide whether there exist two integers a and b such that a * a + b * b = c.

Why this problem matters

Sum of Square Numbers sits at the intersection of two powerful patterns: two-pointer search and mathematical structure. The naive approach would try every pair of values, but the sorted nature of perfect squares lets you apply the same converging two-pointer technique you use on sorted arrays. Recognizing that the candidate values [0, 1, 2, ..., floor(sqrt(c))] form an ordered range is the key insight. Once you see it, the problem reduces to a familiar search.

This pattern also shows up in number theory and competitive programming. Fermat's theorem on sums of two squares gives a purely mathematical answer, but the two-pointer approach is what you want in an interview because it generalizes to other search problems.

The approach

The search space is the range of integers from 0 to floor(sqrt(c)). Any value larger than sqrt(c) would produce a square exceeding c on its own, so it cannot be part of a valid pair.

Place pointer a at 0 (the left end) and pointer b at floor(sqrt(c)) (the right end). Compute a*a + b*b:

• If the sum equals c, you found a valid pair. Return True.
• If the sum is less than c, the current combination is too small. Move a one step right to increase the sum.
• If the sum is greater than c, the current combination is too large. Move b one step left to decrease the sum.

Each step eliminates at least one candidate. The pointers converge toward each other, and the search ends when they meet or cross.

import math

def judgeSquareSum(c):
    a = 0
    b = int(math.isqrt(c))

    while a <= b:
        total = a * a + b * b
        if total == c:
            return True
        elif total < c:
            a += 1
        else:
            b -= 1

    return False

Step-by-step walkthrough

Let's trace through c = 13. The floor of sqrt(13) is 3, so the search range is [0, 3]. The orange pointer is a and the green pointer is b.

The search converges quickly. In three steps, the pointers find that 2*2 + 3*3 = 13. If no pair existed, the pointers would cross (a > b) and the function would return False.

Complexity analysis

Time: O(sqrt(c)). Each step moves one pointer inward. The two pointers start a total of floor(sqrt(c)) positions apart and each step closes the gap by one. At most sqrt(c) steps.

Space: O(1). Only two integer variables (a and b) plus one for the computed sum. No auxiliary data structures.

Edge cases to watch for

• c = 0: 0*0 + 0*0 = 0. The function returns True immediately since a = 0 and b = 0 satisfy the condition.
• c = 1: 0*0 + 1*1 = 1. One step with a = 0, b = 1.
• Perfect square itself: c = 4 works because 0*0 + 2*2 = 4. The pair (0, 2) is valid since the problem allows a = 0.
• Large c values: For c = 2147483647 (a 32-bit max), floor(sqrt(c)) is 46340. The loop runs at most 46340 iterations, which is fast. In Python there is no overflow concern since integers have arbitrary precision, but in languages like Java or C++, be careful that a*a + b*b does not overflow. Use long or check against c - a*a instead.

The building blocks

This problem is built from one core technique.

Two-pointer convergence on an ordered range

You have an ordered set of candidate values and you need to find a pair that satisfies a target condition. Place one pointer at each end. Compare the result of combining the two pointed values against the target. Move the pointer that can improve the outcome.

This same convergence pattern drives:

• Two Sum II: same converging search on a sorted array, looking for a pair that sums to a target
• Container With Most Water: converge from both ends, moving the shorter side inward
• 3Sum: fix one element, then use converging pointers to find the remaining pair

The difference here is that your "array" is implicit. The values are just the integers from 0 to floor(sqrt(c)), and the "lookup" is squaring. But the search logic is identical to any two-pointer problem on sorted data. If you can write Two Sum II from memory, you already know the skeleton for this problem.

From understanding to recall

The code for Sum of Square Numbers is short. Set up two pointers, compare the sum of squares, move one pointer. But the details that matter in an interview are the ones that fade first: why a can equal b, why math.isqrt instead of int(math.sqrt(...)) for precision, how to handle c = 0.

Reading the solution once gives you understanding. Practicing it from scratch at increasing intervals gives you recall. After a few spaced repetitions, the two-pointer-on-squares pattern becomes a brick you own, not a solution you vaguely remember seeing.

Related posts

• Two Sum II - two-pointer search on sorted data
• Valid Perfect Square - binary search for square roots
• Sqrt(x) - computing integer square roots