algoadvance

Leetcode 169. Majority Element

Problem Statement

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Clarifying Questions

  1. Can the input array contain negative numbers or only positive numbers?
    • The problem statement does not restrict the array to positive numbers only, so it can contain negative numbers as well.
  2. Is the input array always non-empty?
    • Yes, as per the problem statement, we can assume the input array is always non-empty.
  3. What should be returned if there are multiple elements that meet the majority requirement?
    • There can only be one element which is the majority element as per the problem definition (appears more than ⌊n / 2⌋ times).

Strategy

There are multiple ways to solve this problem, but one of the most efficient methods is the Boyer-Moore Voting Algorithm. This algorithm operates in linear time O(n) and requires constant space O(1).

The Boyer-Moore Voting Algorithm works as follows:

  1. Maintain a candidate for the majority element and a count.
  2. Initialize candidate as nums[0] and count as 1.
  3. Iterate through the array starting from the second element:
    • If count is 0, set the current element as the candidate and reset count to 1.
    • If the current element is the same as candidate, increment count.
    • Otherwise, decrement count.
  4. The candidate at the end of iteration will be the majority element.

Code

public class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 1;

        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2,2,1,1,1,2,2};
        System.out.println(sol.majorityElement(nums));  // Output: 2
    }
}

Time Complexity

This approach ensures that we find the majority element efficiently with minimal use of resources.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI