These are the notes for Python Coding Questions, episode 5, the first list episode. Three questions every fresher is asked: the largest element, the second largest, and the minimum and maximum. They are easy to write and easy to get wrong with negative numbers, duplicates and empty lists, and they're a good place to see what sorting really costs.
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real; timings depend on the machine, so compare them, don't copy them.
Q1: The largest element
| Input | Output |
|---|---|
[3, 9, 4] |
9 |
[12, 35, 1, 10, 34] |
35 |
[-3, -7, -1] (night temperatures in Leh in January, °C) |
-1 |
[] |
? (ask the interviewer) |
The obvious attempt: start at 0
def largest(nums):
best = 0
for x in nums:
if x > best:
best = x
return best
print(largest([3, 9, 4]), largest([12, 35, 1, 10, 34]))
print(largest([-3, -7, -1])) # Leh in January
print(largest([]))
Output:
9 35
0
0
Why it's wrong: best = 0 quietly adds a fake element, 0, to the list. Every negative number loses to it, so Leh's warmest night comes out as 0 °C, a temperature that never happened, and the empty list also says 0.
The fix: start from a real element
def largest(nums):
best = nums[0] # the first one so far
for x in nums[1:]:
if x > best:
best = x
return best
print(largest([3, 9, 4]), largest([-3, -7, -1]))
print(max([-3, -7, -1]), max([], default=None))
print(max([]))
Output:
9 -1
-1 None
Traceback (most recent call last):
File "main.py", line 10, in <module>
print(max([]))
~~~^^^^
ValueError: max() iterable argument is empty
best = nums[0], then loop overnums[1:](slicing copies the list;for x in nums:from the start also works and avoids the copy).max()does the same in C.max([])raisesValueError: max() iterable argument is empty, which is better than a made-up 0.max(nums, default=None)returnsNoneinstead.- Our own version raises
IndexErroronnums[0]for an empty list. In an interview, ask what an empty list should return, then checkif not nums:first. - Time O(n), space O(1).
Q2: The second largest element
Real-life example: a race scored 5, 5, 3. Two runners tie for gold; silver goes to the next different value, 3. "Second largest" usually means the largest value smaller than the maximum; if all values are equal, there is none. Always confirm this definition.
| Input | Output |
|---|---|
[12, 35, 1, 10, 34, 1] |
34 |
[5, 5, 3] |
3 |
[10, 10, 10] |
None |
[7], [] |
None |
[-3, -7, -1] |
-3 |
Attempt 1: sort and take index -2
def second_largest(nums):
return sorted(nums)[-2]
print(second_largest([12, 35, 1, 10, 34, 1]))
print(second_largest([5, 5, 3]))
print(second_largest([7]))
Output:
34
5
Traceback (most recent call last):
File "main.py", line 6, in <module>
print(second_largest([7]))
~~~~~~~~~~~~~~^^^^^
File "main.py", line 2, in second_largest
return sorted(nums)[-2]
~~~~~~~~~~~~^^^^
IndexError: list index out of range
sorted([5, 5, 3]) is [3, 5, 5]: index −2 is the other 5. A one-element list has no index −2: IndexError: list index out of range. And sorting costs O(n log n).
Attempt 2: one pass with float("-inf")
float("-inf") (minus infinity) is smaller than every number, so it's a safe starting value.
def second_largest(nums):
first = second = float("-inf")
for x in nums:
if x > first:
first, second = x, first
elif x > second:
second = x
return second
for nums in [[12, 35, 1, 10, 34, 1], [5, 5, 3], [7]]:
print(nums, "->", second_largest(nums))
Output:
[12, 35, 1, 10, 34, 1] -> 34
[5, 5, 3] -> 5
[7] -> -inf
The second 5 is not bigger than first (5) but is bigger than second (−inf at that moment), so it takes silver. And [7] returns -inf, not a real answer.
The fix: a chained comparison
first > x > second means first > x and x > second, written like in maths. A value equal to first is skipped.
def second_largest(nums):
first = second = float("-inf")
for x in nums:
if x > first:
first, second = x, first
elif first > x > second: # strictly between
second = x
return None if second == float("-inf") else second
for nums in [[12, 35, 1, 10, 34, 1], [5, 5, 3], [10, 10, 10],
[7], [], [-3, -7, -1], [1, 2]]:
print(nums, "->", second_largest(nums))
Output:
[12, 35, 1, 10, 34, 1] -> 34
[5, 5, 3] -> 3
[10, 10, 10] -> None
[7] -> None
[] -> None
[-3, -7, -1] -> -3
[1, 2] -> 1
One pass: O(n) time, O(1) space, and it works even on a stream of numbers that never fits in memory.
The readable alternative: a set
def second_largest(nums):
distinct = sorted(set(nums)) # set drops duplicates
return distinct[-2] if len(distinct) >= 2 else None
for nums in [[12, 35, 1, 10, 34, 1], [5, 5, 3], [10, 10, 10], [7], []]:
print(nums, "->", second_largest(nums))
Output:
[12, 35, 1, 10, 34, 1] -> 34
[5, 5, 3] -> 3
[10, 10, 10] -> None
[7] -> None
[] -> None
Correct and short, but it builds a set and a sorted list: O(n) extra space, O(n log n) time. Give both answers in an interview and say when you'd pick each.
Q3: Min and max
Real-life example: a max-min thermometer has two markers the mercury pushes during the day; at night you read the lowest and highest. Nothing else is stored: one pass, two variables. Sorting the whole list to read its two ends is like writing down every reading of the day in order, just to read two of them.
import random, time
random.seed(1)
nums = [random.randint(-10**9, 10**9) for _ in range(2_000_000)]
start = time.perf_counter()
s = sorted(nums)
print("sorted: ", s[0], s[-1], f"{time.perf_counter() - start:.3f} s")
start = time.perf_counter()
print("min, max: ", min(nums), max(nums), f"{time.perf_counter() - start:.3f} s")
start = time.perf_counter()
lo = hi = nums[0]
for x in nums:
if x < lo:
lo = x
elif x > hi:
hi = x
print("one loop: ", lo, hi, f"{time.perf_counter() - start:.3f} s")
Output (one run):
sorted: -999997904 999998257 0.400 s
min, max: -999997904 999998257 0.028 s
one loop: -999997904 999998257 0.079 s
random.seed(1)makes the "random" numbers the same on every run, so the test can be repeated.- sorted is O(n log n): about log₂(2,000,000) ≈ 21 comparisons per number, plus a new list of 2 million items. About ten times slower than
min()+max(). - min() + max() are O(n) each: two passes, but written in C.
- The Python loop is also O(n), and does only one pass, yet it's slower than
min()+max(): each Python loop turn costs much more than a step inside a C built-in. - Big-O describes how time grows, not exact seconds. Two O(n) solutions can differ by a constant factor. Write the loop to show the idea; use the built-ins in real code. (
min()andmax()also takekey=anddefault=.)
Follow-up: fewer comparisons, in pairs
One by one, each number is compared with lo and with hi: about 2 comparisons per number. Taking the numbers in pairs, compare the two with each other first, then only the smaller with lo and only the bigger with hi: 3 comparisons for every 2 numbers.
def min_max_pairs(nums):
lo = hi = nums[0]
comparisons = 0
for i in range(1, len(nums) - 1, 2):
a, b = nums[i], nums[i + 1]
if a > b:
a, b = b, a # now a <= b
comparisons += 3
lo = min(lo, a) # small one vs lo
hi = max(hi, b) # big one vs hi
if len(nums) % 2 == 0: # one left over
lo, hi = min(lo, nums[-1]), max(hi, nums[-1])
comparisons += 2
return lo, hi, comparisons
nums = [7, 2, 9, 4, 11, 3, 8, 1, 6, 5]
print(min_max_pairs(nums), "vs", 2 * (len(nums) - 1), "one by one")
Output:
(1, 11, 14) vs 18 one by one
About 1.5 n comparisons instead of 2 n. Still O(n), a smaller constant; in Python the C built-ins still win on time, but the interviewer is checking that you can count operations.
Follow-up: which day was it?
week = [("Mon", -3), ("Tue", -7), ("Wed", -1), ("Thu", -9), ("Fri", -4)]
coldest = min(week, key=lambda day: day[1])
warmest = max(week, key=lambda day: day[1])
print("coldest:", coldest, " warmest:", warmest)
temps = [t for _, t in week]
i = temps.index(min(temps))
print("coldest day index:", i, week[i][0])
Output:
coldest: ('Thu', -9) warmest: ('Wed', -1)
coldest day index: 3 Thu
min(items, key=...)/max(items, key=...)compare by the key (here the temperature,day[1]) and return the whole item, so you also get the day (the samekey=assortedin episode 17).temps.index(min(temps))finds the position in a plain list of numbers: two passes, still O(n). On a tie, bothminandindexreturn the first one.
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
best = 0 |
-1 list gives 0 |
0 is a fake element | best = nums[0], or max() |
max([]) |
ValueError: max() iterable argument is empty |
no elements | max(nums, default=None) or check first |
sorted(nums)[-2] |
[5, 5, 3] → 5; IndexError: list index out of range |
ties; one element | one pass, or a set with a length check |
elif x > second |
[5, 5, 3] → 5, [7] → -inf |
a duplicate of first takes silver | elif first > x > second, return None |
sorted() just for min and max |
~10× slower on 2,000,000 numbers | O(n log n) + a new list | min(), max(): O(n) |
| assuming fewer passes = faster in Python | the one-pass loop loses to min() + max() |
C built-ins vs Python bytecode | measure with time.perf_counter() |
Your turn: the third largest distinct value (solution)
[12, 35, 1, 10, 34, 1] → 12, [5, 5, 3] → None.
Solution
Three variables, each new value shifting the smaller ones down; chained comparisons skip duplicates.
import heapq
def third_largest(nums):
a = b = c = float("-inf")
for x in nums:
if x > a:
a, b, c = x, a, b
elif a > x > b:
b, c = x, b
elif b > x > c:
c = x
return None if c == float("-inf") else c
for nums in [[12, 35, 1, 10, 34, 1], [5, 5, 3], [3, 2, 1], []]:
print(nums, third_largest(nums), heapq.nlargest(3, set(nums)))
Output:
[12, 35, 1, 10, 34, 1] 12 [35, 34, 12]
[5, 5, 3] None [5, 3]
[3, 2, 1] 1 [3, 2, 1]
[] None []
heapq.nlargest(k, iterable) returns the k largest values in O(n log k) time; with set() they are distinct. For the k-th largest, take the last item of that list if it has k items.
Practice questions (with solutions)
1. Smallest and second smallest in one pass.
Solution
def two_smallest(nums):
s1 = s2 = float("inf")
for x in nums:
if x < s1:
s1, s2 = x, s1
elif s1 < x < s2:
s2 = x
fix = lambda v: None if v == float("inf") else v
return fix(s1), fix(s2)
print(two_smallest([12, 35, 1, 10, 34, 1]), two_smallest([4]))
Output:
(1, 10) (4, None)
2. The index of the largest element (the first one if tied).
Solution
nums = [3, 9, 4, 9]
print(nums.index(max(nums)), max(range(len(nums)), key=nums.__getitem__))
Output:
1 1
nums.index(max(nums)) makes two passes; max(range(len(nums)), key=...) compares indexes by their values in one pass. Both return the first index on a tie.
3. The largest value in each row of a table.
Solution
grid = [[3, 8, 1], [-2, -5, -1], [7, 7, 0]]
print([max(row) for row in grid])
Output:
[8, -1, 7]
Quick quiz
What does this print?
nums = [4, 8, 8, 2]
a = sorted(nums)[-2]
b = sorted(set(nums))[-2]
c = max(nums[:0], default=-1)
print(a, b, c)
(A) 8 4 -1 (B) 4 4 -1 (C) 8 8 2 (D) 8 4 ValueError
Answer
(A). sorted(nums) is [2, 4, 8, 8], so [-2] is the other 8. The set removes the duplicate: [2, 4, 8] → 4. nums[:0] is an empty list, so max returns the default, −1.
8 4 -1
Interview questions
- Why is
best = 0wrong for the largest element? It invents an element; all-negative lists return 0. Start fromnums[0]or usemax(). - What does
max([])do? RaisesValueError; passdefault=to return a value instead. - What does "second largest" mean with duplicates? Usually the largest value strictly smaller than the maximum; clarify with the interviewer.
- Second largest in one pass? Track
firstandsecondfrom-inf; update withx > first, elsefirst > x > second. - What is
float("-inf")? Negative infinity: smaller than every number, a safe initial value for a maximum. - What is a chained comparison?
a > b > cmeansa > b and b > c, evaluated left to right, withbcomputed once. - Complexity of
sorted()? O(n log n) time, O(n) extra space (it returns a new list;list.sort()sorts in place). - Why can a one-pass Python loop be slower than two built-in passes? Built-ins run in C; same Big-O, smaller constant factor.
- How do you get the k largest values efficiently?
heapq.nlargest(k, nums), O(n log k). - How would you find the min and max with fewer than 2n comparisons? Compare elements in pairs: about 1.5 n comparisons.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Largest / maximum | The biggest element | max([3, 9, 4]) → 9 |
| Empty list | A list with no elements | [] |
default= |
What max/min return for an empty input |
max([], default=None) → None |
ValueError |
Raised for a value that can't be used | max([]) |
IndexError |
Raised for an index outside the list | [7][-2] |
| Distinct | Different values (duplicates counted once) | set([5, 5, 3]) → {3, 5} |
float("-inf") |
Minus infinity, smaller than every number | initial first |
| Chained comparison | a > b > c = a > b and b > c |
first > x > second |
| Tuple assignment | Update several variables at once | first, second = x, first |
sorted() |
Returns a new sorted list | sorted([3, 1, 2]) → [1, 2, 3] |
set() |
Unordered collection without duplicates | set([4, 8, 8]) |
random.seed() |
Makes random numbers repeatable | random.seed(1) |
time.perf_counter() |
High-resolution stopwatch | timing sorted() |
| O(n log n) | Sorting-level growth | sorted() |
| Constant factor | The fixed cost per step that Big-O ignores | C built-ins vs a Python loop |
heapq.nlargest |
The k largest items, O(n log k) | heapq.nlargest(3, nums) |
| Stream | Values that arrive one at a time | sensor readings |
Summary
- Largest: start from a real element (
nums[0],max()), never from 0; decide what an empty list returns (default=). - Second largest = the next distinct value: one pass from
-infwithfirst > x > second, returningNonewhen there isn't one; orsorted(set(nums))with a length check (shorter, but O(n log n) time and O(n) space). - Min and max:
sorted()is O(n log n) and builds a new list;min()/max()are O(n). Same Big-O can still mean different real times: measure.
Next episode: List questions II: reverse in place, rotate by k (k larger than n), remove duplicates while keeping the order.