Majority element and max subarray

Why this matters

Majority element and maximum subarray are two classic problems that come up in interviews. Each has a short solution that does not use divide and conquer. Majority element can be solved by counting with a hash map, and maximum subarray can be solved with Kadane's algorithm, which walks the array once. This lesson uses divide and conquer anyway, on purpose. The same pattern appears in many harder problems, and these two are small enough to see every step.

By the end of this lesson you will be able to split an array in half, solve each half with the same function, and handle the answers that cross the middle. You will also see why the crossing case needs its own check, and why one of the two problems needs a final check after the recursion has finished.

The merge step from the merge sort lesson uses the same shape. This lesson does not repeat it.

The pattern in three steps

Divide and conquer on an array follows three steps every time.

Split the array into a left half and a right half at the middle index.
Solve the left half and the right half with the same function. That function splits its own piece again, until a piece has one element.
Combine the two answers. For most problems, the combine step must also look at the answers that cross the middle, meaning the answers that use elements from both halves.

The base case is an array with one element. The function can answer that case directly without splitting.

Here is the pattern applied to a tiny array of four numbers, 3 1 4 1.

Split into 3 1 and 4 1.
Split 3 1 into 3 and 1. Each single element is a base case.
Split 4 1 into 4 and 1. Each single element is a base case.
Combine upward. The combine step at each level looks at both halves and at the crossing case.

Each level of splitting cuts the array in half, so an array of n elements has about log2(n) levels. In C++, the function will receive a view of each half. A span is a view of part of an array. It does not copy the numbers, it only points at them and knows how many there are. The std::span type is in the  header, and it needs C++20.

Problem 1: majority element

The majority element of an array of n values is the value that appears more than n / 2 times. Here are three examples.

3 2 3 has majority element 3, because 3 appears 2 times and 2 is more than 3 / 2.
2 2 1 1 1 2 2 has majority element 2, because 2 appears 4 times and 4 is more than 7 / 2.
1 2 3 4 has no majority element, because no value appears more than 2 times.

The simplest correct method counts each value. A hash map can do this in O(n) time, but it needs O(n) extra memory. The divide and conquer method below uses no extra memory beyond the recursion itself.

The key fact

Suppose value x is the majority element of the whole array. Then x must be the majority element of at least one of the two halves.

Here is why. Let the left half have L values and the right half have R values, so the whole array has n = L + R values. If x appeared at most L / 2 times in the left half and at most R / 2 times in the right half, then x would appear at most (L + R) / 2 = n / 2 times in total. But x is the majority, so it appears more than n / 2 times. That is a contradiction, so x must be a majority in at least one half.

This gives a plan. Ask each half for its candidate, which is its majority element if it has one. Then check which of the two candidates can be the whole array's majority. The whole array's majority must be one of the two candidates.

The combine rule

Let left be the candidate from the left half and right be the candidate from the right half. The combine step works like this.

If left and right are the same value, that value is the candidate for the whole array.
If they differ, count how many times left appears in the whole array. If it appears more than n / 2 times, it is the candidate.
Otherwise, the candidate is right.

Why is right the safe choice when the first count fails? If the whole array has a majority, it must be left or right. If the majority is left, the count check finds it. If the majority is not left, it must be right. So returning right is correct.

The result of this step is only a candidate. A candidate can be wrong. For example, 1 2 3 4 produces candidate 4, but 4 is not a majority. That is why the top-level function counts the candidate once more at the end.

Worked example: `2 2 1 1 1 2 2`

This example has 7 values, so the split is at index 3. The left half is 2 2 1 and the right half is 1 1 2 2.

Solve the left half 2 2 1. Split it into 2 and 2 1. The left piece 2 gives candidate 2. The right piece 2 1 is split into 2 and 1, which give candidates 2 and 1. They differ. Count 2 in 2 1: it appears 1 time, and 1 is not more than 2 / 2 = 1, so the candidate is 1. Now back in 2 2 1: the left candidate is 2 and the right candidate is 1. They differ. Count 2 in 2 2 1: it appears 2 times, and 2 is more than 3 / 2 = 1, so the candidate is 2.

