Nhut Nguyen
Nhut Nguyen

Follow

Nhut Nguyen

Follow
Solutions to Leetcode 454. 4Sum II

Solutions to Leetcode 454. 4Sum II

Nhut Nguyen's photo
Nhut Nguyen
·Mar 18, 2022·

3 min read

Play this article

Problem statement

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:
The 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

  • nums1.length = nums2.length = nums3.length = nums4.length = n.
  • 1 <= n <= 200.
  • -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28.

Solution 1: Four loops

Code

#include <iostream>
#include <vector>
using namespace std;
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    int count = 0;
    for (auto& n1 : nums1) {
        for (auto& n2 : nums2) {
            for (auto& n3 : nums3) {
                for (auto& n4 : nums4) {
                    if (n1 + n2 + n3 + n4 == 0) {
                        count++;
                    }
                }
            }
        }
    }
    return count;    
}
int main() {
    vector<int> nums1, nums2, nums3, nums4;
    nums1 = {1, 2};
    nums2 = {-2, -1};
    nums3 = {-1, 2};
    nums4 = {0, 2};
    cout << fourSumCount(nums1, nums2, nums3, nums4) << endl;
    nums1 = {0};
    nums2 = {0};
    nums3 = {0};
    nums4 = {0};
    cout << fourSumCount(nums1, nums2, nums3, nums4) << endl;
}
Output:
2
1

Complexity

  • Runtime: O(n^4).
  • Extra memory: O(1).

Solution 2: Two loops

Rewriting nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 as nums1[i] + nums2[j] == 0 - nums3[k] - nums4[l] you could reduce the runtime complexity of the solution above from O(n^4) to O(n^2) by storing the sum nums1[i] + nums2[j] in a map.

Code

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    int count = 0;
    unordered_map<int, int> sumTwo; 
    for (auto& n1 : nums1) {
        for (auto& n2 : nums2) {
            sumTwo[n1 + n2]++;
        }
    }
    for (auto& n3 : nums3) {
        for (auto& n4 : nums4) {
            auto it = sumTwo.find(0 - n3 - n4);
            if (it != sumTwo.end()) {
                count += it->second;
            }
        }
    }
    return count;    
}
int main() {
    vector<int> nums1, nums2, nums3, nums4;
    nums1 = {1, 2};
    nums2 = {-2, -1};
    nums3 = {-1, 2};
    nums4 = {0, 2};
    cout << fourSumCount(nums1, nums2, nums3, nums4) << endl;
    nums1 = {0};
    nums2 = {0};
    nums3 = {0};
    nums4 = {0};
    cout << fourSumCount(nums1, nums2, nums3, nums4) << endl;
}
Output:
2
1

Complexity

  • Runtime: O(n^2).
  • Extra memory: O(n^2).

Did you find this article valuable?

Support Nhut Nguyen by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this