Clean java solution O(n^2)


  • 62
    A
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i=0; i<C.length; i++) {
            for(int j=0; j<D.length; j++) {
                int sum = C[i] + D[j];
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        
        int res=0;
        for(int i=0; i<A.length; i++) {
            for(int j=0; j<B.length; j++) {
                res += map.getOrDefault(-1 * (A[i]+B[j]), 0);
            }
        }
        
        return res;
    }
    
    Time complexity:  O(n^2)
    Space complexity: O(n^2)

  • 0
    L

    Time complexity: O(lgn * n^2)?


  • 0
    A

    @liyi193328
    Time complexity for both the outer for-loops is O(n^2) since statements inside inner loops are O(1). What makes you think it's O(logn * n^2)?


  • 0
    L

    @asurana28
    map search one element is O(1)?


  • 0
    A

    @liyi193328
    HashMap amortized time complexity for get & put is O(1).


  • 0

    exactly the same as mine. Good solution


  • 0

    Similar Idea -

    public class Solution {
        public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
            int n = A.length; 
            if (n == 0) return 0; 
    
            HashMap<Integer, Integer> map = new HashMap<>(); 
            int res = 0, sum = 0; 
            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    sum = A[i] + B[j]; 
                    map.put(-sum, map.getOrDefault(-sum, 0) + 1); 
                }
            }
            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    sum = C[i] + D[j]; 
                    res += map.getOrDefault(sum, 0); 
                }
            }
            
            return res; 
        }
    }

  • 0

    Hashing is so powerful!


  • 0
    S

    same idea for c++ version

        int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
            unordered_map<int,int> m;
            int res = 0;
            for(int i=0; i < A.size(); i++)
                for(int j=0; j < B.size(); j++)
                   m[A[i]+B[j]]++;
            for(int i=0; i < C.size(); i++)
                for(int j=0; j < D.size(); j++)
                   res += m[-1*(C[i]+D[j])];
                   
            return res;
        }
    

  • 0
    F

    @asurana28 I don't agree with you.The time complexity of method getOrDefault is O(logN) just like binary search when it works.So,the total complexity is O(logN * N^2) .


  • 0
    F

    Oh,is my mistake.I have read source code of HashMap class carefully last night,and those methods' complexity is O(1) or O(n),it depends on the length of entry array and the entry link,


  • 0
    A

    @FuZhihong Amortized time complexity of method getOrDefault in HashMap is O(1).


  • 0
    F

    @asurana28 Yes,you are right. it does is O(1).


  • 1
    M

    thanks for sharing, the following is my more concise code:

        public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
            for(int a : A)
                for(int b : B){
                    int s = a+b;
                    map.put( s, map.getOrDefault(s, 0)+1 ); 
                }
            
            int result=0;
            for(int c : C)
                for(int d : D){
                    int s = -c-d;
                    result += map.getOrDefault(s, 0);
                }
            return result; 
        }
    

  • 0
    B

    Why should they have the same length? Even the length is different, the code still works.


  • 0
    J

    @asurana28 said in Clean java solution O(n^2):

    map.getOrDefault(-1 * (A[i]+B[j])

    why -1 here ? Can someone please explain?


  • 0
    K

    @jpankhan said in Clean java solution O(n^2):

    -1 here ? Can someone please

    The HashMap contains sum of all the pairs from C and D. Now we have a pair(say X) from which is sum from A and B (A[i]+B[j]) and we need to check if there is something in the HashMap which when added to X will give us zero. And we can have sum = 0 of two pairs(X and one from map) only if there is a corresponding negative value of X i.e -X in the Hashmap, so we just check that if there is -X in the map or not. If yes, we have a result and will add in our result variable else just add 0.


  • 0
    K

    @asurana28

    Somehow I think this looks even cleaner:

    public class Solution {
        
        public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
            Map<Integer, Integer> freqs = new HashMap<>();
            
            for (int c : C) {
                for (int d : D) {
                    freqs.put(c + d, freqs.getOrDefault(c + d, 0) + 1);
                }
            } 
            
            int count = 0;
            for (int a : A) {
                for (int b : B) {
                    count += freqs.getOrDefault(-a - b, 0);
                }
            }
            
            return count;
        }
    }
    

  • 0
    X
    This post is deleted!

  • 0
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
      int n = A.length;
      Map<Integer, Integer> map = new HashMap();
      for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
          int k = A[i] + B[j];
          int v = map.getOrDefault(k, 0) + 1;
          map.put(k, v);
        }        
      }
    
      int res = 0;
      for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
          int s = C[i] + D[j];
          if(map.containsKey(-s)){
            res += map.get(-s);
          }
        }
      } 
      return res;
    }

Log in to reply
 

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