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

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:

1. Place one pointer at the start (left) and another at the end (right).

2. Calculate the sum of both numbers.

3. If sum == target, we found the pair.

4. If sum < target, move the left pointer forward (to increase the sum).

5. 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

1. Sort the array.
   Sorting helps handle duplicates and makes the two-pointer logic work properly.

2. Fix one element (nums[i]).
   Then apply the Two Sum approach on the remaining part of the array.

3. Set a new target:
   Since we want nums[i] + nums[left] + nums[right] = 0,
   the new target becomes -nums[i].

4. Move pointers (left, right) based on the current sum.

5. If sum == 0, store the triplet.

6. Skip duplicates to avoid repeated triplets.

7. 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:

• Skipping duplicates easily.
• Using the two-pointer pattern effectively.

This approach efficiently finds all unique triplets in O(n²) time — which is optimal for this problem.

What was your aha moment while reading this?
Let us know — and don’t forget to share this post with someone preparing for their coding interviews!

Comments

[Rohit Khola]

If time complexity is n^2 then we can do this problem using hash map also.

[we_are_broken_compilers]

Thanks for reading the article and posting your question here!

You are right to think that we could go for hashmap approach for two sum logic as that would work as well here. However that approach uses O(n) space because of map, but in this sorted array approach we are using constant amount of space which is beneficial for us.

Let us know if you have any further questions 🙂