Animations
Find Largest Number — Visual Walkthrough
Watch a champion variable scan through the array, updating whenever a bigger number is found.
Find Largest Number
Array: [3, 7, 1, 9, 4, 11, 2, 8, 6, 5]
Start by assuming the first element is the largest — the champion. Walk through every other element. Any time a bigger number is found, it becomes the new champion. At the end — the champion is the largest number.
Find Largestlinear scan · O(n)
champion—
3
[0]7
[1]1
[2]9
[3]4
[4]11
[5]2
[6]8
[7]6
[8]5
[9]current
champion
new champion
checked
current—
vs→
champion—
find_largest.py
def find_largest(numbers):
largest = numbers[0] # start here
for number in numbers[1:]:
# check each number
if number > largest:
largest = number # new champion!
return largest
Call find_largest([3, 7, 1, 9, 4, 11, 2, 8, 6, 5])
step 0/24
0%
How it works
def find_largest(numbers):
largest = numbers[0] # start with first as champion
for number in numbers[1:]:
if number > largest:
largest = number # new champion
return largestThe champion changes only when a strictly bigger number is found. Equal numbers do not replace the current champion.
| Step | number | largest | Update? |
|---|---|---|---|
| start | — | 3 | — |
| 1 | 7 | 7 | ✓ new champion |
| 2 | 1 | 7 | ✗ |
| 3 | 9 | 9 | ✓ new champion |
| 4 | 4 | 9 | ✗ |
| 5 | 11 | 11 | ✓ new champion |
| 6–9 | 2,8,6,5 | 11 | ✗ |
Starting largest = numbers[0] instead of largest = 0 is important. If all numbers are negative like [-5, -1, -8], starting at 0 would wrongly return 0. Starting at the first element works correctly for any input.
Complexity
| Time | Space | |
|---|---|---|
| This approach | O(n) | O(1) |