Majority element and max subarray in Python

Why this matters

Divide and conquer solves a problem by cutting it into smaller copies of the same problem. You solve each copy, then combine the answers into one result. Many list problems look at every pair of values if you solve them the direct way. Divide and conquer often avoids that cost.

This lesson uses one pattern for two problems. Both problems ask for an answer about a range of a list. The hard part is the answer that sits on both sides of the cut. The code has to check that case on its own, and beginners usually forget it. Most of this lesson is about that check.

The Master theorem lesson earlier in this module shows how to turn this pattern into a cost formula. Here we count the work by hand.

The three steps

Each problem in this lesson follows the same three steps.

1. Divide. Cut the range into a left half and a right half at a middle index.
2. Conquer. Solve the problem for the left half and for the right half. Each half uses the same method, so the function calls itself. A function that calls itself is called recursive.
3. Combine. Use the two answers. Then check any answer that uses values from both halves.

A recursive function needs a base case. The base case is a range small enough to answer without cutting again. Here, a range with one value is the base case.

Part 1: the majority element

The problem

A majority element is a value that appears more than half the time in a list. In a list of 7 values, the majority must appear at least 4 times.

Take the list [2, 2, 1, 1, 1, 2, 2]. The value 2 appears 4 times. Half of 7 is 3.5, and 4 is more than 3.5, so 2 is the majority. The value 1 appears 3 times. That is not enough.

Take the list [1, 2, 3]. No value appears twice, so there is no majority. The function returns None for "no answer". None is Python's value for "nothing here". Its role is the same as null in Java. A function that may return a number or nothing can return int | None. That is a type hint. It tells a reader that the result is an int or None. Python does not enforce type hints when it runs the code.

The direct method counts each value by scanning the whole list. For a list of n values, that is about n times n steps. For 1,000,000 values, that is about a trillion steps. The divide and conquer method does about n times log n steps, which is about 20 million for 1,000,000 values. Here, log n means the number of times you can cut n in half before you reach 1.

The key fact

Suppose the value x is the majority of a whole list of length n. Then x appears more than n divided by 2 times.

Now cut the list into two halves. Call the left half's length L and the right half's length R, so L plus R is n. Suppose x is not a majority of either half. Then x appears at most L divided by 2 times on the left, and at most R divided by 2 times on the right. Together that is at most n divided by 2 times. That contradicts the fact that x appears more than n divided by 2 times. So x must be the majority of at least one half.

So the function works like this. Ask the left half for its majority. Ask the right half for its majority. Those two answers are the only possible majorities of the whole list. Then count each candidate across the whole range. Keep the candidate only if its count is enough.

The count needed in a range of length L is one more than half of L, rounded down. For L equal to 7, that is 4. For L equal to 4, that is 3.

A worked example

Take [2, 2, 1, 1, 1, 2, 2], with indexes 0 to 6.

The middle index is 3, so the left half is indexes 0 to 3, which holds [2, 2, 1, 1]. The right half is indexes 4 to 6, which holds [1, 2, 2].

The left half has length 4, so it needs 3 copies of a value to be a majority. Its values appear 2 times each, so the left half has no majority.

The right half has length 3, so it needs 2 copies. The value 2 appears 2 times, so the right half's majority is 2.

Now count 2 across the whole list. It appears 4 times. The whole list needs 4, so 2 is the answer.

A second example with more levels

Take [5, 5, 3, 5, 3, 3, 5]. The value 5 appears 4 times out of 7, so it is the majority.

The middle index is 3. The left half is [5, 5, 3, 5], and the right half is [3, 3, 5]. Each half is split again.

The left half splits into [5, 5] and [3, 5]. The first pair has majority 5. The second pair has no majority, since each value appears once and a range of length 2 needs 2. So the left half has 5 as a candidate. Counting 5 across the left half gives 3, which is enough for a length 4 range.

