LeetCode 633 - Sum of Square Numbers

The problem gives a non-negative integer c and asks whether it can be represented as the sum of the squares of two integers.

leetcodemediummathtwo-pointersbinary-search

LeetCode Problem 633

Difficulty: 🟡 Medium
Topics: Math, Two Pointers, Binary Search

Solution

Problem Understanding

The problem gives a non-negative integer c and asks whether it can be represented as the sum of the squares of two integers.

In mathematical terms, we need to determine whether there exist integers a and b such that:

$a^2 + b^2 = c$

The integers a and b can be zero, and they do not need to be distinct. The task is only to determine whether at least one valid pair exists.

The input consists of a single integer c. The output is a boolean value:

  • true if such integers exist
  • false otherwise

The constraint is important:

0 <= c <= 2^31 - 1

This means the value of c can be as large as about 2.1 billion. A naive approach that checks too many combinations will become too slow. We need an algorithm that scales efficiently for large values.

Several edge cases are important immediately:

  • c = 0, because 0^2 + 0^2 = 0
  • Perfect squares such as 1, 4, or 9, because one number may be zero
  • Small values like 2 and 3, where only limited combinations exist
  • Very large integers near the upper constraint, where overflow or inefficient iteration could become problematic

The problem guarantees that the input is a valid non-negative integer, so we do not need to handle invalid or negative input cases.

Approaches

Brute Force Approach

The most direct approach is to try every possible pair (a, b) and check whether:

$a^2 + b^2 = c$

Since both squares must be less than or equal to c, both a and b only need to range from 0 to sqrt(c).

A brute-force algorithm would use two nested loops:

  • The outer loop chooses a
  • The inner loop chooses b
  • For each pair, compute a*a + b*b
  • Return true if the sum equals c

This approach is correct because it exhaustively checks every possible valid pair.

However, the performance is poor. If sqrt(c) is roughly 46340, then the nested loops may perform over two billion iterations in the worst case. That is far too slow for the problem constraints.

Key Insight for an Optimal Solution

The important observation is that the sum changes predictably as the two numbers move.

Suppose we choose:

  • left = 0
  • right = floor(sqrt(c))

Then:

  • left^2 + right^2 is the largest possible sum using the current right
  • If the sum is too small, we must increase it by moving left upward
  • If the sum is too large, we must decrease it by moving right downward

This monotonic behavior makes the two-pointer technique possible.

Instead of checking all pairs independently, we intelligently eliminate impossible ranges after each comparison. Each pointer moves at most sqrt(c) times, producing a much more efficient algorithm.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(c) O(1) Checks every pair of possible values
Optimal Two Pointers O(sqrt(c)) O(1) Uses monotonic movement to eliminate impossible pairs efficiently

Algorithm Walkthrough

Optimal Two-Pointer Algorithm

  1. Initialize two pointers.

Set left = 0 and right = floor(sqrt(c)).

The left pointer represents the smaller number, while right represents the larger number. Starting this way ensures every possible valid pair lies within the search range. 2. Compute the current sum of squares.

At each iteration, calculate:

$left^2 + right^2$

This tells us whether the current pair matches the target value c. 3. Check whether the sum equals c.

If the sum equals c, we have found integers satisfying the equation, so return true. 4. Handle the case where the sum is too small.

If the sum is less than c, increasing left is the only way to make the sum larger.

Moving right downward would only decrease the sum further. 5. Handle the case where the sum is too large.

If the sum is greater than c, decreasing right is the only way to reduce the sum.

Increasing left would only make the sum even larger. 6. Continue until the pointers cross.

The search ends when left > right.

At that point, every possible pair has been considered or ruled out, so return false.

Why It Works

The algorithm works because the search space is ordered.

For a fixed right, increasing left always increases the sum. Similarly, for a fixed left, decreasing right always decreases the sum.

At every step, the algorithm removes combinations that can never lead to a valid answer. Since no valid pair is skipped, the algorithm is guaranteed to find a solution if one exists.

Python Solution

import math

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left = 0
        right = int(math.isqrt(c))

        while left <= right:
            current_sum = left * left + right * right

            if current_sum == c:
                return True

            if current_sum < c:
                left += 1
            else:
                right -= 1

        return False

The implementation begins by computing the integer square root of c. This gives the largest possible value that could participate in the equation.

Two pointers are then initialized:

  • left starts at 0
  • right starts at sqrt(c)

The loop continues while left <= right, ensuring all valid pairs are examined exactly once.

Inside the loop, the algorithm computes the current sum of squares.

If the sum equals c, the method immediately returns True.

If the sum is too small, left is incremented to increase the sum. If the sum is too large, right is decremented to reduce it.

