Skip to content

Volume ITechnology

4.0.15 — Largest, Smallest and Second Largest ​

Classic · Easy · the most-asked array question in service-company rounds

The problem ​

Given a list of numbers:

  1. Find the largest and the smallest.
  2. Find the second largest. In [12, 35, 1, 10, 34, 1] it is 34.
  3. Do it in one pass, without sorting.

1. Largest and smallest ​

This is the "keep the best so far" pattern from the largest-of-three warm-up in 4.0.2, stretched over a whole list.

python
def largest_smallest(nums: list[int]) -> tuple[int, int]:
    if not nums:
        raise ValueError("empty list")
    hi = lo = nums[0]            # (1)
    for x in nums[1:]:
        if x > hi:
            hi = x
        elif x < lo:             # (2)
            lo = x
    return hi, lo

print(largest_smallest([12, 35, 1, 10, 34, 1]))   # → (35, 1)
print(largest_smallest([-5, -2, -9]))             # → (-2, -9)

(1) Start with the first element as both the largest and the smallest. Do not start with 0. If every number is negative, a starting value of 0 would wrongly win as the largest. [-5, -2, -9] would give 0, which is not even in the list. This is the most common bug on this problem.

(2) elif is safe here. A number bigger than the current largest cannot also be smaller than the current smallest.

In real code, use max(nums) and min(nums).

2. Second largest ​

The sorting answer, and why it is not enough ​

sorted(nums)[-2] looks right. It has two problems. Sorting costs O(n \log n), when one pass of O(n) is enough. And with duplicates it gives the wrong answer. For [35, 35, 10] it returns 35, but the second largest distinct value is 10. Ask the interviewer which one they want. They almost always mean distinct.

One pass, keeping two values ​

Keep the largest seen so far, first, and the second largest, second. For each new number there are three cases.

  1. It beats first. The old champion drops to second place. The new number becomes first.
  2. It is between second and first. It takes second place. first does not change.
  3. Otherwise it is too small, or equal to first. Ignore it.
python
def second_largest(nums: list[int]) -> int | None:
    first = second = float("-inf")       # (1)
    for x in nums:
        if x > first:                    # (2)
            second = first
            first = x
        elif first > x > second:         # (3)
            second = x
    return second if second != float("-inf") else None   # (4)

print(second_largest([12, 35, 1, 10, 34, 1]))   # → 34
print(second_largest([35, 35, 10]))             # → 10
print(second_largest([7, 7, 7]))                # → None
print(second_largest([-3, -1, -2]))             # → -2

(1) float("-inf") is a value smaller than every number. It means "nothing seen yet". Starting both at 0 would break on all-negative lists, just like before.

(2) Case 1. The order of the two lines matters. Move the old first down before overwriting it. Swapping the two lines would lose the old champion.

(3) Case 2. Python lets you chain comparisons, so first > x > second means first > x and x > second. The first > x part is what skips duplicates of the largest. Without it, the second 35 in [35, 35, 10] would land in second place.

(4) If second never changed, there is no second largest. That happens when all values are equal, or the list has fewer than two elements.

Trace on [12, 35, 1, 10, 34, 1]:

xcasefirstsecond
12beats first12−∞
35beats first3512
1too small3512
10too small3512
34between3534
1too small3534

The answer is 34.

Second smallest is the same code with every comparison flipped and float("inf") as the start.

3. Largest and smallest with fewer comparisons ​

This is a tricky follow-up, asked by interviewers who like algorithms. The simple loop does up to 2 comparisons per element, about 2n in total. Can you do better?

Yes, by taking the numbers in pairs. First compare the two numbers of a pair with each other. Then only the bigger one can be a new largest, so compare it with hi. Only the smaller one can be a new smallest, so compare it with lo. That is 3 comparisons for every 2 numbers, instead of 4.

python
def min_max_pairs(nums: list[int]) -> tuple[int, int]:
    n = len(nums)
    if n % 2:                       # odd length: first element starts both
        lo = hi = nums[0]
        start = 1
    else:                           # even length: first pair starts them
        lo, hi = min(nums[0], nums[1]), max(nums[0], nums[1])
        start = 2
    for i in range(start, n - 1, 2):
        a, b = nums[i], nums[i + 1]
        if a > b:                   # 1 comparison inside the pair
            a, b = b, a             # now a is the smaller
        if a < lo:                  # only the smaller can be a new min
            lo = a
        if b > hi:                  # only the bigger can be a new max
            hi = b
    return lo, hi

print(min_max_pairs([12, 35, 1, 10, 34, 1]))   # → (1, 35)

That is about 1.5n comparisons instead of 2n. It is still O(n). Big-O ignores constant factors like 1.5 and 2, so this matters only when comparisons are expensive. It is a nice example that the same O(n) can hide different amounts of real work. It has also been proved that about 1.5n comparisons is the fewest possible for this task.

4. What about the k-th largest? ​

For k = 2, two variables are enough. For a general k, keeping k variables by hand gets messy. The tools for that come later. A heap of size k solves it in O(n \log k) (4.17.4). Quickselect, a cousin of the quicksort in 4.0.28, solves it in O(n) on average.

Complexity ​

Every version here is one pass, O(n) time and O(1) extra memory. Sorting first would be O(n \log n).

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"What if all the numbers are negative?" Start your "largest so far" with the first element or with negative infinity, never with 0. Starting with 0 would make 0 the answer, even though 0 is not in the list.

"What if the largest number appears twice?" Usually they want the second largest different value. For [35, 35, 10] that is 10. The check first > x > second makes sure a second 35 does not take second place.

"Do it without sorting." Keep two variables, first and second. When a number beats first, move first down into second before replacing it. One pass is enough.

"What if there is no second largest?" That happens when all values are the same or the list is too short. Return None, or ask what they want back.

"Find both the smallest and largest with fewer than 2n comparisons." Take the numbers in pairs. Compare the two in a pair first. Then compare only the bigger one with the max and only the smaller one with the min. That is 3 comparisons for every 2 numbers.

One thing to volunteer: "Sorting would also cost O(n \log n) and change the order of the list. One pass is faster and leaves the list as it was."

Next: 4.0.16 Frequency and Duplicates in an Array. Counting each element, finding repeats, and a clever trick that needs no extra memory.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet