Maximum Score of a Good Subarray: Two-Pointer Expansion

You are given an integer array nums and an integer k. A subarray (i, j) is called good if i <= k <= j. The score of a subarray is defined as min(nums[i..j]) * (j - i + 1). Return the maximum possible score of a good subarray.

This is LeetCode 1793: Maximum Score of a Good Subarray.

Why this problem matters

At first glance, this looks like it might require checking every subarray that contains index k, which would be O(n^2). But the constraint that the subarray must include k is actually what makes a greedy approach possible. Instead of scanning all pairs (i, j), you can start at k and expand outward one index at a time, always picking the direction that keeps the minimum value as high as possible.

This problem is closely related to the classic "Largest Rectangle in Histogram" (LeetCode 84). In that problem, you find the maximum area rectangle under a histogram of bars. Here, you are doing something similar: you want to maximize min * width over a contiguous range of bars, but with the added constraint that the range must include a specific index. The greedy expansion approach works because the minimum can only decrease (or stay the same) as you widen the window. Once you expand, you never need to shrink back.

Understanding this greedy pattern also helps with problems like "Container With Most Water" and "Trapping Rain Water," where the idea of expanding or contracting a window while tracking a running extremum is central.

The key insight

Start with i = j = k. The window contains just one element, so the minimum is nums[k] and the width is 1. Now consider expanding: you can move i one step left or j one step right. Which should you pick?

The minimum of the window can only stay the same or drop when you include a new element. So you want to include whichever neighbor is larger, because that gives you the best chance of keeping the minimum high. If nums[i - 1] >= nums[j + 1], expand left. Otherwise, expand right. After each expansion, update the running minimum and compute the new score. Track the best score seen.

This greedy choice works because the minimum is monotonically non-increasing as the window grows. Once you skip a larger neighbor in favor of a smaller one, you would never get a better score by revisiting that choice later. The larger neighbor will still be there when you eventually include it, but by then the minimum will already be at least as low.

The solution

def maximum_score(nums: list[int], k: int) -> int:
    n = len(nums)
    i = j = k
    min_val = nums[k]
    result = min_val

    while i > 0 or j < n - 1:
        left = nums[i - 1] if i > 0 else 0
        right = nums[j + 1] if j < n - 1 else 0

        if left >= right:
            i -= 1
            min_val = min(min_val, nums[i])
        else:
            j += 1
            min_val = min(min_val, nums[j])

        result = max(result, min_val * (j - i + 1))

    return result

The loop runs until both pointers hit their respective walls. At each step, we look at the values immediately outside the current window. If the left neighbor is at least as large as the right neighbor, we expand left. Otherwise, we expand right. When a pointer is already at the boundary, we treat its neighbor as 0, which forces expansion in the other direction.

After each expansion, min_val is updated to account for the newly included element. The score for the current window is min_val * (j - i + 1), and we keep a running maximum.

The key detail: when i hits 0 and cannot go further left, left becomes 0. This guarantees we will expand right for all remaining iterations (since right >= 0 always holds with positive array values). The same logic applies symmetrically when j hits n - 1.

Visual walkthrough

Let's trace through nums = [1, 4, 3, 7, 4, 5] with k = 3. We start at index 3 and greedily expand outward, picking the larger neighbor at each step.

Notice how the best score of 15 occurs at step 4 with window [1..5] and min = 3. Expanding further to include index 0 drops the min to 1 and the score plummets to 6. The greedy approach naturally explores this, but the running maximum captures the peak before the decline.

Complexity analysis

Time is O(n) because each pointer moves at most n times total. The left pointer moves from k down to 0 (at most k steps), and the right pointer moves from k up to n - 1 (at most n - 1 - k steps). Together, that is exactly n - 1 expansion steps. Each step does O(1) work: one comparison, one pointer move, one min update, one max update.

Space is O(1). We only track four variables: i, j, min_val, and result. No auxiliary data structures are needed.

The building blocks

1. Two-pointer expansion from a fixed center

The pattern of starting at a known position and expanding outward one step at a time:

i = j = center
while i > 0 or j < n - 1:
    if should_expand_left(i, j):
        i -= 1
    else:
        j += 1

You see this same pattern in "Longest Palindromic Substring" (expand around center) and in several interval/window problems. The key property that makes it work: you have a clear greedy criterion for which direction to expand, and the window never needs to shrink.

2. Running minimum tracking

Maintaining a running minimum as elements are added to a growing window:

min_val = initial_value
for new_element in stream:
    min_val = min(min_val, new_element)

This only works when the window grows monotonically (elements are added but never removed). If elements can leave the window, you need a more sophisticated structure like a monotonic deque. Here, since the window only expands, a simple variable suffices.

Edge cases

• Single element array: nums = [5], k = 0. The only subarray is [5], so the score is 5.
• k at the left boundary: k = 0. The left pointer never moves. All expansion goes right.
• k at the right boundary: k = n - 1. The right pointer never moves. All expansion goes left.
• All elements equal: Every expansion keeps the same minimum. The best score is nums[0] * n, achieved when the window covers the full array.
• Descending array with k at the end: The minimum drops with every left expansion. The best score might be just nums[k] * 1.
• Array with zeros: A zero in the window drops the minimum to 0, making the score 0. The best score was found before including that zero.

From understanding to recall

The two-pointer greedy expansion is a clean and elegant approach. Start at k, look left and right, pick the bigger neighbor, update the min, compute the score. The logic fits in about ten lines. But under interview pressure, the details matter. Do you use >= or > when comparing left and right? What value do you assign when a pointer is at the wall? Do you update min_val before or after computing the score?

These are not conceptual mistakes. They are recall gaps. You understand the algorithm perfectly, but the precise implementation slips under stress. Spaced repetition closes that gap. You write the two-pointer expansion from scratch, check against the reference, and repeat at increasing intervals. After a few rounds, the code flows out automatically. You see "maximize min * width with a constraint" in a problem, and your hands type the template before your brain finishes parsing the description.

Related posts

• Largest Rectangle in Histogram - The classic monotonic stack problem for maximizing rectangle area under a histogram, which is the generalization of this problem without the k constraint
• Container With Most Water - Two-pointer approach for area maximization where you contract inward instead of expanding outward
• Trapping Rain Water - Array bar problems with prefix min/max logic, another member of the "histogram family" of problems

CodeBricks breaks Maximum Score of a Good Subarray into its two-pointer expansion and running minimum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy expansion problem shows up in your interview, you do not hesitate. You just write it.