In this post we will attempt to solve LeetCode 169. Majority Element problem using Java.
Given an array nums of size n, return the majority element. The majority element is the element that appears more than floor(n / 2) times. You may assume that the majority element always exists in the array. Constraints: o n == nums.length o 1 <= n <= 5 * 10^4 o -2^31 <= nums[i] <= 2^31 - 1 Related Topics: o Array o Hash Table o Divide and Conquer o Sorting o Counting
We are given an int[] array and we must return the majority element. There are several variations of this problem. I believe we have solved a couple in this post.
If interested in this problem please visit the LeetCode web site and get the latest version of the requirements before attempting a solution.
In this post I will solve the problem using the Java programming language and the VSCode IDE on a Windows platform. The simplest way is to solve the problem using the online IDE provided by LeetCode.
Since I am developing the code on my computer, I will need to generate test code to read the input data, populate the necessary argument, call the function of interest and display the result. Please note that the test scaffold IS NOT PART OF THE SOLUTION!
public int majorityElement(int[] nums) {
}
The signature for the function of interest takes as argument a single int[] array `nums`. It should return the majority element as defined in the requirements.
3,2,3 main <<< nums: [3, 2, 3] main <<< majorityElement0: 3 main <<< majorityElement1: 3 main <<< majorityElement: 3 2,2,1,1,1,2,2 main <<< nums: [2, 2, 1, 1, 1, 2, 2] main <<< majorityElement0: 2 main <<< majorityElement1: 2 main <<< majorityElement: 2 1 main <<< nums: [1] main <<< majorityElement0: 1 main <<< majorityElement1: 1 main <<< majorityElement: 1 3,5,1,2,2,3,4,3,3,3,3 main <<< nums: [3, 5, 1, 2, 2, 3, 4, 3, 3, 3, 3] main <<< majorityElement0: 3 main <<< majorityElement1: 3 main <<< majorityElement: 3 1,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4 main <<< nums: [1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4] main <<< majorityElement0: 3 main <<< majorityElement1: 3 main <<< majorityElement: 3
The test samples are separated by two blank lines.
The first line represents the input. It holds the integer values to populate the `nums` array. Our test scaffold reads the input line, populates and displays the `nums` array. Displaying the `nums` array allows us to verify that all is well so far.
Our test scaffold seems to call three implementations of the function of interest. Each displays the majority element.
/**
* Test scaffold
* !!! NOT PART OF SOLUTION !!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read int[] nums ****
int[] nums = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
// **** call function of interest and display result ****
System.out.println("main <<< majorityElement0: " + majorityElement0(nums));
// **** call function of interest and display result ****
System.out.println("main <<< majorityElement1: " + majorityElement1(nums));
// **** call function of interest and display result ****
System.out.println("main <<< majorityElement: " + majorityElement(nums));
}
There is not much to add to the description of the test scaffold.
/**
* Given an array nums of size n, return the majority element.
*
* Execution: O(n) - Space: O(n)
*
* 47 / 47 test cases passed.
* Status: Accepted
* Runtime: 8 ms
* Memory Usage: 44.7 MB
* @return
*/
static public Integer majorityElement0(int[] nums) {
// **** sanity check ****
if (nums.length == 1) return nums[0];
// **** initialization ****
int floor = nums.length / 2;
HashMap<Integer, Integer> freqs = new HashMap<>();
// **** populate freqs hashmap - O(n) ****
for (int key : nums) {
Integer val = freqs.putIfAbsent(key, 1);
if (val != null) {
// **** check if done ****
if (++val > floor) return key;
// **** ****
freqs.put(key, val);
}
}
// **** iterate through the entry set populating the list - O(n) ****
for (Entry<Integer, Integer> e : freqs.entrySet()) {
if (e.getValue() > floor) return e.getKey();
}
// **** something went wrong ****
return -1;
}
In this implementation of the function of interest we use a hashmap to keep track of the frequencies for the integers in the `nums` array.
The hashmap is populated with the contents of the `nums` array. Note that in the associated loop we check if the floor value is reached. If so we exit the function returning the majority element.
After the loop we iterate through the entry set. We should have found the majority element while populating the hashmap. As you can see, if the value is not found in the last loop, our function returns a -1 to indicate there was an issue.
Please check the comments section of this function for runtime statistics. Let’s see if we can improve on the next implementation of the function of interest.
/**
* Given an array nums of size n, return the majority element.
*
* 47 / 47 test cases passed.
* Status: Accepted
* Runtime: 2 ms
* Memory Usage: 54.6 MB
*/
static public Integer majorityElement1(int[] nums) {
// **** sanity check ****
if (nums.length == 1) return nums[0];
// **** initialization ****
int floor = nums.length / 2;
int n1 = Integer.MIN_VALUE;
int c1 = 0;
int n2 = Integer.MIN_VALUE;
int c2 = 0;
// **** ****
for (int num : nums) {
// **** increment count for n1 ****
if (num == n1) {
c1++;
if (c1 > floor) return n1;
}
// **** increment count for n2 ****
else if (num == n2) {
c2++;
if (c2 > floor) return n2;
}
// **** replace n1 with num and start counting ****
else if (c1 == 0) {
n1 = num;
c1 = 1;
}
// **** replace n2 with num and start counting ****
else if (c2 == 0) {
n2 = num;
c2 = 1;
}
// **** decrement both counters ****
else {
c1--;
c2--;
}
}
// **** ****
if (c1 > c2) return n1;
else return n2;
}
In this pass we will not use a hashmap. The approach is similar to the one we used in the post in this blog LeetCode 229. Majority Element II in Java.
We traverse the `nums` int[] array and keep track of the two top values and their associated counts. In this problem we need to keep track of a single value only.
Please take a look at the comments section in this implementation of the function of interest to see the runtime statistics. We improved but we know we could possibly do somewhat better.
/**
* Given an array nums of size n, return the majority element.
*
* 47 / 47 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 45.2 MB
*
* Runtime: 1 ms, faster than 99.90% of Java online submissions.
* Memory Usage: 45.2 MB, less than 32.83% of Java online submissions.
*/
static public Integer majorityElement(int[] nums) {
// **** number of elements in nums ****
int n = nums.length;
// **** sanity check ****
if (n == 1) return nums[0];
// **** initialization ****
int n1 = nums[0];
int c1 = 1;
// **** traverse nums array ****
for (int i = 1; i < n; i++) {
// **** increment count for n1 ****
if (nums[i] == n1)
c1++;
// **** decrement counter ****
else
c1--;
// **** replace n1 with num and start counting ****
if (c1 == 0) {
n1 = nums[i];
c1 = 1;
}
}
// **** ****
return n1;
}
In this implementation we use a similar approach but we only keep track of the highest value and associated count.
For performance information please take a look at the comments section of the third implementation of the function of interest.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named MajorityElement.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John