[Hackerrank] – Missing Numbers Solution

2.8K

Question: You are required to find missing numbers that are left out while an artist transports numbers from one array to other. The output array should be sorted.

Input:
arr [ ] = {7, 2, 5, 3, 5, 3}
brr [ ] = {7, 2, 5, 4, 6, 3, 5, 3}

Output:
Missing numbers: {4, 6}

Problem Statement:

Let me try to simplify the problem a little first.

The problem description is quite verbose and we narrow down it to quite an extent. To summarize, the artist has an original array brr, and he is transporting the numbers to other array arr. While transporting he misses to copy some numbers and they are termed as missing numbers. We need to return all the missing numbers in an array that is also sorted.

An important thing to note here is that while transporting the numbers, we need to take care of the frequency as well. So for instance if the original array brr has two 1‘s, and the other array arr has just one 1. Then 1 will also be in the output array.

Brute Force Method:

One easy way to solve this problem could be:

1. Start with the first element of array arr.
2. Now try to search this element in the original array brr.
3. Once this element is found, you can flag it.
4. Repeat the steps 1-3 for all elements in the array arr.
5. Once all the elements have been flagged, iterate through the array brr for one last time and add all un-flagged elements to a resultant array.
6. Sort the resultant array and return it.

This solution would work perfectly for all sample test cases, but it would take a lot of time if the arrays are huge. This is because we would be wasting a lot of time in searching elements in the original array brr.

Optimized Method:

Instead of scanning the entire array over and over again, we can utilize a data structure that can speed up things. A TreeMap for instance is a data structure in JAVA, which works as a HashMap, but also keeps the keys sorted in an ascending order. Using this treemap, we can come up with a solution as:

1. Create an empty TreeMap to store array elements and their frequencies.
2. Traverse the array brr, and update the map with the frequency of each element. This map now represents all the elements of the original array. Note that they are also in a sorted manner.
3. Now traverse the array arr and for each element in the array, decrease the frequency by 1.
4. If the frequency of any element becomes 0, then remove the key from the TreeMap.
5. At the end, scan the entire map for one last time and see all the elements who have a frequency greater than 1.

These all numbers are the missing numbers and since the Treemap is already sorted, we add them to an array and return the result.

Code:

  public int[] missingNumbers(int[] arr, int[] brr) {

    TreeMap<Integer, Integer> integerFreqMap = new TreeMap<>();

    // Add elements of original list
    for (int i : brr) {
      int freq = integerFreqMap.getOrDefault(i, 0);
      freq++;
      integerFreqMap.put(i, freq);
    }

    // Remove elements of new list
    for (int i : arr) {
      int freq = integerFreqMap.get(i);
      freq--;
      if (freq == 0)
        integerFreqMap.remove(i);
      else
        integerFreqMap.put(i, freq);
    }

    // Create the result array
    int[] result = new int[integerFreqMap.size()];
    int i = 0;
    for (Map.Entry<Integer, Integer> integerIntegerEntry : integerFreqMap.entrySet()) {
      result[i++] = integerIntegerEntry.getKey();
    }

    return result;
  }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(n)

You can find the code and test cases on Github.
The problem statement on HackerRank.

Video Explanation: