Understanding the Logic Behind Two Sum — and Extending It to Three Sum

#datastructures #programming #sorting #twosum

Welcome back to our DSA Learning Series — where we pick one problem at a time, understand its logic deeply, and write clean, beginner-friendly code.

The Three Sum problem is a favorite among interviewers because it tests layered logical thinking — combining array traversal, the two-pointer technique, and duplicate handling.

But before tackling Three Sum, it’s crucial to fully understand the Two Sum logic, especially when the array is sorted.

Revisiting Two Sum (in a Sorted Array)
Problem Statement
Given a sorted array and a target sum, find two numbers whose sum equals the target.

Example:

Input: nums = [-3, -1, 0, 2, 4, 5], target = 3

Output: [1, 2] -- since nums[1] + nums[2] = 3

Intuition
If the array is sorted, we can use the two-pointer approach instead of nested loops for efficiency.

Steps:

Place one pointer at the start (left) and another at the end (right).
Calculate the sum of both numbers.
If sum == target, we found the pair.
If sum < target, move the left pointer forward (to increase the sum).
If sum > target, move the right pointer backward (to decrease the sum).

This way, we traverse the array only once — giving an O(n) solution.

Code: Two Sum (Sorted Array)

int left = 0;
int right = nums.length - 1;

while (left < right) {
    int sum = nums[left] + nums[right];

    if (sum == target) {
        System.out.println("Pair found: " + nums[left] + ", " + nums[right]);
        left++;
        right--;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

Extending the Logic to Three Sum
Once the Two Sum logic is clear, we can easily extend it to handle three numbers. Let's take a look at the below problem to understand the logic deeper.

Problem Statement
Find all unique triplets in the array whose sum equals 0.

Example:

Input: nums = [-1, 0, 1, 2, -1, -4]

Output: [[-1, -1, 2], [-1, 0, 1]]

Step-by-Step Intuition

Sort the array.
Sorting helps handle duplicates and makes the two-pointer logic work properly.
Fix one element (nums[i]).
Then apply the Two Sum approach on the remaining part of the array.
Set a new target:
Since we want nums[i] + nums[left] + nums[right] = 0,
the new target becomes -nums[i].
Move pointers (left, right) based on the current sum.
If sum == 0, store the triplet.
Skip duplicates to avoid repeated triplets.
Adjust pointers (left++, right--) accordingly.

Code: Three Sum (Two-Pointer Approach)

Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();

for (int i = 0; i < nums.length - 2; i++) {
    // Skip duplicate elements for the first number
    if (i > 0 && nums[i] == nums[i - 1]) continue;

    int left = i + 1;
    int right = nums.length - 1;

    while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];

        if (sum == 0) {
            result.add(Arrays.asList(nums[i], nums[left], nums[right]));

            // Skip duplicates for left and right
            while (left < right && nums[left] == nums[left + 1]) left++;
            while (left < right && nums[right] == nums[right - 1]) right--;

            left++;
            right--;
        } else if (sum < 0) {
            left++;
        } else {
            right--;
        }
    }
}

Why This Works

The outer loop fixes one element (nums[i]).

The inner loop uses the Two Sum logic to find pairs that sum to negative of nums[i].

Sorting enables: