Analysis of Algorithms: Solving the 3-SUM Problem

When it comes to measuring the efficiency of algorithms, we often look at their time and space complexity. This analysis helps us understand how an algorithm will perform as the input size grows. A classic problem that illustrates these concepts is the 3-SUM problem.

The 3-SUM Problem

The 3-SUM problem asks us to find all unique triplets in an array of n integers that sum up to zero.

Question: Design an algorithm for the 3-SUM problem that takes time proportional to n² in the worst case. You may assume that you can sort the n integers in time proportional to n² or better.

A Quadratic Time Solution

To solve the 3-SUM problem in O(n²) time, we can use a combination of sorting and the two-pointer technique.

Approach

1. Sort the Array: First, we sort the input array in ascending order. This is a crucial step that allows us to efficiently find the triplets.
2. Iterate and Use Two Pointers: We iterate through the array with a for loop. For each element nums[i], we’ll try to find two other elements in the array that sum up to -nums[i]. To do this, we use two pointers, left and right, initialized to i + 1 and the end of the array, respectively.
3. Adjust Pointers Based on the Sum:
   • If nums[left] + nums[right] is less than our target (-nums[i]), we increment left to get a larger sum.
   • If the sum is greater than the target, we decrement right to get a smaller sum.
   • If we find a sum that equals our target, we’ve found a triplet. We add it to our result list.
4. Skip Duplicates: To ensure our triplets are unique, we skip over any duplicate elements during our iteration.

Python Implementation

def three_sum(nums):
    nums.sort()
    result = []
    n = len(nums)
    for i in range(n):
        # Skip duplicate elements for the first element of the triplet
        if i > 0 and nums[i] == nums[i-1]:
            continue

        target = -nums[i]
        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[left] + nums[right]
            if current_sum < target:
                left += 1
            elif current_sum > target:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                # Skip duplicates for the second and third elements
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
    return result

Java Implementation

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSumQuadratic {

    public static List<List<Integer>> threeSum(int[] nums) {
        // Sort the array to enable the two-pointer approach
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;

        // Iterate through the array, considering each element as a potential first element of a triplet
        for (int i = 0; i < n - 2; i++) {
            // Skip duplicate elements to avoid redundant triplets
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = n - 1;
            int target = -nums[i];

            // Use two pointers to find the other two elements
            while (left < right) {
                int currentSum = nums[left] + nums[right];

                if (currentSum == target) {
                    // Found a triplet
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // Skip duplicates for the second and third elements
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    // Move pointers to find the next unique pair
                    left++;
                    right--;
                } else if (currentSum < target) {
                    // Sum is too small, move the left pointer to increase it
                    left++;
                } else {
                    // Sum is too large, move the right pointer to decrease it
                    right--;
                }
            }
        }
        return result;
    }
}

Complexity Analysis

• Time Complexity: The sorting step takes O(n log n) time. The nested loops give us a time complexity of O(n²). Since O(n²) is greater than O(n log n), the overall time complexity of our algorithm is O(n²).
• Space Complexity: We use a list to store the resulting triplets. In the worst case, we might have to store O(n²) triplets, so the space complexity is O(n²). If we don’t count the space for the output, the space complexity is O(1) (or O(n) if the sorting algorithm requires it).

This approach provides an efficient way to solve the 3-SUM problem within the desired time complexity, showcasing the power of combining sorting with clever pointer manipulation.