Last weekend my wife and I stopped to visit our son who also lives in the Twin Cities of Minneapolis and St. Paul. On our last trip to Europe, our granddaughters asked us if we could get for their dad a bottle of flavored vodka in the duty free store in the Schiphol airport in Amsterdam. At the time looked like a good idea. He seems to enjoy vodka. When we returned home the girls gave their dad the bottle.
Last Sunday my wife and I stopped at my son’s house. He offered us a glass of flavored vodka with some Sprite. We did notice that the bottle was almost full. That was an indication that the flavor was not that great. My wife and I had a sip and added the rest of the can into our drinks. For sure the vodka had the flavor and smell of tulips.
Around 08:00 PM my wife and I headed home. We go to sleep early so we did.
I woke up the next day at 05:00 AM with the alarm. Overnight I did not go to the bathroom. I always wake up a few times. On occasions I get up and read for a while. Then I get back in bed. This particular night I slept through.
After I fixed breakfast I woke up my wife. She had a hard time waking up. She also did not make a trip to the bathroom. She slept through. While having breakfast we discussed what changed. We quickly figured out that it was the flavored vodka. I will call my son in a few to tell him our story and conclusion. I am curios to hear his comments.
Now let’s get to the actual topic for this post. First I want to apologize. I was planning on using Visual Studio Core for this post but as a force of habit I used the Eclipse IDE. I have a sticky paper note on my table to remind me to use Visual Studio Core on the next post.
The problem at hand is 17.10 in the Cracking the Coding Interview book by Gayle Laakmann McDowell. The challenge is to determine the value of the majority element in an array. If the majority is not found, we should return -1. By the way, the majority element is the value that fills more than half the entries in an array. The kicker is that we need to find the value in O(n) which is not a problem, but we also must use O(1) space. My first thought was to use a hash map to keep track of the counts of the values. That is not possible if we have to solve it in O(1) space.
Let’s start by taking a look at the screen capture from a screen capture of the console of the Eclipse IDE when we run the program using different values.
9 1 2 5 9 5 9 5 5 5 main <<< n: 9 main <<< arr: [1, 2, 5, 9, 5, 9, 5, 5, 5] main <<< findMajorityElement: 5 findMajorityElementA <<< candidate: 5 main <<< findMajorityElementA: 5 13 3 1 7 1 3 7 3 7 1 7 7 7 7 main <<< n: 13 main <<< arr: [3, 1, 7, 1, 3, 7, 3, 7, 1, 7, 7, 7, 7] main <<< findMajorityElement: 7 findMajorityElementA <<< candidate: 7 main <<< findMajorityElementA: 7 5 1 1 4 4 6 main <<< n: 5 main <<< arr: [1, 1, 4, 4, 6] main <<< findMajorityElement: -1 findMajorityElementA <<< candidate: 6 main <<< findMajorityElementA: -1 4 1 1 3 3 main <<< n: 4 main <<< arr: [1, 1, 3, 3] main <<< findMajorityElement: -1 findMajorityElementA <<< candidate: 1 main <<< findMajorityElementA: -1
The first number is the sequence indicates the number of elements that we will insert in the array. The actual numbers follow. Our program displays the number of elements followed by the contents of the array.
We then display the majority element twice. As we will see shortly, the first display matches a brute force approach that runs in O(n^2) time. The book suggested trying it first to see if some optimization comes to mind. The second message from main if the optimized code than runs in O(n) time. In between we see the majority candidate. Figuring out this value is at the core of the problem. Once we have a candidate we can check it by traversing the array in O(n) time.
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open the scanner ****
Scanner sc = new Scanner(System.in);
// **** read the number of elements in the array ****
int n = sc.nextInt();
// ???? ????
System.out.println("main <<< n: " + n);
// **** read and populate the array ****
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextInt();
// **** close the scanner ****
sc.close();
// ???? ????
System.out.print("main <<< arr: [");
for (int i = 0; i < arr.length; i++) {
if ((i + 1) < arr.length)
System.out.print(arr[i] + ", ");
else
System.out.print(arr[i]);
}
System.out.println("]");
// **** brute force attempt: O(n^2) ****
System.out.println("main <<< findMajorityElement: " + findMajorityElement(arr));
// **** faster attempt: O(n) ****
System.out.println("main <<< findMajorityElementA: " + findMajorityElementA(arr));
}
The test scaffolding does what we previously described. We read the count of elements for the array and then populate it. We display the contents of the array to make sure all is well so far.
We then make a call to the brute force method to determine the majority element. The following line makes a call to the optimized method. I did have a hard time figuring out how to get a majority candidate.
/*
* Find the majority element (if any) in the specified array.
* This code runs in O(n^2) time.
*/
static int findMajorityElement(int[] arr) {
// **** traverse the array looking for the majority value ****
for (int x : arr) {
if (validate(arr, x))
return x;
}
// **** majority not found ****
return -1;
}
This is the brute force method that runs in O(n^2). We traverse the contents of the array, and for each pass we run the validate() method which as we will see in a few, traverses the entire array once per invocation.
/*
* Validate if m is the majority element in the specified array.
* This method runs in O(n) time.
*/
static Boolean validate(int[] arr, int m) {
// **** initialize the count ****
int count = 0;
// **** traverse the array counting the number of times m is present ****
for (int i : arr) {
if (i == m)
count++;
}
// **** return true if m is the majority element ****
return (count > (arr.length / 2) ? true : false);
}
The validate() method initializes a count and loops through the array counting the occurrences of the specified value. If the value is present in more than half of the array entries, then the method returns true to indicate we have a majority element.
/*
* Find the majority element (if any) in the specified array.
* This code runs in O(n) time.
*/
static int findMajorityElementA(int[] arr) {
// **** get candidate in O(n) time ****
int candidate = getCandidate(arr);
// ???? ????
System.out.println("findMajorityElementA <<< candidate: " + candidate);
// **** validate in O(n) time ****
return validate(arr, candidate) ? candidate : -1;
}
The findMajorityElementA() method first gets a majority candidate in O(n) time. As mentioned this is the key to solving this problem. Once we get the candidate we need to verify it is valid. This is performed in O(n) time.
/*
* Get a majority candidate from the specified array.
* This method runs in O(n) time.
*/
static int getCandidate(int[] arr) {
int candidate = 0;
int count = 0;
// **** traverse the array ****
for (int n : arr) {
// **** set a new candidate (if needed) ****
if (count == 0) {
candidate = n;
}
// **** update the count based on the this array value ****
if (n == candidate)
count++;
else
count--;
}
// **** return a candidate ****
return candidate;
}
The getCandidate() method initializes a couple variable. We then traverse the array once. If the count is set to 0 we flag that the current value is a majority candidate. We then increment or decrement the count. Since the majority candidate is the number that occurs the most times in the array, when we are done traversing the array we should have the value that occurs the most in the candidate variable.
I did not use the white board to solve this problem. I just used several pages on my paper tablet. I will remember to use the white board and Visual Studio code for the next post.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa