Maximum Score of a Good Subarray

How it works

Start with just the element at index k as our subarray. To expand, we have two choices: go left or go right. The key insight is that we should always expand toward the larger neighbor. This greedy choice maximizes the minimum value we can maintain for as long as possible, leading to higher scores. We continue until we have expanded to cover the entire array.

Steps

1. Initialize pointers l = r = k and track the current minimum starting with nums[k].
2. While we can still expand (l > 0 or r < n-1):
   • Compare the left neighbor (if exists) with the right neighbor (if exists).
   • Expand toward the larger one (or whichever exists).
   • Update the current minimum with the newly included element.
   • Calculate the score and update the result.
3. Return the maximum score.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Forgetting the Subarray Must Include Index k

The problem requires the subarray to contain index k. A common mistake is computing the maximum score over all subarrays without enforcing this constraint. In the monotonic stack approach, you must check that the range [left, right] actually contains k before updating the result. Skipping this check leads to incorrect answers when the global maximum rectangle doesn't include k.

Off-by-One Errors in Boundary Calculations

When computing the left and right boundaries of a valid subarray, it's easy to be off by one. The valid range for an element at index i extends from prev_smaller + 1 to next_smaller - 1, not from prev_smaller to next_smaller. Miscalculating these boundaries causes incorrect subarray lengths and wrong scores.

Expanding in the Wrong Direction with Two Pointers

In the greedy two-pointer approach, you should always expand toward the larger neighbor to maintain the highest possible minimum for as long as possible. Expanding toward the smaller neighbor prematurely reduces the minimum value, potentially missing the optimal score. Always compare nums[l-1] with nums[r+1] and expand toward the larger one.

Not Handling Edge Cases at Array Boundaries

When the left pointer reaches 0 or the right pointer reaches n-1, you can only expand in one direction. Failing to handle these boundary conditions (e.g., accessing nums[-1] or nums[n]) causes index out of bounds errors. Use sentinel values or explicit boundary checks to handle these cases gracefully.

Misunderstanding the Score Formula

The score is min(subarray) * length(subarray), not min(subarray) * sum(subarray). Confusing this formula with similar problems leads to computing the wrong value entirely. Always verify you're multiplying the minimum element by the subarray length, not its sum.

from typing import List

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        l = r = k
        res = nums[k]
        cur_min = nums[k]

        while l > 0 or r < len(nums) - 1:
            left = nums[l - 1] if l > 0 else 0
            right = nums[r + 1] if r < len(nums) - 1 else 0

            if left > right:
                l -= 1
                cur_min = min(cur_min, left)
            else:
                r += 1
                cur_min = min(cur_min, right)

            res = max(res, cur_min * (r - l + 1))

        return res

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int l = k, r = k;
        int res = nums[k];
        int curMin = nums[k];
        int n = nums.size();

        while (l > 0 || r < n - 1) {
            int left = (l > 0) ? nums[l - 1] : 0;
            int right = (r < n - 1) ? nums[r + 1] : 0;

            if (left > right) {
                l--;
                curMin = min(curMin, left);
            } else {
                r++;
                curMin = min(curMin, right);
            }

            res = max(res, curMin * (r - l + 1));
        }

        return res;
    }
};