We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Sparse Arrays
  2. Discussions

Sparse Arrays

  • williamliu14789
     + 3 comments

    O(m*n) Traditional Way

        public static List<Integer> matchingStrings(List<String> strings, List<String> queries) {
    
      List<Integer> sol = new ArrayList<Integer>();
      for(String x : queries)sol.add(countStr(x,strings));//O(m)
      return sol;
    }
    
    public static Integer countStr(String s, List<String> strings){
       int count = 0;
       for(String x : strings)if(s.equals(x))count++; //O(n)
       return count;
    }

    Utilizing HashMap O(m+n) Fastest way.

        public static List<Integer> matchingStrings(List<String> strings, List<String> queries) {
        Map<String, Integer> dic = new HashMap<String, Integer>();
        for(String ii: strings){ //O(n)
            int temp = dic.getOrDefault(ii,0);
            dic.put(ii, ++temp);
        }
        
        List<Integer> sol = new ArrayList<Integer>();
        for(String i : queries)    //O(m)
            sol.add(dic.getOrDefault(i,0));
        
        return sol;
    }

    This also works, Since collections is solid O(n), this is O(n*m)

        public static List<Integer> matchingStrings(List<String> strings, List<String> queries) {
        List<Integer> sol = new ArrayList<Integer>();
        for(String key : queries)  //O(m)
            sol.add(Collections.frequency(strings, key)); //O(n)
        return sol;

    }