Missing Numbers

  • + 0 comments

    My Java Solution below has o(n + m + u + k log k) time and o(n + m +k) space:

    public static List<Integer> missingNumbers(List<Integer> arr, List<Integer> brr) {
            //goal: determine which elements in brr are missing or underrepresented in arr
            
            //use a freq map for each val in brr and arr
            Map<Integer, Integer> brrFreqMap = 
                brr.stream()
                .collect(Collectors.
                groupingBy(Function.identity(), Collectors.collectingAndThen(Collectors.counting(), Long::intValue)));
            Map<Integer, Integer> arrFreqMap = 
                arr.stream()
                .collect(Collectors.
                groupingBy(Function.identity(), Collectors.collectingAndThen(Collectors.counting(), Long::intValue)));
            
            //iterate over each key in arr and check if its in brr
            Set<Integer> missingNumbersSet = new HashSet<>();
            for (Map.Entry<Integer, Integer> entry : brrFreqMap.entrySet()) {
                int key = entry.getKey();
                int freqInBrr = entry.getValue();
                int freqInArr = arrFreqMap.getOrDefault(key, 0); // avoids null issues
    
                if (freqInArr < freqInBrr) {
                    missingNumbersSet.add(key);
                }
            }
    
            // Step 3: Convert to list and sort
            List<Integer> missingNumbers = new ArrayList<>(missingNumbersSet);
            Collections.sort(missingNumbers);
            return missingNumbers;
        }