Q45 4Sum II - LeetCode

PHOTO EMBED

Mon Jan 30 2023 08:34:31 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //Tc- O(n^2) Sc - O(n^2) = hashmap

        //make a HM to store sum of nums1 and nums2 and their frequency
        HashMap<Integer,Integer> fmap = new HashMap<>();

        for(int val1 : nums1){
            for(int val2 : nums2){
                int sum = val1+val2;
                fmap.put(sum , fmap.getOrDefault(sum,0)+1);
            }
        }

        //iterate through nums 3 and nums 4 and find if -(sum) exists in HM
        int count = 0;

        for(int val3 : nums3){
            for(int val4 : nums4){
                int sum = val3+val4;
                
                //if -(sum) exists then all 4sum = 0
                if(fmap.containsKey(-sum))
                count += fmap.get(-sum);
            }
        }

        return count;
    }
}
content_copyCOPY

https://leetcode.com/problems/4sum-ii/