4-line C++ O(N^2) solution with hashmap + what to do wisely for generic list sizes


  • 0

    To find tuple (a, b, c, d) with elements from each list, it is straight forward to loop through any two lists to count for partial sum, and then look for opposite partial sum in the rest two lists.

        int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
          unordered_map<int, int> APlusBcount; int res = 0;
          for (int a:A) for (int b:B) APlusBcount[a+b]++;
          for (int c:C) for (int d:D) res += APlusBcount[-c-d];
          return res;
        }
    

    The interesting question is how to minimize time complexity if the 4 given lists have different sizes? Let NA ≤ NB ≤ NC ≤ ND be the sizes of the given lists and without losing generality, assume the list sizes are in ascending order. The overall time complexity will be the hashmap size for partial sum count (we pick some list(s) to build) plus the loop(s) to go through the rest list(s) for opposite sum matching, so we have time complexity

    • Time = O(f(n)), where f(n) = max(n, N/n) with N := NANBNCND,

    where n is the product of list sizes picked to build hashmap. Note that for any 0 < x < y, function f has

    • f(x) ≤ f(y) if and only if N ≤ xy,

    so for all choices, either n = ND or NAND achieves minimum values. Note that ND ≤ NAND, so we have the optimal time complexity is

    • O(f(ND)) = O(max(ND, NANBNC)) if NBNC ≤ ND
      and
    • O(f(NAND)) = O(max(NAND, NBNC)) otherwise.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.