If the loop finishes without finding a valid pair, the function returns False.

The implementation uses math.isqrt, which safely computes the integer square root without floating-point precision issues.

Go Solution

package main

import "math"

func judgeSquareSum(c int) bool {
	left := 0
	right := int(math.Sqrt(float64(c)))

	for left <= right {
		currentSum := left*left + right*right

		if currentSum == c {
			return true
		}

		if currentSum < c {
			left++
		} else {
			right--
		}
	}

	return false
}

The Go implementation follows the same algorithmic structure as the Python version.

One difference is that Go's math.Sqrt operates on float64, so we convert c to float64 before taking the square root, then convert the result back to int.

The constraints ensure that integer overflow is not a problem in Go for standard 64-bit environments, because the largest square involved is approximately:

46340^2 = 2147395600

which fits safely inside Go's int type on LeetCode systems.

Worked Examples

Example 1

Input: c = 5

We want to determine whether:

$a^2 + b^2 = 5$

Initial values:

left = 0
right = 2

because sqrt(5) is approximately 2.

Iteration left right left² + right² Action
1 0 2 0 + 4 = 4 Sum too small, increase left
2 1 2 1 + 4 = 5 Found solution

The algorithm returns true.

Example 2

Input: c = 3

Initial values:

left = 0
right = 1
Iteration left right left² + right² Action
1 0 1 0 + 1 = 1 Sum too small, increase left
2 1 1 1 + 1 = 2 Sum too small, increase left

Now:

left = 2
right = 1

Since left > right, the loop stops.

No valid pair exists, so the algorithm returns false.

Complexity Analysis

Measure Complexity Explanation
Time O(sqrt(c)) Each pointer moves at most sqrt(c) times
Space O(1) Only a few integer variables are used

The time complexity comes from the fact that the two pointers only move in one direction. The left pointer increases monotonically, and the right pointer decreases monotonically.

Since both pointers are bounded by sqrt(c), the total number of iterations is proportional to sqrt(c).

The algorithm uses constant extra memory because it stores only a few integer variables regardless of input size.

Test Cases

solution = Solution()

assert solution.judgeSquareSum(0) == True   # 0^2 + 0^2
assert solution.judgeSquareSum(1) == True   # 0^2 + 1^2
assert solution.judgeSquareSum(2) == True   # 1^2 + 1^2
assert solution.judgeSquareSum(3) == False  # no valid pair
assert solution.judgeSquareSum(4) == True   # 0^2 + 2^2
assert solution.judgeSquareSum(5) == True   # 1^2 + 2^2
assert solution.judgeSquareSum(8) == True   # 2^2 + 2^2
assert solution.judgeSquareSum(10) == True  # 1^2 + 3^2
assert solution.judgeSquareSum(11) == False # no valid pair
assert solution.judgeSquareSum(25) == True  # 0^2 + 5^2
assert solution.judgeSquareSum(50) == True  # 1^2 + 7^2
assert solution.judgeSquareSum(99) == False # no valid pair
assert solution.judgeSquareSum(1000000) == True  # large perfect square
assert solution.judgeSquareSum(2147483647) == False  # upper constraint stress test

Test Case Summary

Test Why
c = 0 Smallest possible input
c = 1 Uses zero plus a perfect square
c = 2 Uses equal squares
c = 3 Small number with no solution
c = 4 Perfect square case
c = 5 Standard positive example
c = 8 Equal non-zero squares
c = 10 Multiple valid combinations possible
c = 11 Confirms rejection behavior
c = 25 Larger perfect square
c = 50 Non-trivial valid pair
c = 99 Medium-sized invalid case
c = 1000000 Large valid value
c = 2147483647 Maximum constraint stress test

Edge Cases

Edge Case 1: c = 0

This is the smallest possible input and can easily be mishandled if the implementation assumes positive integers.

The correct interpretation is:

$0^2 + 0^2 = 0$

The algorithm handles this naturally because both pointers begin at 0, and the first computed sum immediately matches the target.

Edge Case 2: Perfect Squares

Values like 1, 4, 9, and 25 are important because one of the numbers may be zero.

For example:

$0^2 + 5^2 = 25$

Some incorrect implementations accidentally exclude zero from consideration. This solution explicitly starts left at 0, ensuring these cases are handled correctly.

Edge Case 3: Large Inputs Near the Constraint Limit

Values close to 2^31 - 1 can expose overflow problems or inefficient algorithms.

The two-pointer solution remains efficient because it performs only about sqrt(c) iterations, which is manageable even at the maximum input size.

The implementation also avoids floating-point comparison issues by using integer arithmetic for the sum computation.