169. Majority Element

Description

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 exist in the array.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [3, 2, 3]

Output: 3

Example 2

Input: [2, 2, 1, 1, 1, 2, 2]

Output: 2

Solutions

Solution 1

/**
 * Time complexity : O(n^2). The brute force algorithm contains two 
 *    nested for loops that each run for nn iterations, adding up to 
 *    quadratic time complexity.
 * Space complexity : O(1). The brute force solution does not allocate 
 *    additional space proportional to the input size.
 */

class Solution {
    public int majorityElement(int[] nums) {
        int majorityCount = nums.length/2;

        for (int num : nums) {
            int count = 0;
            for (int elem : nums) {
                if (elem == num) {
                    count += 1;
                }
            }

            if (count > majorityCount) {
                return num;
            }

        }

        return -1;    
    }
}

Solution 2

/**
 * Time complexity : O(N)
 * Space complexity : O(N)
 */

class Solution {
    private Map<Integer, Integer> countNums(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
            }
            else {
                counts.put(num, counts.get(num)+1);
            }
        }
        return counts;
    }

    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = countNums(nums);

        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || 
                entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }

        return majorityEntry.getKey();
    }
}

Solution 3

/**
 * Time complexity : O(nlgn). Sorting the array costs O(nlgn) time in Python 
 *    and Java, so it dominates the overall runtime.
 * Space complexity : O(1) or (O(n)). We sorted nums in place here - if that 
 *    is not allowed, then we must spend linear additional space on a copy 
 *    of nums and sort the copy instead.
 */

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

Solution 4

/**
 * Time complexity : O(n). Boyer-Moore performs constant work exactly n 
 *    times, so the algorithm runs in linear time.
 * Space complexity : O(1). Boyer-Moore allocates only constant additional memory.
 */

class Solution {
    public int majorityElement(int[] nums) {
        int result = 0, count = 0;
        
        for(int n: nums) {
            if(count == 0) {
                result = n;
                count = 1;
            } else if(result == n) {
                count++;
            } else {
                count--;
            }
        }
        return result;
    }
}

Follow up