The right half splits into [3, 3] and [5]. The first part has majority 3, and the second part has majority 5. Those two candidates differ. Counting 3 across the right half gives 2, which is enough for a length 3 range. So the right half's answer is 3.

The two candidates for the whole list are 5 and 3. Counting 5 across the whole list gives 4, which is enough for a length 7 range. The answer is 5. Running majority_of on this list returns 5.

The code

The function majority takes the list and a range, given by two indexes. It returns the majority value or None. The helper count_in counts one value inside a range.

Two Python features appear here. The expression nums[lo:hi + 1] is a slice. A slice is a copy of part of a list. It starts at the first index and stops before the second one, so the end index is not included, and + 1 makes hi part of the copy. The method list.count(value) counts how many times a value appears in a list.

Save the program as majority.py and run it with python3 majority.py. The output is:

[2, 2, 1, 1, 1, 2, 2] -> 2
[3, 3, 4, 2, 4, 4, 2, 4, 4] -> 4
[1, 2, 3] -> None
[7] -> 7
20000 random arrays agree with brute force

The last part of the program is a check. It makes 20,000 random lists, and compares the divide and conquer answer with the brute force answer (the simple, slow method that checks every case). The random.Random(42) line creates a random number generator with a fixed seed, so the same lists come out on every run. A check like this finds bugs that a few hand examples can miss.

Why the code checks the candidates

The code does not return the left or right answer straight away. It counts the candidate across the whole range. The left answer might be a majority of the left half only. A value can be a majority of the left half and still be too rare in the whole range.

Take [1, 2, 3] again. Each half gives a candidate, or no candidate, and neither candidate reaches the count the whole range needs. The function returns None.

Part 2: the maximum subarray

The problem

A subarray is a run of values that sit next to each other in the list. The maximum subarray problem asks for the run with the largest sum. The run must hold at least one value.

Take [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The best run is [4, -1, 2, 1], which starts at index 3 and ends at index 6. Its sum is 6.

The direct method tries every start index and every end index, then adds the values. That is about n squared steps, the same cost as the direct majority method. The code in this lesson uses a brute function for checking, and the max_subarray function uses divide and conquer.

Where can the best run be?

Cut the list at the middle. The best run is in one of three places.

1. Entirely in the left half.
2. Entirely in the right half.
3. Crossing the middle. It starts in the left half and ends in the right half.

Cases 1 and 2 come from the recursive calls. Case 3 needs new work. A function that only compares the left answer and the right answer misses case 3.

Take [5, -1, 5]. The middle index is 1. The left half is [5, -1]. Its best run is [5], with sum 5. The right half is [5], with sum 5. The best run that crosses the middle is the whole list, [5, -1, 5], with sum 9. The correct answer is 9. A function that only compares the two halves returns 5, which is wrong.

How to find the best crossing run

A crossing run is two pieces joined at the middle. The left piece ends at the middle index and goes left. The right piece starts just after the middle and goes right. The two pieces do not depend on each other. So you find the best left piece and the best right piece, then add their sums.

To find the best left piece, start at the middle index and walk left. Add each value to a running total. Keep the largest running total you see, and remember where that piece starts. Do the same walk to the right, starting just after the middle.

Take [5, -1, 5] again, with the middle between index 1 and index 2.

Left pieces that end at index 1 are [-1] with sum -1, and [5, -1] with sum 4. The best is 4, starting at index 0.

Right pieces that start at index 2 are [5] with sum 5. The best is 5, ending at index 2.

The best crossing run is 4 plus 5, which is 9. It starts at index 0 and ends at index 2.

Both walks always run at least once, because each half has at least one value. So a best piece always exists, and the code never has to handle an empty walk.

The answer for the whole range is the largest of three values: the best left answer, the best right answer, and the best crossing answer.

A second example where the crossing run wins

Take [2, -1, 3, -2]. The middle is between index 1 and index 2.

The left half [2, -1] has best run [2], with sum 2. The right half [3, -2] has best run [3], with sum 3. Neither half's best run is the answer for the whole list.

The best left piece that ends at index 1 is [2, -1], with sum 1. The best right piece that starts at index 2 is [3], with sum 3. The crossing run is [2, -1, 3], with sum 4.

The largest of 2, 3, and 4 is 4. The answer is sum 4 at indexes 0 to 2. Running max_subarray on this list returns that answer.

The code

The Best class holds the start index, the end index, and the sum. It is a dataclass. A dataclass is a short class that holds fixed values. The line @dataclass(frozen=True) above the class is a decorator, which is a marker that changes the class below it. Here it writes the constructor for you (the code that sets the fields when you call Best(...)), and frozen=True stops the values from being changed after they are set.

Python integers have no size limit, so the sum can be any size without a special type. The program below uses a float value float("-inf") as a starting value for the best sum. It means negative infinity. Any real sum is bigger than it.

The output is:

[-2, 1, -3, 4, -1, 2, 1, -5, 4] -> sum 6 at indexes 3..6 = [4, -1, 2, 1]
[5, -1, 5] -> sum 9 at indexes 0..2 = [5, -1, 5]
[-3, -1, -2] -> sum -1 at indexes 1..1 = [-1]
[4, -1, -2, 1, 5, -3] -> sum 7 at indexes 0..4 = [4, -1, -2, 1, 5]
20000 random arrays agree with brute force

The third line shows a case where every value is negative. The best run is the single least negative value, -1. The run cannot be empty, so the answer is not 0.

Cost

Each recursive call does one crossing walk over its range, which costs about the length of the range. The halving creates about log n levels. So the total cost is about n times log n. The Master theorem lesson gives the formal version of this count.

The table compares the direct method with the divide and conquer method. The numbers are rounded.

The majority method has the same cost. A faster method for the maximum subarray runs in one pass over the list. It is not covered in this lesson.

A slice such as a[b.start:b.end + 1] copies its values, so printing a slice costs time too. The copy is only used for printing here. The count_in function in the majority code makes a slice on each call, so it does more work than a plain loop, but the cost still grows at the same rate.

Checking with random tests

A fast method is only useful if its answers are right. The brute function in the code is slow, but it is simple enough to trust. The main part of the program builds 20,000 random lists, runs both functions on each one, and stops if the answers differ.

Random tests often find cases that a few hand examples miss, such as a list of only negative values or a list of length 1. Keep the slow function in your test code, and use the fast function in your program.

Common mistakes

Forgetting the crossing case

If you only take the best of the two halves, the answer for [5, -1, 5] is wrong. Here is a version with that bug.

def wrong(a, lo, hi):
    if lo == hi:
        return a[lo]
    mid = lo + (hi - lo) // 2
    return max(wrong(a, lo, mid), wrong(a, mid + 1, hi))
 
 
print("wrong max subarray on [5, -1, 5]:", wrong([5, -1, 5], 0, 2))

The output is:

wrong max subarray on [5, -1, 5]: 5

The correct sum is 9. The fix is the crossing function. Always ask: can the best answer use values from both sides of the cut?

Returning a candidate without counting it

In the majority problem, a common bug returns the left candidate if it exists.

def wrong_majority(nums, lo, hi):
    if lo == hi:
        return nums[lo]
    mid = lo + (hi - lo) // 2
    left = wrong_majority(nums, lo, mid)
    if left is not None:
        return left
    return wrong_majority(nums, mid + 1, hi)
 
 
print("wrong majority on [1, 2, 3]:", wrong_majority([1, 2, 3], 0, 2))

The output is:

wrong majority on [1, 2, 3]: 1

The correct answer is None, because no value is a majority. The fix is to count each candidate across the whole range before you return it.

Using None as a number

The majority function returns None when there is no answer. If you use the result as a number, Python stops with an error. The program below calls majority_of on a list that has no majority, then adds 1 to the result.

from majority import majority_of
 
x = majority_of([1, 2, 3]) + 1
print(x)

The last lines of the error are:

    x = majority_of([1, 2, 3]) + 1
        ~~~~~~~~~~~~~~~~~~~~~~~^~~
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

The name NoneType is the type of None. The fix is to check for None before you use the value:

answer = majority_of([1, 2, 3])
if answer is None:
    print("no majority")
else:
    print(answer + 1)

Use is None to test for None, not == None. The is test checks the object itself.

Forgetting that the end of a slice is excluded

The slice nums[lo:hi] stops before index hi. So it leaves out the last value of the range. Look at this list:

nums = [2, 2, 1, 1, 1, 2, 2]
print(nums[0:3], nums[0:4])

The output is:

[2, 2, 1] [2, 2, 1, 1]

The range from index 0 to index 3 needs nums[0:4]. In this lesson, count_in uses hi + 1 for that reason.

Starting the best sum at zero

Some people start the best sum at 0. That works only if the empty run is allowed. This lesson does not allow an empty run. If every value is negative, the best sum at 0 would wrongly give 0. The code starts from a real value instead.

Starting with a sentinel value

A sentinel is a special value that marks "not set yet". The code sets best_left to float("-inf"). In Python, adding a number to negative infinity gives negative infinity, so the value stays marked as "no real sum yet":

print(float("-inf") + 5)

The output is:

-inf

The crossing function avoids this problem, because both loops always run at least once. So best_left and best_right always hold real sums before they are added together. Python integers do not overflow. A sum of two large numbers is still correct:

print(2000000000 + 2000000000)
print(2 ** 100)

The output is:

4000000000
1267650600228229401496703205376

Practice

Exercise 1

What is the majority element of [9, 9, 9, 1, 1, 1, 1]?

Show the answer

The answer is 1. The list has length 7, so the majority needs 4 copies. The value 1 appears 4 times. The value 9 appears 3 times, which is not enough.

Exercise 2

What is the majority element of [1, 1, 2, 2, 3, 3]?

Show the answer

The answer is that there is none. The list has length 6, so the majority needs 4 copies. Each value appears only twice. The function returns None.

Exercise 3

Find the maximum subarray of [3, -2, 5, -1]. Give the sum and the indexes.

Show the answer

The best run is [3, -2, 5]. Its sum is 6, and it runs from index 0 to index 2. The whole list sums to 5, which is less than 6. Running max_subarray on this list gives the same answer.

Exercise 4

Take [1, -3, 2, 5], with the middle between index 1 and index 2. Find the best crossing run. Then find the overall answer.

Show the answer

The best left piece that ends at index 1 is [1, -3] with sum -2. The best right piece that starts at index 2 is [2, 5] with sum 7. The best crossing run is from index 0 to index 3, with sum 5. The overall answer is different. The right half alone has the run [2, 5], with sum 7 from index 2 to index 3. So the overall answer is sum 7 at indexes 2 to 3.

Exercise 5

What does max_subarray return for [-1, -2, -3]? Why is the answer not 0?

Show the answer

It returns sum -1 at index 0, the run [-1]. The answer is not 0, because a subarray must hold at least one value. The empty run is not allowed.

Exercise 6

Each level of the recursion halves the range. How many levels does a list of 1024 values have, from the full list down to single values?

Show the answer

There are 11 levels of sizes, from 1024 down to 1. Halving 1024 gives 512, then 256, then 128, then 64, then 32, then 16, then 8, then 4, then 2, then 1. That is 10 halvings. The value 1024 is 2 to the power of 10.

Summary

• Divide and conquer cuts a range in half, solves each half, then combines the answers.
• A majority element must be the majority of at least one half, so only two candidates need checking.
• The maximum subarray can cross the middle, so the code must find the best run that uses values from both halves.
• Both methods cost about n times log n steps, compared with about n squared for the direct method.
• Check for None before you use a result as a number, and remember that the end of a slice is excluded.