In this blog post, we’ll explore a classic problem from LeetCode called “Majority Element.” This problem is a popular interview question and serves as a great exercise in understanding efficient algorithms and data structures. We’ll discuss the problem statement, various approaches to solve it, and provide a detailed Java solution.

Problem Statement

The “Majority Element” problem is defined as follows:

For example:

• Input: nums = [3, 2, 3]
• Output: 3
• Input: nums = [2, 2, 1, 1, 1, 2, 2]
• Output: 2

Approaches to Solve the Problem

There are multiple ways to solve this problem. Let’s explore three popular approaches: using a hash map, sorting, and the Boyer-Moore Voting Algorithm.

1. Using a Hash Map

A straightforward approach is to use a hash map to count the occurrences of each element. Then, we find the element with the maximum count.

import java.util.HashMap;
import java.util.Map;

public class MajorityElement {
public int majorityElement(int[] nums) {
Map countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
if (countMap.get(num) > nums.length / 2) {
return num;
}
}
return -1; // This line will never be reached since we assume a majority element always exists
}
}

2. Sorting

Another approach is to sort the array. Since the majority element appears more than half the time, it will be at the middle index of the sorted array.

import java.util.Arrays;

public class MajorityElement {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}

3. Boyer-Moore Voting Algorithm

The Boyer-Moore Voting Algorithm is an efficient solution with O(n) time complexity and O(1) space complexity. It works by maintaining a count that is incremented and decremented based on the current candidate.

public class MajorityElement {
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;

    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }

    return candidate;
}

}

Detailed Java Solution Using Boyer-Moore Voting Algorithm

Let’s delve into the Boyer-Moore Voting Algorithm, which is the most efficient approach among the three.

Step-by-Step Explanation

1. Initialization: Start with an initial count of 0 and no candidate.
2. Iterate Through the Array: For each element in the array:
   • If the count is 0, set the current element as the candidate.
   • Increment the count if the current element is the candidate, otherwise decrement the count.
3. Return the Candidate: By the end of the array, the candidate will be the majority element.

Complete Code

public class MajorityElement {
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;

    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }

    return candidate;
}

public static void main(String[] args) {
    MajorityElement solution = new MajorityElement();
    int[] nums1 = {3, 2, 3};
    int[] nums2 = {2, 2, 1, 1, 1, 2, 2};

    System.out.println("Majority element in [3, 2, 3]: " + solution.majorityElement(nums1));
    System.out.println("Majority element in [2, 2, 1, 1, 1, 2, 2]: " + solution.majorityElement(nums2));
}

}

Conclusion

The Boyer-Moore Voting Algorithm is a powerful method to find the majority element with optimal time and space complexity. While other methods like using a hash map or sorting are also viable, the Boyer-Moore algorithm stands out for its efficiency. Understanding and implementing such algorithms not only helps in solving the problem but also enhances your problem-solving skills for more complex scenarios.

Read More …

Napoleon Cake Data Structure: A Delicious Approach to Understanding Stacks – https://kamleshsingad.com/napoleon-cake-data-structure-a-delicious-approach-to-understanding-stacks/

Optimizing SQL Queries for Performance: Best Practices –https://kamleshsingad.com/4582-2optimizing-sql-queries-for-performance/

Solving the Relatively Prime Problem – https://kamleshsingad.com/solving-the-relatively-prime-problem/