Video 5-7: Majority
CS 566 – Efficient Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-16, 20:10
The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.
0:02 In the next section, we'll look at the majority problem. Another very basic, very innocent problem where hopefully we can get some really fast algorithms. Uh the problem we're looking at is is this one. We have an array of objects and uh the question is is there one that is in the strict majority that occurs strictly more than in half of the positions. Okay, absolute majority I should have said. Uh what we assume here is that all we can do with these objects is ask whether two are equal. There's no other operation. In particular, you cannot add them up or you cannot compare them with less or equal or anything like that. So um this seems a very restricted setting. The naive solution for this would be if you want to check you take each element of the array in a row and just count how many elements are equal to it. Then afterwards you know for each element its frequency. So you have the full frequency table of the elements. And clearly there's a majority if and only if one of the elements has a frequency strictly greater than n half. Now you're usually if there is a frequency greater than n half element then you'll find it maybe a bit sooner most of the time but in the worst case they could be the last elements you look at. So uh overall this takes quadratic time because I have n elements and for each of the ele elements I might have to check all the others. If I'm not trying to be smarter then that's what I get. And with this approach I think there's not that much smartness that you can put into this.
1:42 Uh note that we require absolute majority even if n is even. It's not good enough that there's an even an equal number of elements and non equal elements. It has to be strictly more.
1:57 Okay. So this is uh the baseline that we want to beat. What can we do? Unsurprisingly, we can do a divide and conquer approach. What would that look like? What can we divide here? Well, I I guess only the array of elements. So, we can take say the first half and the second half of the elements. What can we do? Uh, we can recursively ask for a majority, right? And then try to recombine that somehow. So, if you have your array and you take the first half, then here is there a majority in the in here?
2:48 Um maybe these are just two recursive calls. Now what what is the options that they can come back with? One option is they say no, right?
3:01 No majority in this part. There's too much diversity. or they return a specific element X or um let me already be consistent with what we use later ML the majority on the left and you can have any combination of these because of course the right could also say this So they could both say no or one could say no or they could both say uh here's a majority. For each of these cases we have to think about what what happens and how that may uh imply something about the entire array. and the key inside. Um let's jump there first. Uh first you can think a bit about this.
4:09 Uh so suppose so that we don't have to worry about halves that there's an even number of elements overall and uh suppose there is a majority element x. So this is a special case that we want to think about first and as in the on the slide before let's say ML and MR denote the result that you get from the left and the right recursive call and I think M ML and MR this is a bit inconsistent to what I said they might be the special value no majority so when it says equal here uh I guess that's that's clear they both return x but here when they say um ML is not Mr. This could be they return to different values that they claim is the majority left and right or it could be that one of them says no majority here. I guess in this case it has to be L right because Mr is equal to X which is a value.
5:06 So uh what you should think about is which of these are possible assuming that there is a majority element uh and you get these two recursive calls and the recursive calls are correct. So they give the right answer. Uh which options can occur and which options cannot occur?
6:18 Okay, it seems to be rather clear vote. It looks like the first three are much more popular and that's correct. And let's see why. So first of all, the first is clearly possible. If say the entire array is full of x's, then you you would have this, right? It's one of the possible options. The possible ones are easy. I just need to find an example input that gives me that. Um here's an example input where the left would have a majority of X but the right may not have the majority X even though X overall is more than um so suppose here really the left part is all X's then I only need one extra X to be the majority in the entire array and of course X is the majority in the left and this is symmetric. So each of these cases we can clearly get. Now we only need to argue why the other ones are are not possible.
7:23 Um first of all this one that left and right agree about what happens uh but they don't agree on X. This is really two cases in disguise. If they were to agree on a value, some value y that's supposedly a majority in both parts, then I have more than half of the occurrences left and right. That's more than half already than in the entire array. So this this clearly cannot happen because then y has to be our majority, not x, but y is not x. Uh the other option is that they both say this um has no majority but x is a majority overall. So I have to somehow hide n half + one occurrences of x. Even if I evenly distribute them, one of the halves will have x more than half of its positions strictly more. So this also can't happen because I I cannot really get rid of my x's. Uh last is is uh is similar. So if if this is not the case, so both return something not x uh we run into a similar issue. I cannot hide all the occurrences of x.
8:51 Okay, that's that. How can we turn that into an algorithm? Let me go back here. Basically, in the obvious way, we've already done it. Uh the possible cases.
9:06 If I have an overall majority, tell me what I have to do. If A has a majority, that element must also be the majority of one of the halves. That's what we established. And then we can find that recursively. We might have two candidates to check on the left and on the right that's coming from uh from these parts here.
9:30 I mean I don't know X yet, right? So if if both come back with a different majority then uh one of them will be the majority. That's what these two cases guarantee. But I don't know X yet. So I have to find out which one it is. Uh so that's that's what what this says. Uh in code it looks much more complicated than it really is. There's a boundary case. We have to stop if we are down to a single element. Otherwise we look at the first and second half where half is to be rounded down appropriately. Then we have two candidate majorities that were the majorities of the left and the right. Um if they are the same then we already know what happens. then this is clearly majority overall otherwise I count how often each occurs. So I go through all the elements and just count how often I have the left or the right majority.
10:27 um if I have k is is n half right so if I have more occurrences from the left then I return that otherwise I will have more occurrences of that one or I don't have any majority and this even catches the case that ml returns no majority element then all of these comparisons will be false already trying to be a bit bit smart and making the code more compact the analysis here uh I didn't even write down the recurrence but uh we can do that the total cost if I start with n elements I do two recursive calls right on essentially half of the elements if we assume n is a power of two then it will be exactly half and what do we do in outside of the recursive call all this mumbo jumbo I go through each element once and count how often things occur everything else is constant time comparisons and initialization but This one gives me a a linear term and this is essentially the same recurrence as for merge sort. So of course it has the same solution.
11:39 Can we do better question? decide a candidate the majority element has to be in two plus one times data. >> Yeah. So this sounds like a randomized algorithm where we somehow take a sample of people or something like that. Um that's right. You can probably work work out something that works like this. In the worst case it it maybe is tricky because you may always be unlucky with the sample. Uh but the answer is of course uh correct. If in a real algorithm you do proper randomness this will be fine because the majority element just occurs so much. Yeah that's right. Yeah you can solve the problem with anything that gives you the precise frequency table. So you can iterate through all the elements and insert them into like a store a mapping from element to frequency in a in a dictionary. Of course you need some dictionary that gives you access in if you want to beat this better than logarithmic time.
13:00 And we made the assumption all we can do to our to our elements is equality checks. So in that strict model you cannot do it. In any sensible model of course you can do hashing and so at least randomize it should be doable. We've seen universal hashing and so at least um with randomization you can get this to work. It turns out that there's a very very cute algorithm here. I have to be honest it has nothing to do with divide and conquer but it's too cute not to show. uh you can do this in in linear time and the algorithm is incredibly simple.
13:44 You maintain a candidate and you go through each element once. Um so the candidate is X C is a counter. If the count is currently zero, then you store a new candidate and increment the counter or you always increment the counter. Um if the element is the same as X your current candidate then you increment otherwise you decrement.
14:12 It's a bit strange right? Um let me show you what happens and um why these are people and so on. I'll show you I'll I'll explain in a second. So first of all this is just simulating the algorithm. So I have I have a new person arriving. If there's already someone there, there's a a counter counting how many copies of the same element I have there. Okay, initially too many um collisions uh happen. Uh only at the last step we'll have the other case that was a bit degenerate. Let me pick a different input for starters. Uh sorry about that. So in this in this case uh when nobody's here then this person can take up the square. If the same gang arrives they can take up the square together. Whenever someone from from another drug gang arrives. This is explaining majority with uh a gang war metaphor. Uh whenever someone arrives not from the gang, they have a duel and both get killed.
15:30 But if they're from the same cartel, then they stay in the square. Claim. Whoever is at the end in the square is the only candidate for being the majority. They may or may not be in the majority, but if the input had a majority, it's the gang at the end in the square. Why is that the case? Uh for that let me or okay my my other input is lost. We can do it on the small one. That's also fine. Um the argument is is very simple. Suppose there is a majority like in this case the red red guys. How can it not end up in this case? Well, uh, I have to look at the graveyards of pairings. Um, in the worst, all of these pairings are of different colors. Okay.
16:34 So, um, there's at most n half minus one of these double graves because someone survives at the end in the in the square. If I have a majority, there is not enough graves to fill with red people. This all sounds really a bit bad, but I think it sticks to mind with this metaphor. If there's strictly more than n half people and at most n half square graves where each grave contains at most one person of each color, there must be a red person left at the end to take the square.
17:12 again your let me run it with um larger example many many jewels. Okay, this is always alternating. This is a bit stupid. Uh okay, there's a very slight majority for red in the end. And of course, let's speed this up a bit.
17:43 The number of double graves is n half and there's one extra red left. Each grave has to be of different colors because it's coming from a clash of different colors. So there can be at most n half minus one red people in the graveyard. If there's strictly more than n half people of red color, there will be one left to take the square. question.
18:25 what happens follows the same rule. If the square is free, it it'll be taken. For example, now it becomes yellow. Um and whenever there's a clash, you'll uh again have a clash of two people of different different gangs. So um in this case it happens that who's left in the square is not in the majority. It's just a candidate, right? You still have to go through this a second time and count. And so here three is not a majority out of seven. But if there was a majority, I cannot put enough of people from that gang into all the graves, one each, so that uh none is left for taking the square in the end. They all have to go somewhere. They're either dead or still standing in the square. Okay, that's majority. Um always written without vowels. Uh you could also say this is one of the earliest streaming algorithms. Uh a cute property of this algorithm is that it goes in passes over the data and keeps very little memory. It only remembers well one one identity, one object and one count. It needs to do a second pass to find out if the element that it got is an actual majority. But it never needs to keep the entire array in memory or do complicated divide and conquer structures over it.
19:53 And so the analysis is almost embarrassing that I'm I'm not even insulting your intelligence to follow through. This is one loop and so clearly linear time. So this is also best possible because you have to compare all the elements in the worst case.
← Video 5-6: Fast MultiplicationVideo 5-8: Closest Points in the Plane →