Solve the right half 1 1 2 2. Its left half 1 1 gives candidate 1, and its right half 2 2 gives candidate 2. They differ. Count 1 in 1 1 2 2: it appears 2 times, and 2 is not more than 4 / 2 = 2, so the candidate is 2.

Back at the top level, both candidates are 2, so the candidate is 2. Count 2 in the whole array: it appears 4 times, which is more than 7 / 2 = 3. So 2 is the majority element.

The C++ code

The program below has the candidate function, the majority function, and a main function that runs five test arrays. It uses only the standard library.

C++ · editable

#include <algorithm>
#include <iostream>
#include <limits>
#include <optional>
#include 
#include <vector>

// Counts how many times value appears in the whole segment.
int countIn(std::span<const int> a, int value) {
 return static_cast<int>(std::ranges::count(a, value));
}

// Returns the one value that could be the majority of a non-empty segment.
// If a majority exists, this always returns it. If not, the result is
// some value that the caller must check.
int candidate(std::span<const int> a) {
 if (a.size() == 1) {
 return a[0];
 }
 auto mid = a.size() / 2;
 int left = candidate(a.first(mid));
 int right = candidate(a.subspan(mid));
 if (left == right) {
 return left;
 }
 if (countIn(a, left) > static_cast<int>(a.size() / 2)) {
 return left;
 }
 return right;
}

// Returns the majority element, or nothing when no value appears more than n / 2 times.
std::optional<int> majorityElement(const std::vector<int>& nums) {
 if (nums.empty()) {
 return std::nullopt;
 }
 int c = candidate(nums);
 if (countIn(nums, c) > static_cast<int>(nums.size() / 2)) {
 return c;
 }
 return std::nullopt;
}

int main() {
 std::vector<std::vector<int>> tests = {
 {3, 2, 3},
 {2, 2, 1, 1, 1, 2, 2},
 {1, 2, 3, 4},
 {7},
 {5, 5, 5, 1, 5, 2},
 };
 for (const auto& t : tests) {
 auto m = majorityElement(t);
 std::cout << "majority: ";
 if (m) {
 std::cout << *m << '\n';
 } else {
 std::cout << "none\n";
 }
 }
}

Compile and run it with these commands.

g++ -std=c++20 -Wall -o majority majority.cpp
./majority

The output is:

majority: 3
majority: 2
majority: none
majority: 7
majority: 5

A few details in the code are worth slowing down for.

std::optional<int> is a value that may be missing. std::nullopt means "no value", and the caller checks if (m) before reading *m. This is clearer than returning -1, because -1 could also be a real value in the array.
a.first(mid) and a.subspan(mid) create the two halves as views. Nothing is copied, so the function uses no extra memory per call.
std::ranges::count counts the values equal to value. It is in the <algorithm> header.

How fast is it?

At each level of splitting, the function counts over the whole segment once in the combine step. Across one level, the segments add up to n values, so one level costs O(n) work. With log2(n) levels, the total is O(n log n). The recursion depth is O(log n), so the call stack stays small.

The count step is the expensive part. The method is correct, but a hash map or the Boyer-Moore voting method is faster in practice. Divide and conquer is taught here because it shows the pattern clearly.

Problem 2: maximum subarray

A subarray is a contiguous piece of an array, meaning values that sit next to each other with no gaps. The maximum subarray problem asks for the largest possible sum of any subarray. Take this array.

-2 1 -3 4 -1 2 1 -5 4

The best subarray is 4 -1 2 1, with sum 6. Other subarrays have smaller sums. For example, 4 alone has sum 4, and -2 1 -3 4 -1 2 1 has sum 2.

A brute force method tries every start and every end. It works, but it is slow for large arrays. Divide and conquer gives a faster method.

Where can the best subarray be?

Split the array at the middle, so there is a left half and a right half. Any subarray must fall into one of three groups.

It lies entirely in the left half.
It lies entirely in the right half.
It crosses the middle. It starts in the left half and ends in the right half.

The first two cases are solved by recursion. The third case needs its own work. Because a subarray is contiguous, a subarray that crosses the middle must contain both the last element of the left half and the first element of the right half. If it does not contain both, it is not crossing.

The crossing case

A crossing subarray is made of two parts. The first part is a run that ends at the last element of the left half. The second part is a run that starts at the first element of the right half. Its sum is the sum of the two parts.

