iOS Interview - Leetcode 169. Majority Element

May 28, 2024 • 1 min read • #swift, #interview, #leetcode

Primary idea: Boyer-Moore Majority Voting Algorithm
Time Complexity: O(n), As two traversal of the array, is needed, so the time complexity is linear.
Space Complexity: O(1), As no extra space is required.

func majorityElement(_ nums: [Int]) -> Int {
    var count = 0, candidate = 0

    for num in nums {
        if count == 0 {
            candidate = num
        }

        count += (candidate == num) ? 1 : -1
    }

    return candidate
}

majorityElement([3,2,3]) // 3
majorityElement([2,2,1,1,1,2,2]) // 2
majorityElement([3, 3, 4, 2, 4, 4, 2, 4, 4]) // 4

Further reading: