169 Majority Element

Given an array of integers, your task is to identify the number that appears more than half the time in the array.

You can assume that such a majority element always exists in the input.

---

Input

• An array nums containing n integers.

---

Output

• Return the element that occurs more than n / 2 times.

---

Example

Input:

nums = [3,2,3]

Output:

3

---

Constraints

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9
• The majority element always exists in the array.

Boyer-Moore Voting Solution

The Boyer-Moore Voting Algorithm is used to find the majority element in a list.

• The idea is to cancel out different elements.
• Start with count = 0 and no candidate.
• If count is 0, choose the current number as the new candidate.
• If the current number equals the candidate, increment count.
• Otherwise, decrement count.
• In the end, the candidate is the majority element (guaranteed to exist by the problem).

This algorithm runs in O(n) time and O(1) space.

This works only if a majority element is guaranteed to exist.

Time Complexity: O(n)
Space Complexity: O(1)

JavaScript

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

TypeScript

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

The count-based solution

The count-based solution uses a map (or object/dictionary) to count the frequency of each element.

Steps:

1. Initialize an empty map to store counts of each number.
2. Iterate through the array:

• For each number, increment its count in the map.
• After updating, check if the count exceeds ⌊n / 2⌋.
• If it does, return that number immediately.

3. If the loop finishes (which won’t happen in this problem since a majority always exists), return the number with the maximum count.

Time Complexity: O(n) Space Complexity: O(n)

JavaScript

var majorityElement = function(nums) {
    let count = {}
    let majority = Math.floor(nums.length / 2) 
    for(let num of nums) {
        let curCount = (count[num] || 0) + 1
        if(curCount > majority) {
            return num
        }
        count[num] = curCount
    }
    return -1
};

TypeScript

function majorityElement(nums: number[]): number {
    let count: Record<number, number> = {}
    let majority = Math.floor(nums.length / 2)
    for(let num of nums) {
        let curCount = (count[num] || 0) + 1
        if(curCount > majority) {
            return num
        }
        count[num] = curCount
    }
    return -1
};