I like to read this solution as a small machine: keep the useful information, throw away the noise. For 169. Majority Element, the solution in this repository is mainly a binary search solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: binary search, two pointers, prefix sums, bit manipulation.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are majorityElement, countInRange, majorityElementRec.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(nlgn)O(nlgn)
- Space: O(1)O(1) or (O(n)O(n))
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
03
04You may assume that the array is non-empty and the majority element always exist in the array.
05
06Example 1:
07
08Input: [3,2,3]
09Output: 3
10Example 2:
11
12Input: [2,2,1,1,1,2,2]
13Output: 2
14**/
15
16//Runtime: 24 ms, faster than 61.49% of C++ online submissions for Find Common Characters.
17//Memory Usage: 10.9 MB, less than 100.00% of C++ online submissions for Find Common Characters.
18class Solution {
19public:
20 int majorityElement(vector<int>& nums) {
21 map<int, int> count;
22
23 for(int e : nums){
24 if(count.find(e)==count.end()){
25 count[e] = 1;
26 }else{
27 count[e] += 1;
28 }
29 }
30
31 for(map<int, int>::iterator it=count.begin();it!=count.end();it++){
32 if(it->second > nums.size()/2){
33 return it->first;
34 }
35 }
36
37 return -1;
38 }
39};
40
41/**
42Approach 3: Sorting
43Intuition
44
45If the elements are sorted in monotonically increasing (or decreasing) order,
46the majority element can be found at index \lfloor \dfrac{n}{2} \rfloor⌊2n⌋
47(and \lfloor \dfrac{n}{2} \rfloor + 1⌊2n⌋+1, incidentally, if nn is even).
48
49Algorithm
50For this algorithm, we simply do exactly what is described: sort nums, and return the element in question.
51To see why this will always return the majority element (given that the array has one),
52consider the figure below (the top example is for an odd-length array and the bottom is for an even-length array):
53**/
54
55/**
56Complexity Analysis
57Time complexity : O(nlgn)O(nlgn)
58Sorting the array costs O(nlgn)O(nlgn) time in Python and Java, so it dominates the overall runtime.
59Space complexity : O(1)O(1) or (O(n)O(n))
60We sorted nums in place here - if that is not allowed,
61then we must spend linear additional space on a copy of nums and sort the copy instead.
62**/
63
64//Runtime: 28 ms, faster than 43.39% of C++ online submissions for Find Common Characters.
65//Memory Usage: 11.1 MB, less than 96.02% of C++ online submissions for Find Common Characters.
66/**
67class Solution {
68public:
69 int majorityElement(vector<int>& nums) {
70 sort(nums.begin(), nums.end());
71 return nums[nums.size()/2];
72 }
73};
74**/
75
76/**
77Approach 5: Divide and Conquer
78Intuition
79
80If we know the majority element in the left and right halves of an array,
81we can determine which is the global majority element in linear time.
82
83Algorithm
84
85Here, we apply a classical divide & conquer approach that recurses on the left and right halves of an array
86until an answer can be trivially achieved for a length-1 array.
87Note that because actually passing copies of subarrays costs time and space,
88we instead pass lo and hi indices that describe the relevant slice of the overall array.
89In this case, the majority element for a length-1 slice is trivially its only element,
90so the recursion stops there. If the current slice is longer than length-1,
91we must combine the answers for the slice's left and right halves.
92If they agree on the majority element, then the majority element for the overall slice is obviously the same[^1].
93If they disagree, only one of them can be "right",
94so we need to count the occurrences of the left and right majority elements to determine which subslice's answer is globally correct.
95The overall answer for the array is thus the majority element between indices 0 and nn.
96**/
97
98/**
99Complexity Analysis
100
101Time complexity : O(nlgn)O(nlgn)
102
103Each recursive call to majority_element_rec performs two recursive calls on subslices of size \frac{n}{2}
1042n and two linear scans of length nn.
105Therefore, the time complexity of the divide & conquer approach can be represented by the following recurrence relation:
106T(n) = 2T(\frac{n}{2}) + 2n T(n)=2T(2n)+2n
107By the master theorem, the recurrence satisfies case 2, so the complexity can be analyzed as such:
108\begin{aligned} T(n) &= \Theta(n^{log_{b}a}\log n) \\ &= \Theta(n^{log_{2}2}\log n) \\ &= \Theta(n \log n) \\ \end{aligned}
109T(n)=Θ(n log b alogn)=Θ(n log 2 2logn)=Θ(nlogn)
110Space complexity : O(lgn)O(lgn)
111
112Although the divide & conquer does not explicitly allocate any additional memory,
113it uses a non-constant amount of additional memory in stack frames due to recursion.
114Because the algorithm "cuts" the array in half at each level of recursion,
115it follows that there can only be O(lgn)O(lgn) "cuts" before the base case of 1 is reached.
116It follows from this fact that the resulting recursion tree is balanced,
117and therefore all paths from the root to a leaf are of length O(lgn)O(lgn).
118Because the recursion tree is traversed in a depth-first manner,
119the space complexity is therefore equivalent to the length of the longest path,
120which is, of course, O(lgn)O(lgn).
121**/
122
123//TLE
124/**
125class Solution {
126public:
127 int countInRange(vector<int>& nums, int num, int lo, int hi){
128 int count = 0;
129 for(int e : nums){
130 if(e==num) count++;
131 }
132 return count;
133 }
134
135 int majorityElementRec(vector<int>& nums, int lo, int hi){
136 if(lo == hi) return nums[lo];
137
138 int mid = (hi+lo)/2;
139 int left = majorityElementRec(nums, lo, mid);
140 int right = majorityElementRec(nums, mid+1, hi);
141
142 if(left == right) return left;
143
144 int leftCount = countInRange(nums, left, lo, hi);
145 int rightCount = countInRange(nums, right, lo, hi);
146
147 return leftCount > rightCount ? left : right;
148 }
149
150 int majorityElement(vector<int>& nums) {
151 return majorityElementRec(nums, 0, nums.size()-1);
152 }
153};
154**/
155
156/**
157Approach 6: Boyer-Moore Voting Algorithm
158Intuition
159
160If we had some way of counting instances of the majority element as +1+1 and instances of any other element as -1−1,
161summing them would make it obvious that the majority element is indeed the majority element.
162
163Algorithm
164
165Essentially, what Boyer-Moore does is look for a suffix sufsuf of nums where suf[0]suf[0] is the majority element in that suffix.
166To do this, we maintain a count, which is incremented whenever
167we see an instance of our current candidate for majority element and decremented whenever we see anything else.
168Whenever count equals 0, we effectively forget about everything in nums up
169to the current index and consider the current number as the candidate for majority element.
170It is not immediately obvious why we can get away with forgetting prefixes of nums -
171consider the following examples (pipes are inserted to separate runs of nonzero count).
172
173[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
174
175Here, the 7 at index 0 is selected to be the first candidate for majority element.
176count will eventually reach 0 after index 5 is processed, so the 5 at index 6 will be the next candidate.
177In this case, 7 is the true majority element, so by disregarding this prefix,
178we are ignoring an equal number of majority and minority elements -
179therefore, 7 will still be the majority element in the suffix formed by throwing away the first prefix.
180
181[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5]
182
183Now, the majority element is 5 (we changed the last run of the array from 7s to 5s), but our first candidate is still 7.
184In this case, our candidate is not the true majority element,
185but we still cannot discard more majority elements than minority elements
186(this would imply that count could reach -1 before we reassign candidate, which is obviously false).
187
188Therefore, given that it is impossible (in both cases) to discard more majority elements than minority elements,
189we are safe in discarding the prefix and attempting to recursively solve the majority element problem for the suffix.
190Eventually, a suffix will be found for which count does not hit 0,
191and the majority element of that suffix will necessarily be the same as the majority element of the overall array.
192**/
193
194//Runtime: 20 ms, faster than 98.96% of C++ online submissions for Find Common Characters.
195//Memory Usage: 11 MB, less than 99.34% of C++ online submissions for Find Common Characters.
196/**
197Complexity Analysis
198
199Time complexity : O(n)O(n)
200
201Boyer-Moore performs constant work exactly nn times, so the algorithm runs in linear time.
202
203Space complexity : O(1)O(1)
204
205Boyer-Moore allocates only constant additional memory.
206**/
207
208/**
209class Solution {
210public:
211 int majorityElement(vector<int>& nums) {
212 int count = 0;
213 int candidate = 0;
214
215 for(int num : nums){
216 if(count == 0){
217 candidate = num;
218 }
219 count += (num == candidate) ? 1 : -1;
220 }
221
222 return candidate;
223 }
224};
225**/Cost
Complexity
Time
O(nlgn)O(nlgn)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(1)O(1) or (O(n)O(n))
Auxiliary state plus the answer structure where the problem requires one.