4546474849505152

package main

import "fmt"

// majorityElementTwo finds majority elements in an array
func majorityElementTwo(nums []int) []int {
    // Size of the array
    n := len(nums)

    // List of answers
    result := []int{}

    for i := 0; i < n; i++ {
        /* Checking if nums[i] is not 
           already part of the answer */
        if len(result) == 0 || result[0] != nums[i] {
            cnt := 0
            // counting the frequency of nums[i]
            for j := 0; j < n; j++ {
                if nums[j] == nums[i] {
                    cnt++
                }
            }
            // check if frequency is greater than n/3
            if cnt > n/3 {
                result = append(result, nums[i])
            }
        }

        // if result size is equal to 2 break out of loop
        if len(result) == 2 {
            break
        }
    }

    // return the majority elements
    return result
}

func main() {
    arr := []int{11, 33, 33, 11, 33, 11}

    ans := majorityElementTwo(arr)

    // Print the majority elements found
    fmt.Print("The majority elements are: ")
    for _, it := range ans {
        fmt.Printf("%d ", it)
    }
    fmt.Println()
}

Complexity Analysis

Time Complexity: O(N²), where N is the size of the array. As for every element of the array the inner loop runs for N times.

Space Complexity: O(1) the space used is so small that it can be considered constant.1d:T3fb8,

Intuition

A better idea is to use a data structure to reduce the number of look-up operations and hence to reduce the time complexity. Moreover, we have been calculating the count of the same element again and again, so reduce that also.

Approach

Use a hashmap and store the elements as pairs. (Can also use frequency array based on the size of nums). Here the key will be the element of the array and the value will be the number of times it occurs.

Traverse the whole array and update the occurrence of each element.

After that, check the map if the value for any element is greater than the floor of N/3. If yes, include it in the answer. Else, iterate forward. At any point if we find that the size of answer array is 2, break out of the loop. Finally, return the answer.

123456789101112131415161718192021222324252627282930313233