Daily bit(e) of C++ | Majority element
Today, we will look at a common C++ interview problem: Majority element.
Given an array of integers as std::vector<int>, return the majority element (guaranteed to be present).
A majority element has more than size/2 number of instances in the array.
For example, in the array {1,0,1,1,0,1,0}, the majority element is 1 with 4 instances, and the element 0 has only 3 instances.
There is a solution that runs in O(n) time and O(1) space.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/nvvcPTen1.
0 Comments