Hash Table Algorithms: Solving Multi-Sum Problems
- 4Sum II (LeetCode 454)
Problem Description
Given four integer arrays nums1, nums2, nums3, and nums4, all of length n, return the number of tuples (i, j, k, l) such that:
- 0 <= i, j, k, l < n
- nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
Example 1:
Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
Two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
Example 2:
Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1
Constraints:
- n == nums1.length == nums2.length == nums3.length == nums4.length
- 1 <= n <= 200
- -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
Approach
The optimal soultion involves using a hash map to store the sum of pairs from the first two arrays, then checking for complementary sums in the last two arrays.
Solution
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int count = 0;
unordered_map<int int=""> sumMap;
// Store all possible sums of elements from nums1 and nums2
for (int num1 : nums1) {
for (int num2 : nums2) {
sumMap[num1 + num2]++;
}
}
// Check for complementary sums in nums3 and nums4
for (int num3 : nums3) {
for (int num4 : nums4) {
int complement = -(num3 + num4);
if (sumMap.find(complement) != sumMap.end()) {
count += sumMap[complement];
}
}
}
return count;
}
};
</int></int></int></int></int>
- Ransom Note (LeetCode 383)
Problem Description
Given two strings ransomNote and magazine, return true if ransomNote can be constructed using the letters from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
Example 1:
Input: ransomNote = "a", magazine = "b"
Output: false
Example 2:
Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3:
Input: ransomNote = "aa", magazine = "aab"
Output: true
Constraints:
- 1 <= ransomNote.length, magazine.length <= 10^5
- ransomNote and magazine consist of lowercase English letters
Approach
We can use a frequency array or hash map to count the occurrences of each character in magazine, then verify if ransomNote can be constructed with these characters.
Solution
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int> charCount(26, 0);
// Count characters in magazine
for (char c : magazine) {
charCount[c - 'a']++;
}
// Check if ransomNote can be constructed
for (char c : ransomNote) {
charCount[c - 'a']--;
if (charCount[c - 'a'] < 0) {
return false;
}
}
return true;
}
};
</int>
- 3Sum (LeetCode 15)
Problem Description
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
The distinct triplets are [-1,0,1] and [-1,-1,2]
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet doesn't sum to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums to 0.
Constraints:
- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
Approach 1: Hash Table
Sort the array first. For each element, use a hash set to find pairs that sum to the complement of the current element.
Solution 1
class Solution {
public:
vector<vector>> threeSum(vector<int>& nums) {
vector<vector>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
// Skip positive numbers as they can't sum to 0
if (nums[i] > 0) break;
// Skip duplicates for the first element
if (i > 0 && nums[i] == nums[i-1]) continue;
unordered_set<int> seen;
for (int j = i + 1; j < nums.size(); j++) {
int complement = -(nums[i] + nums[j]);
if (seen.find(complement) != seen.end()) {
result.push_back({nums[i], complement, nums[j]});
// Skip duplicates for the third element
while (j + 1 < nums.size() && nums[j] == nums[j+1]) j++;
}
seen.insert(nums[j]);
}
}
return result;
}
};
</int></vector></int></vector>
Approach 2: Two Pointers
Sort the array. For each element, use two pointers (left and right) to find pairs that sum to the complement of the current element.
Solution 2
class Solution {
public:
vector<vector>> threeSum(vector<int>& nums) {
vector<vector>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
// Skip positive numbers as they can't sum to 0
if (nums[i] > 0) break;
// Skip duplicates for the first element
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
} else {
result.push_back({nums[i], nums[left], nums[right]});
// Skip duplicates for the second element
while (left < right && nums[left] == nums[left+1]) left++;
// Skip duplicates for the third element
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
}
}
}
return result;
}
};
</vector></int></vector>
- 4Sum (LeetCode 18)
Problem Description
Given an array nums of n integers and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
- 0 <= a, b, c, d < n
- a, b, c, and d are distinct
- nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Constraints:
- 1 <= nums.length <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
Approach
Extend the two-pointer approach used in 3Sum. Sort the array and use two nested loops for the first two elements, then use two pointers for the remaining elements.
Solution
class Solution {
public:
vector<vector>> fourSum(vector<int>& nums, int target) {
vector<vector>> result;
if (nums.size() < 4) return result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 3; i++) {
// Skip duplicates for the first element
if (i > 0 && nums[i] == nums[i-1]) continue;
// Early termination if smallest possible sum exceeds target
if ((long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
// Early termination if largest possible sum is less than target
if ((long)nums[i] + nums[nums.size()-3] + nums[nums.size()-2] + nums[nums.size()-1] < target) continue;
for (int j = i + 1; j < nums.size() - 2; j++) {
// Skip duplicates for the second element
if (j > i + 1 && nums[j] == nums[j-1]) continue;
// Early termination if smallest possible sum exceeds target
if ((long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
// Early termination if largest possible sum is less than target
if ((long)nums[i] + nums[j] + nums[nums.size()-2] + nums[nums.size()-1] < target) continue;
int left = j + 1;
int right = nums.size() - 1;
while (left < right) {
long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
result.push_back({nums[i], nums[j], nums[left], nums[right]});
// Skip duplicates for the third element
while (left < right && nums[left] == nums[left+1]) left++;
// Skip duplicates for the fourth element
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
}
}
}
}
return result;
}
};
</vector></int></vector>
- Hash Table Summary
Hash tables are primarily used to check if an element has appeared before. In C++, we can use arrays, sets, and maps as hash table implementations:
- Arrays: Suitable when the number of possible elements is known and limited (e.g., 26 lowercase letters).
- Sets: Useful when dealing with an unlimited number of elements, providing O(1) average time complexity for insertions, deletions, and lookups.
- Maps: Ideal for key-value pair storage, allowing efficient lookups based on keys.
For multi-sum porblems, hash tables can significantly reduce time complexity by storing intermediate results and checking for complements in constant time.