Explorer
Data Structures & Algorithms

Find the element that appears more than n/2 times in an array.

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.

Examples

Input: nums = [3, 2, 3]

Output: 3

Explanation: 3 appears more than N/2 times in the array.

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

Output: 2

Explanation: 2 appears more than N/2 times in the array.

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: The majority element appears more than floor(n / 2) times. šŸ’” Hint 2: Boyer-Moore Voting Algorithm allows finding this candidate in O(N) time and O(1) space. šŸ’” Hint 3: Maintain a candidate and a count. When count drops to 0, choose the current element as the new candidate.

Editorial & Approach

Problem Overview & Intuition

Using the Boyer-Moore Voting Algorithm, any element occurring more than n/2 times will dominate the cancellation balance against all other elements combined. This guarantees finding the majority element in a single pass with O(1) auxiliary space.

Step-by-Step Approach

  1. Initialize candidate = null and count = 0.
  2. Iterate through each number in nums.
  3. If count === 0, set candidate = num.
  4. If num === candidate, increment count++; otherwise decrement count--.
  5. Return candidate.

Optimal Implementation (JavaScript)

function majorityElement(nums) {
  let candidate = nums[0];
  let count = 0;
  for (let num of nums) {
    if (count === 0) {
      candidate = num;
    }
    count += (num === candidate) ? 1 : -1;
  }
  return candidate;
}

Complexity Analysis

Time Complexity O(N) ā€” single linear scan through nums.
Space Complexity O(1) ā€” constant auxiliary space.

Edge Cases & Corner Traps Handled

  • Array of length 1: returns nums[0].
  • Majority element occurs n times (all identical).
  • Majority element alternating across the array.

Majority Element-I

Medium
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.
Example Scenarios
1Example 1
Input: nums = [3, 2, 3]
Output: 3
Explanation:

3 appears more than N/2 times in the array.

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

2 appears more than N/2 times in the array.

Editor
Loading Editor...
nums =
[3, 2, 3]
Output:Click "Run" above to execute and verify your code here.
3