Coding Interview Questions | Three Sum

January 10th, 2024

Three Sum Problem Introduction:

This summary will talk about my solution to the three sum problem as seen on leetcode here.

How do you solve the Three Sum Problem Using Two Pointers?

Solution:

function threeSum(nums: number[]): number[][] {
  const result: number[][] = [];

  nums.sort((a, b) => a - b);

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

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

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

      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        left++;
        right--;

        // Skip duplicate elements
        while (left < right && nums[left] === nums[left - 1]) {
          left++;
        }
        while (left < right && nums[right] === nums[right + 1]) {
          right--;
        }
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }

  return result;
}

Three Sum Solution Summary:

Below is a breakdown of the key aspects of the provided solution:

1. Array Sorting: The algorithm starts by sorting the input array nums in ascending order. Sorting is crucial for identifying patterns and simplifying the process of finding unique triplets.

2. Iterative Approach: The algorithm uses a nested loop structure to iterate through the sorted array. The outer loop (for (let i = 0; i < nums.length - 2; i++)) selects the first element of a potential triplet.

3. Duplicate Skip Handling: To avoid duplicate triplets, the algorithm skips over consecutive identical elements during both the outer and inner loops (if (i > 0 && nums[i] === nums[i - 1]) and while (left < right && nums[left] === nums[left - 1]) and while (left < right && nums[right] === nums[right + 1])).

4. Two-Pointer Technique: The core of the solution lies in the two-pointer technique. Inside the nested loops, two pointers (left and right) are adjusted based on the sum of the current triplet. This efficiently explores all possible triplet combinations.

5. Triplet Validation and Storage: When the sum of the current triplet equals zero, it is considered a valid solution, and the triplet is stored in the result array. The pointers are then adjusted to explore other potential solutions.

Complexities:

1. Time Complexity: The time complexity of the solution is O(n^2), where n is the size of the input array. The nested loops iterate through the array, and the two-pointer technique ensures an efficient exploration of triplets.

2. Space Complexity: The space complexity is O(1) as the algorithm uses a constant amount of extra space, excluding the input and output. The result is not considered in the space complexity analysis since it is part of the function’s output.