Blogs Hub

by Sumit Chourasia | Nov 18, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

Majority Element II - Array - Medium - LeetCode

Majority Element II - Array - Medium - LeetCode

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Follow-up: Could you solve the problem in linear time and in O(1) space?

 

Example 1:

Input: nums = [3,2,3]
Output: [3]
Example 2:

Input: nums = [1]
Output: [1]
Example 3:

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

Constraints:

1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109

public class Solution {
    public IList<int> MajorityElement(int[] nums) {
        var result = new List<int>();
        if(nums.Length == 0 ){
            return result;
        }
        
        int number1 = nums[0];
        int number2 = nums[0];
        int count1 = 0;
        int count2 = 0;
        int len = nums.Length;
        
        for(int i=0;i<len;i++){
            if(nums[i]==number1){
                count1++;
            }
            else if(nums[i]==number2){
                count2++;
            }
            else if(count1==0){
                number1 = nums[i];
                count1 = 1;
            }
            else if(count2==0){
                number2 = nums[i];
                count2 = 1;
            }
            else{
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for(int i=0;i<len;i++){
            if(nums[i]==number1){
                count1++;
            }
            else if(nums[i]==number2){
                count2++;
            }
        }
        
        if(count1>len/3){
            result.Add(number1);
        }
        
        if(count2>len/3){
            result.Add(number2);
        }
        
        return result;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Contributed By: Sumit Chourasia
Fizz Buzz - List - Easy - LeetCode
Contributed By: Sumit Chourasia
Next Permutation - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Array Nesting - Array - Medium - LeetCode