If you’re preparing for coding interviews or just looking to sharpen your programming skills, LeetCode is an invaluable resource. One of the interesting challenges you might encounter is “Majority Element II”. In this blog, we’ll break down the problem, discuss the solution approach, and walk through the Java code implementation.
Problem Description
The Majority Element II problem on LeetCode asks us to find all elements that appear more than ⌊n/3⌋ times in a given array of integers, where ⌊n/3⌋ denotes the floor function that rounds down to the nearest integer. The challenge is to solve this problem in linear time and constant space.
Solution Approach
To solve this problem efficiently, we’ll use a variation of the Boyer-Moore Voting Algorithm. This algorithm is particularly useful for finding majority elements in an array with a time complexity of O(n) and a space complexity of O(1).
Steps to Solve the Problem
- Finding Potential Candidates:
- We can have at most two majority elements in an array since an element needs to appear more than ⌊n/3⌋ times.
- We iterate through the array while maintaining two potential candidates and their respective counts.
- Validating the Candidates:
- After identifying potential candidates, we iterate through the array again to confirm if they actually appear more than ⌊n/3⌋ times.
Java Implementation
Here’s how you can implement the solution in Java:
import java.util.ArrayList;
import java.util.List;
public class MajorityElementII {
public List majorityElement(int[] nums) {
List result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
int candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;
// Step 1: Find potential candidates
for (int num : nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
} else if (count1 == 0) {
candidate1 = num;
count1 = 1;
} else if (count2 == 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
// Step 2: Validate the candidates
count1 = 0;
count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;
else if (num == candidate2) count2++;
}
int n = nums.length;
if (count1 > n / 3) result.add(candidate1);
if (count2 > n / 3) result.add(candidate2);
return result;
}
public static void main(String[] args) {
MajorityElementII solution = new MajorityElementII();
int[] nums = {3, 2, 3, 2, 2, 1, 1, 1};
System.out.println("Majority Elements are: " + solution.majorityElement(nums));
}}
Explanation of the Code
- Finding Potential Candidates:
- We iterate through the array to identify two potential candidates. We increase the count if the current number matches one of the candidates. If the count for a candidate drops to zero, we update the candidate.
- Validating the Candidates:
- We reset the counts and iterate through the array again to confirm the counts of the two candidates. If they appear more than ⌊n/3⌋ times, we add them to the result list.
Conclusion
The Majority Element II problem on LeetCode is an excellent way to practice advanced array manipulation and understand the Boyer-Moore Voting Algorithm. By implementing this algorithm in Java, you can solve the problem efficiently with a time complexity of O(n) and a space complexity of O(1).
LeetCode problems like these not only enhance your coding skills but also prepare you for technical interviews. Happy coding!
Read More …
Solving the Square of a Rotated Array Problem – https://kamleshsingad.com/solving-the-square-of-a-rotated-array-problem/
Differences Between Arrays and Strings in Java – https://kamleshsingad.com/differences-between-arrays-and-strings-in-java/
Mastering Bit Manipulation: Squaring a Number Using Bitwise Operations in Java – https://kamleshsingad.com/mastering-bit-manipulation-squaring-a-number-using-bitwise-operations-in-java/
