Java O(n) Easy To Understand, Optimal O(1) Space Solution


  • 0
    B

    Explanation
    There are many ways to solve this problem such as sorting nums and returning nums[n/2], using a dictionary to store the frequency of each distinct integer in nums, but I will show you a way to solve this problem that runs strictly in O(n) with O(1) space.

    /* Simple Example */
    
    /* We start off with a simple example to illustrate the code's logic */
    int [] nums = { 2, 1, 2, 2 };
    
    /* 1. Set majorityElementSoFar to be nums[0], which is 2, count to be 1. */
    int majorityElementSoFar = nums[0]; // 2
    int count = 1;
     
    /* 2. Check nums[1]. Since is NOT equal to majorityElementSoFar AND
     *      count - 1 would be 0, we need to set majorityElementSoFar to be 
     *      nums[1], which is 1.
     */
    assert(nums[1] != majorityElementSoFar && count - 1 == 0);
    majorityElementSoFar = nums[1]; // 1
    
    /* 3. Check nums[2]. Since it is NOT equal to majorityElementSoFar AND
     *     count - 1 would be 0, we need to set majortyElementSoFar to be
     *     nums[2], which is 2.
     */
    assert(nums[2] != majorityElementSoFar && count - 1 == 0);
    majorityElementSoFar = nums[2]; // 2
    
    /* 4. Check nums[3]. Since it IS equal to majorityElementSoFar, we 
     *    increment count by 1.
    */
    assert(nums[3] == majorityElementSoFar);
    count++;
    
     /* 5. Return majorityElementSoFar as our solution. */
    return majorityElementSoFar; // 2
    

    The idea behind this solution is take advantage of the fact that the majority element appears more than ⌊ n/2 ⌋ times. As long as we keep track of the majority element so far, with the help of a count variable, regardless of how many times majoritySoFar is reset again and again, we are guaranteed to have majorityElementSoFar equal to the actual majority element by the end.

    Time Complexity
    The time complexity is O(n) where n is the number of elements in input nums, since we scan through every element in nums once.

    class Solution {
        public int majorityElement(int[] nums) {
            // Initially set the first element of nums to be majority
            int majorityElementSoFar = nums[0];
            int count = 1;
            
            // Scan sequentially from the second element onwards
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == majorityElementSoFar) {
                    count++;
                } 
                // Need to set a new majorityElementSoFar
                else if (count == 1) {
                    majorityElementSoFar = nums[i];
                } 
                // Decrement count with no repercussions
                else {
                    count--;
                }
            }
            return majorityElementSoFar;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.