Maximum Score of a Good Subarray

Maximum Score of a Good Subarray

1. What is this problem about?

The Maximum Score of a Good Subarray interview question is a high-level array problem that combines range optimization with a specific constraint. You are given an array nums and an index k. A "good" subarray is a contiguous subarray nums[i...j] such that i <= k <= j. The score of a subarray is defined as min(nums[i...j]) * (j - i + 1).

The goal is to find the maximum possible score among all "good" subarrays.

2. Why is this asked in interviews?

Google asks the Maximum Score of a Good Subarray coding problem to evaluate a candidate's ability to optimize search using Two Pointers or Monotonic Stacks. It tests whether you can recognize that as you expand the subarray from the starting point k, the minimum value only decreases or stays the same. It evaluates your ability to make locally optimal expansion decisions to find the global maximum score.

3. Algorithmic pattern used

The Array, Monotonic Stack, Two Pointers, Binary Search, Stack interview pattern applies. The most intuitive and efficient approach is the Two-Pointer method:

1. Start with left = k and right = k. Initialize min_val = nums[k].
2. Expand the window by moving either left or right.
3. Greedy Choice: Move the pointer that points to the larger value between nums[left-1] and nums[right+1]. This keeps the min_val of the new window as high as possible.
4. Update min_val and calculate score = min_val * (right - left + 1).
5. Continue until both pointers reach the array boundaries.

4. Example explanation

nums: [1, 4, 3, 7, 4, 5], k = 3.

• i=3, j=3: min=7. Score = 7 * 1 = 7.
• Neighbors: nums[2]=3, nums[4]=4. Pick 4 (right).
• i=3, j=4: min=min(7,4)=4. Score = 4 * 2 = 8.
• Neighbors: nums[2]=3, nums[5]=5. Pick 5 (right).
• i=3, j=5: min=min(4,5)=4. Score = 4 * 3 = 12.
• Neighbors: nums[2]=3. Pick 3 (left).
• i=2, j=5: min=min(4,3)=3. Score = 3 * 4 = 12. ... and so on. Max score = 12.

5. Common mistakes candidates make

A common mistake in the Maximum Score of a Good Subarray coding problem is using a brute-force $O(N^2)$ approach, checking all pairs $(i, j)$. Another error is not correctly handling the greedy expansion—perhaps always moving one pointer first or moving based on a wrong condition. Candidates also sometimes forget that the minimum value must be updated every time the window expands.

6. Interview preparation tip

When you need to expand from a specific index while maintaining a property (like a minimum or maximum), Two Pointers with a greedy expansion is often the best approach. Practice this "expanding window" technique as it's a common variation of the standard sliding window.