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.

It works in linear time O(n) and constant space O(1).

The algorithm is based on the fact that if an element appears more than n/2 times,

it will survive all the "cancellations" against other elements.

Here's how it works step by step:

1. Initialize a count to 0 and a variable candidate to store the potential majority.
2. Iterate through the array:

• If count is 0, assign the current number as the candidate.
• If the current number equals the candidate, increase the count by 1.
• Otherwise, decrease the count by 1.

3. After the loop ends, the candidate will be the majority element.

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

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

Java

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

Kotlin

class Solution {
    fun majorityElement(nums: IntArray): Int {
        var candidate = 0
        var count = 0
        for(num in nums) {
            if(count == 0) {
                candidate = num
            }
            count += if(candidate == num) 1 else -1
        }
        return candidate
    }
}

Scala

object Solution {
    def majorityElement(nums: Array[Int]): Int = {
        var count = 0
        var candidate = 0
        for(num <- nums) {
            if(count == 0) {
                candidate = num
            }
            count += (if(candidate == num) 1 else -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)

This approach is simple and works for all cases, also it can find out if majority exists.

class Solution {
    public int majorityElement(int[] nums) {
        var count = new HashMap<Integer, Integer>();
        var majority = nums.length / 2;
        for(var num : nums) {
            var curCount = count.getOrDefault(num, 0) + 1;
            if(curCount > majority) {
                return num;
            }
            count.put(num, curCount);
        }
        return -1;
    }
}

Kotlin

class Solution {
    fun majorityElement(nums: IntArray): Int {
        val count = mutableMapOf<Int, Int>()
        val majority = nums.size / 2
        for(num in nums) {
            val curCount = count.getOrDefault(num, 0) + 1
            if(curCount > majority) {
                return num
            }
            count[num] = curCount
        }
        return -1
    }
}