Optimizing the 3Sum Problem

Given an integer array elements, the objective is to identify all unique triplets [a, b, c] such that a + b + c = 0. The soluiton set must not contain duplicate triplets.

Constraints

• Array length ranges from 0 to 3000.
• Element values range from -10^5 to 10^5.

Implementation Strategy

Sorting the array allows the use of a fixed pivot combined with two moving pointesr. Pruning conditions are applied to skip unnecessary iterations when the smallest available number exceeds zero or when duplicate values are encountered.

class Solution {
public:
    std::vector<std::vector<int>> findTriplets(std::vector<int>& elements) {
        std::sort(elements.begin(), elements.end());
        std::vector<std::vector<int>> solutionSet;
        int n = elements.size();

        if (n < 3) {
            return solutionSet;
        }

        for (int pivot = 0; pivot < n - 2; ++pivot) {
            // Optimization: If the smallest number is positive, sum cannot be zero
            if (elements[pivot] > 0) {
                break;
            }

            // Skip duplicate pivots
            if (pivot > 0 && elements[pivot] == elements[pivot - 1]) {
                continue;
            }

            int start = pivot + 1;
            int end = n - 1;

            while (start < end) {
                int currentSum = elements[pivot] + elements[start] + elements[end];

                if (currentSum == 0) {
                    solutionSet.push_back({elements[pivot], elements[start], elements[end]});
                    
                    // Skip duplicate values for the left pointer
                    while (start < end && elements[start] == elements[start + 1]) {
                        ++start;
                    }
                    // Skip duplicate values for the right pointer
                    while (start < end && elements[end] == elements[end - 1]) {
                        --end;
                    }
                    
                    ++start;
                    --end;
                } else if (currentSum < 0) {
                    ++start;
                } else {
                    --end;
                }
            }
        }
        return solutionSet;
    }
};

Solving the 3Sum Closest Variation

In this variation, given an array data and an objective value, the goal is to find three integers whose sum is nearest to the target. The function returns the sum itself. It is assumed that exactly one optimal solution exists.

Constraints

• Array length ranges from 3 to 1000.
• Element values range from -1000 to 1000.
• Target value ranges from -10^4 to 10^4.

Implementation Strategy

Similar to the standard 3Sum problem, the array is sorted to facilitate pointer movement. The algorithm tracks the sum with the minimum absolute difference from the target. Duplicate pivots are skipped to avoid redundant calculations.

class Solution {
public:
    int findClosestSum(std::vector<int>& data, int objective) {
        std::sort(data.begin(), data.end());
        int n = data.size();
        
        // Initialize with the first possible triplet
        int bestMatch = data[0] + data[1] + data[2];

        for (int i = 0; i < n - 2; ++i) {
            // Avoid processing the same pivot value multiple times
            if (i > 0 && data[i] == data[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int currentTotal = data[i] + data[left] + data[right];

                // Update result if current total is closer to the objective
                if (std::abs(currentTotal - objective) < std::abs(bestMatch - objective)) {
                    bestMatch = currentTotal;
                }

                if (currentTotal > objective) {
                    --right;
                } else if (currentTotal < objective) {
                    ++left;
                } else {
                    // Exact match found
                    return objective;
                }
            }
        }
        return bestMatch;
    }
};