To make the first part as large as possible, start at the last element of the left half and walk left. Keep a running sum, and record the best value seen. Do the same for the right half, walking right from its first element. Add the two best values.

Here is the example array split at index 4, so the left half is -2 1 -3 4 and the right half is -1 2 1 -5 4.

Walking left from the end of the left half gives running sums 4, then 1 (4 + -3), then 2 (1 + 1), then 0 (2 + -2). The best is 4, from the element 4 alone.
Walking right from the start of the right half gives running sums -1, then 1 (-1 + 2), then 2 (1 + 1), then -3 (2 + -5), then 1 (-3 + 4). The best is 2, from -1 2 1.
The crossing best is 4 + 2 = 6, which is the subarray 4 -1 2 1.

The recursive calls on the two halves give 4 for the left half and 4 for the right half, so the answer is the largest of 4, 4, and 6, which is 6.

The C++ code

The program below has two functions. bestAcrossMiddle handles the crossing case. maxSubarray splits the array, calls itself on each half, and takes the largest of the three answers.

C++ · editable

#include <algorithm>
#include <iostream>
#include <limits>
#include 
#include <vector>

// Best sum of a subarray that uses the last element of left and the first element of right.
long long bestAcrossMiddle(std::span<const int> left, std::span<const int> right) {
 long long bestLeft = std::numeric_limits<long long>::min();
 long long run = 0;
 for (auto it = left.rbegin(); it != left.rend(); ++it) {
 run += *it;
 bestLeft = std::max(bestLeft, run);
 }

long long bestRight = std::numeric_limits<long long>::min();
 run = 0;
 for (int x : right) {
 run += x;
 bestRight = std::max(bestRight, run);
 }
 return bestLeft + bestRight;
}

// Best sum of any non-empty contiguous piece of a. The input must not be empty.
long long maxSubarray(std::span<const int> a) {
 if (a.size() == 1) {
 return a[0];
 }
 auto mid = a.size() / 2;
 auto left = a.first(mid);
 auto right = a.subspan(mid);
 return std::max({maxSubarray(left),
 maxSubarray(right),
 bestAcrossMiddle(left, right)});
}

int main() {
 std::vector<std::vector<int>> tests = {
 {-2, 1, -3, 4, -1, 2, 1, -5, 4},
 {1},
 {-3, -1, -4},
 {5, 4, -1, 7, 8},
 };
 for (const auto& t : tests) {
 std::cout << maxSubarray(t) << '\n';
 }
}

Compile and run it with these commands.

g++ -std=c++20 -Wall -o maxsub maxsub.cpp
./maxsub

The output is:

Check the four answers by hand. 1 is the single element. For -3 -1 -4, the best subarray is the single element -1, because any longer piece adds a negative number. For 5 4 -1 7 8, the whole array has sum 23.

The running sums start at std::numeric_limits<long long>::min() instead of 0. That matters when every value is negative. With a starting value of 0, the function would report 0 for -3 -1 -4, but a subarray must contain at least one element, so the correct answer is -1.

Why the recursion is O(n log n)

The crossing step walks over every element of its segment once, so one call on n elements costs O(n). The two recursive calls split the work, and each level of the recursion covers the whole array once. With log2(n) levels, the total time is O(n log n). This is slower than the O(n) method called Kadane's algorithm, which is the method you would use in a real program. Kadane's algorithm keeps one running best sum while it walks the array once.

Common mistakes

The first mistake is forgetting the crossing case. If maxSubarray returns only the larger of the two recursive answers, it misses subarrays such as 4 -1 2 1 that touch the middle. The example above returns 4 instead of 6 in that case, so the test is worth keeping.

The second mistake is starting a running best at 0. This gives the wrong answer for arrays with only negative values, as shown above.

The third mistake is forgetting the final check in the majority element code. Without the last countIn call, majorityElement({1, 2, 3, 4}) returns 4, which is not a majority. The candidate is only a guess, and the count is what makes it a real answer.

The fourth mistake is calling maxSubarray on an empty array. The function expects at least one element. With an empty array, both halves stay empty, and the function calls itself forever until the call stack runs out. The fix is a check at the top, such as if (a.empty()) throw std::invalid_argument("empty input");.

