Find the Majority Element that occurs more than N/2 times

[Question] Find the Majority Element in an given array that occurs more than N/2 times

Approach #1 Brute-force

Use two loop and compare each elements with rest if it matches increment the counter

// TC: O(n*2)
// SC: O(1)
func majorityElement(arr: inout [Int]) -> Int {
    // Size of the given array
    let n = arr.count

    for i in 0..<n {
        // Selected element is arr[i]
        var cnt = 0
        for j in 0..<n {
            // Counting the frequency of arr[i]
            if arr[j] == arr[i] {
                cnt+=1
            }
        }
        
        // Check if frequency is greater than n/2
        if (cnt > n/2) {
            return arr[i]
        }
    }

    return -1
}

Approach #2 : Optimal Approach: Moore’s Voting Algorithm

 Basically, we are trying to keep track of the occurrences of the majority element and minority elements dynamically. if the count becomes 0 as the occurrence of Element and the occurrence of the other elements are the same. So, they canceled each other. The element with the most occurrence will remain and the rest will cancel themselves.

func majorityElementMooreVoting(arr: inout [Int]) -> Int {
    // Size of the given array
    let n = arr.count
    var cnt = 0 // Count
    var el = 0 // Element

    // Applying the algorithm
    for i in 0..<n {
        if cnt == 0 {
            cnt = 1
            el = arr[i]
        } else if el == arr[i] {
            cnt+=1
        } else {
            cnt-=1
        }
    }

    // Checking if the stored element is the majority element
    var cnt1 = 0
    for i in 0..<n where arr[i] == el {
        cnt1+=1
    }

    if (cnt1 > n / 2) {
        return el
    }
    return -1
}

var majorityArr = [2, 2, 1, 1, 1, 2, 2]
let ansMajority = majorityElementMooreVoting(arr: &majorityArr)
print("The majority element is:", ansMajority)