Majority element in an array

Given an array of size n, find the majority element. The majority element is the element that appears more than n/2 times. You may assume that the array is non-empty and the majority element always exists in the array.

Input-Output Examples

Example 1:

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

Example 2:

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

Approach:

Technique: Boyer-Moore Voting Algorithm

  1. Initialization: Start by initializing two variables: candidate and count. Set candidate to None and count to 0.

  2. Finding the Candidate:

    • Iterate through each element in the array.
    • If count is 0, set the current element as the candidate.
    • If the current element is the same as the candidate, increment count by 1.
    • If the current element is different from the candidate, decrement count by 1.

C++ Program to find the majority element in an array

cpp
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0, count = 0;
        // Finding the candidate
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
    cout << "Majority Element: " << sol.majorityElement(nums) << endl;
    return 0;
}

Java Program to find the majority element in an array

java
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        System.out.println("Majority Element: " + sol.majorityElement(nums));
    }
}

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0, count = 0;
        // Finding the candidate
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

Python Program to find the majority element in an array

python
from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate, count = 0, 0
        # Finding the candidate
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate

if __name__ == "__main__":
    sol = Solution()
    nums = [2, 2, 1, 1, 1, 2, 2]
    print(f"Majority Element: {sol.majorityElement(nums)}")

Explanation

Finding the Candidate

  1. Initialization:
    • candidate is initially set to None or 0.
    • count is set to 0.
  2. Iterate through the array:
    • For each element in the array:
      • If count is 0, set the current element as candidate.
      • If the current element is equal to candidate, increment count.
      • If the current element is different, decrement count.

The Boyer-Moore Voting Algorithm is efficient with a time complexity of O(n) and a space complexity of O(1), making it an optimal solution for finding the majority element in an array.

DSA

7945

435

Related Articles