Linear-Scan Patterns

The problem

You have a week of daily temperatures: [71, 68, 75, 75, 69, 82, 80]. You want the hottest day. Easy enough. But then the questions keep coming: what was the second hottest? Which days were warmer than both of their neighbours — the little local peaks? Each of these feels like it needs its own pass over the data.

It doesn't. A huge family of problems — running maximum, second largest, peaks, the index of the best element — all fall out of a single left-to-right sweep that remembers a tiny bit of state as it goes.

A first attempt

The obvious move for "second largest" is to sort the array descending and read index 1. Correct, but sorting is O(n log n) — you reorganized the entire week just to answer one question. And it quietly breaks on duplicates: sorting [75, 75, 71] gives 75 at index 1, but the second largest distinct value is 71.

Sorting throws away the one advantage you have: you only ever need to remember, never to reorder.

The insight

Walk the array once, carrying the answer-so-far. For the maximum, that's a single variable you bump up whenever you see something bigger. For the second largest, carry two variables — the best and the runner-up — and when a new value beats the best, the old best slides into second place.

That's the whole pattern: one pass, a handful of running variables. No sorting, no extra array, O(n) time and O(1) space.

How it works

Finding the two largest distinct values:

Sweeping [71, 68, 75, 75, 69, 82, 80]:

value:  71   68   75   75   69   82   80
best:   71   71   75   75   75   82   82
second: -∞   68   71   71   71   75   80

The code

def two_largest(arr):
    best = second = float("-inf")
    for value in arr:
        if value > best:
            second = best
            best = value
        elif best > value > second:
            second = value
    return best, second

function twoLargest(arr: number[]): [number, number] {
  let best = -Infinity;
  let second = -Infinity;
  for (const value of arr) {
    if (value > best) {
      second = best;
      best = value;
    } else if (value < best && value > second) {
      second = value;
    }
  }
  return [best, second];
}

int[] twoLargest(int[] arr) {
    long best = Long.MIN_VALUE, second = Long.MIN_VALUE;
    for (int value : arr) {
        if (value > best) {
            second = best;
            best = value;
        } else if (value < best && value > second) {
            second = value;
        }
    }
    return new int[] { (int) best, (int) second };
}

#include <limits.h>

void two_largest(const int arr[], int n, long *best, long *second) {
    *best = LONG_MIN;
    *second = LONG_MIN;
    for (int i = 0; i < n; i++) {
        if (arr[i] > *best) {
            *second = *best;
            *best = arr[i];
        } else if (arr[i] < *best && arr[i] > *second) {
            *second = arr[i];
        }
    }
}

#include <limits>

std::pair<long, long> twoLargest(const std::vector<int>& arr) {
    long best = std::numeric_limits<long>::min();
    long second = best;
    for (int value : arr) {
        if (value > best) {
            second = best;
            best = value;
        } else if (value < best && value > second) {
            second = value;
        }
    }
    return {best, second};
}

Complexity

Sorting to answer the same question would cost O(n log n) time — the single sweep is strictly better.

When to use it

Practice

Recap

• A large family of problems — max, second max, peaks, best index — need only one sweep carrying a constant amount of state.
• This beats sorting (O(n log n)) with O(n) time and O(1) space.
• The bugs live in the edges: seed maxima with negative infinity and pin down your duplicate and boundary conventions.