Majority Element II

main.md

Approach

1. A loop is run to go through each number.
2. A map is used to check if the number is seen for the first time , if it has not been then the loop skips to the next number.
3. if a number is seen for the first time a second inner loop is run to check which other number in the array is the same as the current number.
4. the size of the duplicate numbers are tracked and if size > n / 3 then i add the number to the results array.

Complexity

• Time complexity: O(N^2)

• Space complexity: O(N)

Code

function majorityElement(nums: number[]): number[] {
    let n = nums.length
    let result: number[] = []
    let seen = new Map()

    for (let i = 0; i < n; i++) {
        let j = 0
        let size = 0
        if (seen.has(nums[i])) continue

        seen.set(nums[i], nums[i])
        
        while (j < n) {
            if (nums[i] === nums[j]) {
                size++
            }
            j++
        }
        if (size > n / 3) result.push(nums[i])

    }
    return result
};