Equalize the Array

It seems like it is going to be a nice day in the Twin Cities of Minneapolis and St. Paul. The sun is shining and the forecast calls for a high in the mid 60s. If it remains dry my wife and I will go for a walk around 05:00 PM. Looking forward to a walk to burn some calories gained over the weekend.

I received a message with the Equalize the Array  challenge from HackerRank. The idea seems that we need to figure out which value repeats the most and then remove the rest of the entries. Seems like a job for a hash map.

Allow me to display the edited values using two test cases:

5
3 3 2 1 3

hm: {1=1, 2=1, 3=3}
maxVal: 3
maxVal: 3
maxVal: 3
2

8
1 2 3 1 2 3 3 3

hm: {1=2, 2=2, 3=4}
maxVal: 4
maxVal: 4
maxVal: 4
4

In the first example number 3 seems to be repeated 3 times. The array contains 5 values. If we delete 5 – 3 = 2 elements we seem to get the job done.

In the second example, number 3 is repeated 4 times. The size of the array is 8. Once again if we compute 8 – 4 = 4 it seems to work out.

The test scaffolding was provided by HackerRank. I copied it to my solution and edited to be able to directly access System.out.

Let’s take a look at my solution written in Java 8 using the Eclipse IDE:

    // Complete the equalizeArray function below.
    static int equalizeArray(int[] arr) {

    	HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
 
    	// **** load hash map (compute max value) [1] ****
    	int maxVal = 0;
    	for (int i = 0; i < arr.length; i++) { if (hm.containsKey(arr[i])) { int val = hm.get(arr[i]) + 1; hm.put(arr[i], val); if (val > maxVal)
    				maxVal = val;
    		} else {
    			hm.put(arr[i], 1);
    			if (1 > maxVal)
    				maxVal = 1;
     		}
    	}
    	
    	// ???? ????
    	System.out.println("hm: " + hm.toString());
     	System.out.println("maxVal: " + maxVal);
     	
     	// **** get max value from hash map [2] ****
     	Map.Entry<Integer, Integer> maxEntry = hm.entrySet().stream().max(Map.Entry.comparingByValue()).get();
     	maxVal = maxEntry.getValue();
     	
     	// ???? ????
     	System.out.println("maxVal: " + maxVal);
     	
     	// **** iterate and get the entry with the maximum value [3] ****
     	Iterator it = hm.entrySet().iterator();
     	maxVal = 0;
     	while (it.hasNext()) {
     		Entry<Integer, Integer> e = (Map.Entry<Integer, Integer>)it.next();
     		if (e.getValue() > maxVal)
     			maxVal = e.getValue();
     	}
     	
    	// ???? ????
     	System.out.println("maxVal: " + maxVal);
 
    	// **** return the minimum number of deletions ****
    	return arr.length - maxVal;
    }

If we use a hash map we will figure out by display it that the number we are looking for in the first example is 3 because for key = 3 the value = 3. In the second example, the largest value = 4 is for key = 3. So how do we get to such value to compute the value returned by our function?

I show three approaches. In the first we keep track of the maximum value using the maxVal variable when loading the hash map with the array values being used as keys. We can then just use the last line in the method to return the desired value.

On the second approach, we can remove the computation of the maxVal in the loop processing the array, and then stream the hash map returning the maximum value. Once again, we can then jump to the returned statement.

In the third and final approach, we skip computing the maxVal in the loop and then we instantiate an iterator. We then iterate through the value looking for the maximum. Once that is done, we can jump to the returned value.

We can use additional approaches to get the same results. I like the simplest because it seems that is the most elegant in the set here presented. We or someone else in the development team may come back weeks, months or year after and be able to quickly determine if the method works as advertised. I always like to follow the KISS rule.

If you are interested in the complete solution, you can find it in my GitHub repository.

Keep on reading and experimenting. It is the best way to learn!

If you have comments or questions regarding this post or any other one in this blog, or if you would like help in any phase of the SDLC for a product or service, please leave me a note bellow. Notes requesting help will be kept confidential.

Enjoy;

John

Follow me on Twitter:  @john_canessa