```

A A A C C B B C C C B C C
^
?:0
```

We will sweep down the sequence starting at the pointer position shown above.

As we sweep we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.

When we move the pointer forward over an element e:

• If the counter is 0, we set the current candidate to e and we set the counter to 1.
• If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.

Click on Step below to carry out the algorithm.

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
A:1
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
A:2
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
A:3
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
A:2
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
A:1
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
?:0
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
B:1
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
?:0
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
C:1
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
C:2
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
C:1
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
C:2
```

[Step]

[Abort]

```

A A A C C B B C C C B C C
^
C:3
```
The majority element is `C` (if any element has a majority).

Note that if you replaced the first C with an A, above, the algorithm would still end with C being chosen, but in fact C would not be the majority element: there is no majority in the modified list.

In some situations you know, or assume, there is a majority element.

But if you must confirm that the chosen element is indeed the majority element, you must take one more linear pass through the data to do it.

[end of example]