Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close
01 / WHAT IT SOLVES

Maximum, minimum and top-k questions where the answer can be updated incrementally.

02 / HOW TO RECOGNIZE IT
  • largest or smallest seen so far
  • one result from an unsorted input
  • sorting feels unnecessary
03 / PROTECT THIS INVARIANT

The running variables contain the best valid answer for the prefix already processed.

04 / EXPECTED COST

Usually O(n) time. Typical auxiliary space: Usually O(1).

JAVA STARTING POINT

A template to adapt, not memorize.

Java
int best = values[0];
for (int index = 1; index < values.length; index++) {
    best = Math.max(best, values[index]);
}

Common mistakes

  • Using zero as the initial answer
  • Updating dependent answers in the wrong order
  • Ignoring duplicate rules

PUBLISHED / 02

Learn in this order.

Available articles always appear before the publishing plan.

PLANNED PRACTICE

What comes after the published lessons.

  1. Third largest distinct valuePlanned, not yet published
  2. Best time to buy and sell stockPlanned, not yet published