229. Majority Element II

Description

Given an integer array nums, find all elements that appear more than n/3 times, where n is the size of the array. The task is to return these elements in a list. The solution should ensure that each element in the result list is unique.

Intuition

The problem asks for elements that appear more than n/3 times, where n is the size of the array. Since the majority elements must appear frequently, we can use a counting approach to track occurrences of each element. To ensure that an element appears only once in the result, we can use a flagging mechanism.

Approach

1. Use of Hash Maps: - Use two hash maps (unordered_map in C++): - The first (res2) tracks the frequency of each element in the array. - The second (res) is used to flag elements that have already been added to the result list to avoid duplicates.
2. Iteration: - Loop through each element in the array: - If the element has already been flagged as processed in res, skip further processing for that element. - Otherwise, increment the count of the element in res2. - If the count of the element exceeds n/3, add it to the result list and flag it in res.
3. Return Result: - After processing all elements, return the result list containing all unique elements that appear more than n/3 times.

Complexity

Time Complexity:

O(n), where n is the size of the array. The algorithm iterates through the array once, performing constant-time operations for each element.

Space Complexity:

O(n), due to the additional space used by the two hash maps to store element frequencies and flags.

Code

C++

class Solution {
public:
    vector majorityElement(vector& nums) {
        unordered_map res;
        unordered_map res2;
        vector final;

        for (int i = 0; i < nums.size(); i++) {
            if (res[nums[i]]) continue;

            res2[nums[i]]++;

            if (res2[nums[i]] > nums.size() / 3) {
                res[nums[i]] = true;
                final.push_back(nums[i]);
            }
        }

        return final;
    }
};

// Usage Example
// int main() {
//     Solution sol;
//     vector nums = {3, 2, 3, 4, 2, 2, 2};
//     vector result = sol.majorityElement(nums);
//     for (int num : result) {
//         cout << num << " ";
//     }
//     return 0;
// }

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        res = {}
        res2 = {}
        final = []

        for num in nums:
            if res.get(num):
                continue

            res2[num] = res2.get(num, 0) + 1

            if res2[num] > len(nums) // 3:
                res[num] = True
                final.append(num)

        return final

# Usage Example
# sol = Solution()
# nums = [3, 2, 3, 4, 2, 2, 2]
# result = sol.majorityElement(nums)
# print(result)  # Output: [2]

Java

class Solution {
    public List majorityElement(int[] nums) {
        Map res = new HashMap<>();
        Map res2 = new HashMap<>();
        List finalResult = new ArrayList<>();

        for (int num : nums) {
            if (res.getOrDefault(num, false)) continue;

            res2.put(num, res2.getOrDefault(num, 0) + 1);

            if (res2.get(num) > nums.length / 3) {
                res.put(num, true);
                finalResult.add(num);
            }
        }

        return finalResult;
    }

    // Usage Example
    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     int[] nums = {3, 2, 3, 4, 2, 2, 2};
    //     List result = sol.majorityElement(nums);
    //     System.out.println(result);
    // }
}

JavaScript

var majorityElement = function(nums) {

    let res=[];
    let res2=[];
    let final=[];

    for(let i=0;i (nums.length/3)){
            res[nums[i]] = true;
            final.push(nums[i]);
        };
    }
    return final;
};
``