4Sum II: Pair Summation with Hash Maps

Given four integer arrays of equal length, determine the number of tuple combinations (i, j, k, l) where the sum of corresponding elements equals zero.

Unlike single-array k-sum problems requiring deduplication, this scenario involves four independent collections. The optimal strategy utilizes a divide-and-conquer approach with hash-based frequency counting:

1. Precompute all possible pairwise sums from the first two arrays, storing each sum's occurrence count in an unordered map
2. Iterate through pairs from the remaining two arrays, checking if their additive inverse exists in the map
3. Accumulate the frequency counts of matching complementary sums

Complexity Analysis:

• Time: O(n²) where n is the array length
• Space: O(n²) for storing pairwise sums

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, 
                     vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> sumFrequency;
        
        for (int x : nums1) {
            for (int y : nums2) {
                sumFrequency[x + y]++;
            }
        }
        
        int validTuples = 0;
        for (int z : nums3) {
            for (int w : nums4) {
                int complement = -(z + w);
                auto it = sumFrequency.find(complement);
                if (it != sumFrequency.end()) {
                    validTuples += it->second;
                }
            }
        }
        return validTuples;
    }
};

Ransom Note Validation Using Frequency Arrays

Determine whether a ransom note string can be constructed from characters available in a magazine string, with each magazine character usable at most once.

Given the constraint of lowercase English letters only, a fixed-size array serves as a more efficient hash structure than a tree-based or bucket-based map, eliminating overhead from dynamic memory allocation and hash computation.

Algorithm:

1. If the ransom note exceeds the magazinee length, immediate rejection
2. Populate a 26-element frequency array with character counts from the magazine
3. Decrement counts for each character in the ransom note
4. Return false if any decrement results in a negative value

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote.size() > magazine.size()) return false;
        
        int charFreq[26] = {0};
        
        for (char c : magazine) {
            charFreq[c - 'a']++;
        }
        
        for (char c : ransomNote) {
            if (--charFreq[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

3Sum: Eliminating Duplicates with Two Pointers

Find all unique triplets in an integer array that sum to zero without using the same element index multiple times.

Hash Set Approach (Suboptimal): While sorting followed by nested loops with a hash set for complement lookup achieves O(n²) time, handling duplicate triplets becomes cumbersome. The deduplication logic requires tracking previously seen values and often leads to excessive time consumption or missed edge cases during implementation.

Two-Pointer Approach (Optimal): After sorting the array, fix the first element and employ dual pointers scanning inward from the aray extremities toward the center:

• If the current sum exceeds zero, decrement the right pointer to reduce the total
• If the sum is less than zero, increment the left pointer to increase the total
• Upon finding a valid triplet, record it and skip adjacent duplicates before continuing

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> triplets;
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i-1]) continue;
            
            int left = i + 1, right = nums.size() - 1;
            
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                
                if (currentSum > 0) {
                    --right;
                } else if (currentSum < 0) {
                    ++left;
                } else {
                    triplets.push_back({nums[i], nums[left], nums[right]});
                    
                    while (left < right && nums[right] == nums[right-1]) --right;
                    while (left < right && nums[left] == nums[left+1]) ++left;
                    
                    --right;
                    ++left;
                }
            }
        }
        return triplets;
    }
};

4Sum: Extending to Quadruplets

Generalize the 3Sum solution to find unique quadruplets suming to a specified target value.

The algorithm adds an additional iteration layer:

1. Two nested loops fix the first two elements
2. Two pointers resolve the remaining pair
3. Pruning optimizations must account for negative targets—unlike 3Sum where positive starting values guarantee no solution, a negative target with negative starting values requires careful boundary checks

Overflow Prevention: Cast intermediate sums to 64-bit integers before comparison to prevent integer overflow with large input values.

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> quadruplets;
        sort(nums.begin(), nums.end());
        
        for (int first = 0; first < nums.size(); ++first) {
            if (nums[first] > target && nums[first] >= 0) break;
            if (first > 0 && nums[first] == nums[first-1]) continue;
            
            for (int second = first + 1; second < nums.size(); ++second) {
                long long partialSum = (long long)nums[first] + nums[second];
                if (partialSum > target && partialSum >= 0) break;
                if (second > first + 1 && nums[second] == nums[second-1]) continue;
                
                int left = second + 1;
                int right = nums.size() - 1;
                
                while (left < right) {
                    long long total = partialSum + nums[left] + nums[right];
                    
                    if (total > target) {
                        --right;
                    } else if (total < target) {
                        ++left;
                    } else {
                        quadruplets.push_back({nums[first], nums[second], 
                                              nums[left], nums[right]});
                        
                        while (left < right && nums[right] == nums[right-1]) --right;
                        while (left < right && nums[left] == nums[left+1]) ++left;
                        
                        --right;
                        ++left;
                    }
                }
            }
        }
        return quadruplets;
    }
};