Maximum Score of a Good Subarray - Video Solutions

Problem Overview: You are given an array nums and an index k. A subarray is considered good if it includes index k. The score of a subarray equals min(nums[i..j]) * (j - i + 1). The goal is to find the maximum score among all good subarrays.

Approach 1: Sliding Window with Two Pointers (O(n) time, O(1) space)

Start with both pointers at index k. The current subarray always includes k, so the score depends on the minimum value in the window and its length. Expand the window outward by choosing the side with the larger adjacent value (nums[left-1] vs nums[right+1]). This greedy choice delays reducing the minimum element as long as possible, which helps maximize the product. After each expansion, update the running minimum and compute minVal * windowLength. Continue until the window covers the entire array. This approach relies on careful pointer movement and constant-time comparisons, making it an efficient linear pass using the two pointers pattern on an array.

Approach 2: Monotonic Stack (O(n) time, O(n) space)

Another perspective treats each element as the potential minimum of a subarray. Using a monotonic stack, compute the nearest smaller element to the left and right for every index. This gives the maximum range where nums[i] remains the minimum. For each index i, the valid subarray range is (left[i] + 1, right[i] - 1). Only consider ranges that include index k. If the interval covers k, compute the score using nums[i] * (right[i] - left[i] - 1). The stack ensures each element is pushed and popped once, giving linear time complexity.

Recommended for interviews: The sliding window expansion from k is usually the expected solution. It demonstrates strong intuition about greedy pointer movement and window expansion. The monotonic stack approach is more general and mirrors the pattern used in problems like Largest Rectangle in Histogram, but it requires additional arrays and reasoning about boundaries. Showing the greedy two‑pointer idea first proves you understand the structure of the problem, while the stack solution shows deeper algorithmic flexibility.