Sum of Square Numbers - Video Solutions

Problem Overview: Given a non‑negative integer c, determine whether there exist integers a and b such that a² + b² = c. The task is essentially checking whether the number can be represented as the sum of two perfect squares.

Approach 1: Mathematical Interpretation and Brute Force (O(√c) time, O(1) space)

The direct way is to iterate one value and check whether the remaining value forms a perfect square. Loop a from 0 to sqrt(c). For each value, compute b² = c - a² and check if b² is a perfect square using sqrt() or an integer check. If b * b == b², the equation holds and the answer is true. This works because a cannot exceed √c, which limits the search space significantly. The approach relies heavily on math reasoning about perfect squares and avoids checking every pair of numbers.

Approach 2: Two Pointers (O(√c) time, O(1) space)

This method treats the possible square values like a sorted range and applies the classic two pointers pattern. Initialize left = 0 and right = floor(sqrt(c)). Compute sum = left² + right². If the sum equals c, a valid pair exists. If the sum is smaller, increment left to increase the value. If the sum is larger, decrement right to reduce it. Because squares grow monotonically, this pointer movement systematically explores all combinations without nested loops. The technique mirrors the two‑sum pattern on a sorted array of square values.

Some implementations replace the perfect square check with a binary search on b, but that increases the time complexity to O(√c log c). The two‑pointer approach achieves the same goal with fewer operations and simpler logic.

Recommended for interviews: Start with the mathematical brute force idea to show you recognize the constraint a ≤ √c. Then move to the two‑pointer approach. Interviewers typically expect this optimization because it demonstrates pattern recognition and efficient search on a monotonic range while maintaining constant space.