The fifth mistake is forgetting the  header. Without it, the compiler reports an error like this.

nospan.cpp:4:17: error: ‘span’ is not a member of ‘std’
    4 | int sumAll(std::span<const int> a) {
      |                 ^~~~
nospan.cpp:3:1: note: ‘std::span’ is defined in header ‘<span>’; this is probably fixable by adding ‘#include <span>’
    2 | #include <vector>
  +++ |+#include <span>
    3 |

The error message names the missing header. Add #include  at the top of the file and the error goes away. The text above is the first part of what g++ 15 printed for a file with only <iostream> and <vector> included, compiled with -std=c++20 -Wall. The compiler prints more errors after this one, which are left out.

Practice

Exercise 1. Use the candidate method by hand on the array 4 4 2 4 2. Write the candidate for each piece, then decide whether 4 is the majority element.

Show the answer

The left half is 4 4 and gives candidate 4. The right half is 2 4 2, which splits into 2 and 4 2. The piece 4 2 has candidates 4 and 2, which differ. Count 4 in 4 2: it appears once, which is not more than 1, so the candidate is 2. Then 2 4 2 has candidates 2 and 2, which are equal, so its candidate is 2. Back at the top, the left candidate is 4 and the right candidate is 2. Count 4 in the whole array: it appears 3 times, which is more than 5 / 2 = 2. So the candidate is 4, and 4 is the majority element.

Exercise 2. Find the maximum subarray sum of -2 -3 4 -1 -2 1 5 -3. Name the subarray that gives it.

Show the answer

The answer is 7, from the subarray 4 -1 -2 1 5. Its sum is 4 - 1 - 2 + 1 + 5 = 7. The program in this lesson returns 7 for this array when you give it the same values.

Exercise 3. Does 1 1 2 2 have a majority element? Explain your answer with the rule "more than n / 2 times".

Show the answer

No. The array has 4 values, so a majority needs more than 2 occurrences. Value 1 appears 2 times and value 2 appears 2 times. Neither is more than 2, so there is no majority element. The candidate function may still return 1 or 2 as a candidate, which is why the final count is needed.

Exercise 4. Explain in plain words why the crossing subarray in maximum subarray must include both the last element of the left half and the first element of the right half.

Show the answer

A subarray is a run of values that sit next to each other. If it starts in the left half and ends in the right half, it must pass over the boundary between the two halves. The boundary is the gap between the last element of the left half and the first element of the right half. Passing over that gap means the subarray includes both of those elements. If a subarray does not include both, it lies on one side of the boundary, so the recursive calls already handle it.

Exercise 5. Write the candidate function's combine rule for an array whose length is odd, such as 5 5 1. Which half is larger, and does that change the rule?

Show the answer

With mid = a.size() / 2, the left half is the smaller half and the right half has one more element. For 5 5 1, mid is 1, so the left half is 5 and the right half is 5 1. The combine rule does not change. It still compares the two candidates and counts the left candidate against n / 2, where n is 3, so the count must be more than 1. The left candidate 5 appears 2 times in the whole array, which is more than 1, so the answer is 5. The rule works for odd and even lengths because it uses integer division in the same way for both.

Summary

Divide and conquer splits an array at the middle, solves each half with the same function, and combines the two answers.
A majority element of the whole array must be the majority element of at least one half, so each half can return a single candidate.
The candidate must be checked with one more count, because a candidate is not always a majority.
Maximum subarray has three cases: the best subarray is in the left half, in the right half, or crosses the middle.
The crossing case is found by walking outward from the middle with a running sum, and the running best must start at the smallest possible value, not 0.
Both solutions run in O(n log n) time, and faster methods exist for each problem.

Majority element and max subarray

Why this matters

The pattern in three steps

Problem 1: majority element

The key fact

The combine rule

Worked example: 2 2 1 1 1 2 2

The C++ code

How fast is it?

Problem 2: maximum subarray

Where can the best subarray be?

The crossing case

The C++ code

Why the recursion is O(n log n)

Common mistakes

Practice

Summary

Stuck? Ask the tutor

Worked example: `2 2 1 1 1 2 2`