Track the Best So Far

Track the Best So Far means you walk through the data once and keep a small variable (or two) that remembers the largest, smallest or best answer seen up to this point. At each new element you ask, "Does this beat my current best?" and update if it does. Interviewers like it because it tests whether you can replace a slow nested loop with a clean O(n) pass and pick the right things to remember.

When to use it

  • The question asks for the maximum, minimum, largest, smallest or best value in a list.
  • You only need one answer, not every pair or every subarray listed out.
  • A brute-force solution compares every element with every other element, and you suspect that is wasteful.
  • The best answer ending at position i depends only on what you saw before position i.
  • The problem asks for a best difference, best profit or best running total, such as buying low and selling high.

See it work

  1. Problem: find the best profit from buying on one day and selling on a later day, with prices [7, 1, 5, 3, 6, 4]. We track two things: the lowest price seen so far (min_price) and the best profit so far (best). Start with min_price = 7 and best = 0 at index 0. [7, 1, 5, 3, 6, 4]
  2. Index 1, price 1. It is lower than min_price, so update min_price = 1. Selling today would give 1 - 7 = -6, which is worse than doing nothing, so best stays 0. [7, 1, 5, 3, 6, 4]
  3. Index 2, price 5. Selling today gives 5 - 1 = 4, which beats best = 0, so best = 4. min_price stays 1. [7, 1, 5, 3, 6, 4]
  4. Index 3, price 3. Selling today gives 3 - 1 = 2, which is less than 4. Nothing changes. [7, 1, 5, 3, 6, 4]
  5. Index 4, price 6. Selling today gives 6 - 1 = 5, which beats 4, so best = 5. This is the buy-at-1, sell-at-6 trade. [7, 1, 5, 3, 6, 4]
  6. Index 5, price 4. Selling today gives 4 - 1 = 3, which is less than 5. We have finished one pass and return best = 5, using only two variables and O(n) time. [7, 1, 5, 3, 6, 4]

Code template

Python

def track_best(nums):
    # Start from the first element so negative numbers work too
    best = nums[0]          # best answer seen so far
    running = nums[0]       # extra state, if the problem needs it

    for x in nums[1:]:
        # Update any helper state using the new element
        running = max(x, running + x)
        # Compare the new candidate with the best so far
        if running > best:
            best = running

    return best  # the answer after one pass

C

int track_best(const int *nums, int n) {
    /* Start from the first element so negative numbers work too */
    int best = nums[0];      /* best answer seen so far */
    int running = nums[0];   /* extra state, if the problem needs it */

    for (int i = 1; i < n; i++) {
        int x = nums[i];
        /* Update any helper state using the new element */
        running = (x > running + x) ? x : running + x;
        /* Compare the new candidate with the best so far */
        if (running > best) {
            best = running;
        }
    }
    return best; /* the answer after one pass */
}

Java

static int trackBest(int[] nums) {
    // Start from the first element so negative numbers work too
    int best = nums[0];      // best answer seen so far
    int running = nums[0];   // extra state, if the problem needs it

    for (int i = 1; i < nums.length; i++) {
        int x = nums[i];
        // Update any helper state using the new element
        running = Math.max(x, running + x);
        // Compare the new candidate with the best so far
        if (running > best) {
            best = running;
        }
    }
    return best; // the answer after one pass
}

Complexity: Time is O(n) because you visit each element once; space is O(1) because you only store a few variables.

Programs that use it

Interview problems that use it

  • Best Time to Buy and Sell Stock: Keep the lowest price seen so far and, at each day, check whether selling today beats the best profit recorded.
  • Maximum Subarray Sum: Keep the best sum of a subarray ending at the current element (extend it or restart) and the overall best across all positions.
  • Second Largest Element: Track both the largest and second-largest values, shifting the old largest down when a new maximum appears.
  • Maximum Product Subarray: Track both the max and min product ending here, since a negative number can flip the smallest into the largest.
  • Longest Consecutive Run of Ones: Keep a current streak counter that resets on a zero, and a best streak that records the largest counter seen.
  • Maximum Score of a Pair of Sightseeing Spots: Keep the best value of (values[i] + i) from earlier spots, and combine it with each new spot's (values[j] - j) to update the best score.

Common mistakes

  • Initializing best to 0 (or to a huge sentinel) instead of the first element, which gives wrong answers when every number is negative.
  • Updating the best before updating the helper state in the wrong order, such as comparing against a min_price that already includes today's price when buying and selling on the same day is not allowed.
  • Forgetting to handle an empty or single-element input, which causes an index error or an incorrect default answer.

Frequently asked questions

How is this different from just sorting the array?

Sorting costs O(n log n) and rearranges the data, while tracking the best so far finds the answer in a single O(n) pass with O(1) extra space. If you only need one max, min or best value, a single pass is faster and simpler.

Is track the best so far the same as Kadane's algorithm?

Kadane's algorithm is one well-known example of it. It tracks the best sum ending at the current index plus the best overall. The general pattern also covers simple cases like finding a maximum or the best stock profit.

What should I initialize the best value to?

Use the first element of the array when it exists, or negative infinity for a max (positive infinity for a min). Avoid starting at 0 unless an empty or zero result is truly a valid answer, since that breaks inputs with all negative numbers.

← All interview patterns

Try AI Flowchart free →