Code Implementation

class Solution:
    def maximumScore(self, nums, k):
        n = len(nums)
        left = right = k
        min_val = nums[k]
        max_score = min_val

        while left > 0 or right < n - 1:
            if left == 0:
                right += 1
            elif right == n - 1:
                left -= 1
            elif nums[left - 1] > nums[right + 1]:
                left -= 1
            else:
                right += 1
            min_val = min(min_val, nums[left], nums[right])
            max_score = max(max_score, min_val * (right - left + 1))
        return max_score
      

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        int left = k, right = k;
        int minVal = nums[k];
        int maxScore = minVal;

        while (left > 0 || right < n - 1) {
            if (left == 0)
                ++right;
            else if (right == n - 1)
                --left;
            else if (nums[left - 1] > nums[right + 1])
                --left;
            else
                ++right;
            minVal = min(minVal, min(nums[left], nums[right]));
            maxScore = max(maxScore, minVal * (right - left + 1));
        }
        return maxScore;
    }
};
      

class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;
        int left = k, right = k;
        int minVal = nums[k];
        int maxScore = minVal;

        while (left > 0 || right < n - 1) {
            if (left == 0) {
                right++;
            } else if (right == n - 1) {
                left--;
            } else if (nums[left - 1] > nums[right + 1]) {
                left--;
            } else {
                right++;
            }
            minVal = Math.min(minVal, Math.min(nums[left], nums[right]));
            maxScore = Math.max(maxScore, minVal * (right - left + 1));
        }
        return maxScore;
    }
}
      

var maximumScore = function(nums, k) {
    let n = nums.length;
    let left = k, right = k;
    let minVal = nums[k];
    let maxScore = minVal;

    while (left > 0 || right < n - 1) {
        if (left === 0) {
            right++;
        } else if (right === n - 1) {
            left--;
        } else if (nums[left - 1] > nums[right + 1]) {
            left--;
        } else {
            right++;
        }
        minVal = Math.min(minVal, nums[left], nums[right]);
        maxScore = Math.max(maxScore, minVal * (right - left + 1));
    }
    return maxScore;
};
      

Problem Description

You are given an integer array nums and an integer k. Your task is to find the maximum possible score for any subarray that contains the index k. The score of a subarray is defined as the minimum value in the subarray multiplied by the length of the subarray.

Key constraints:

• The subarray must include the index k.
• You may expand the subarray to the left or right, but it must always be contiguous and include k.
• There is guaranteed to be at least one valid subarray (the single element at k).

Thought Process

At first glance, it seems we could check every possible subarray containing k, calculate the minimum value in each, multiply by its length, and keep track of the maximum score found. However, this brute-force approach would be too slow for large arrays because it involves checking many overlapping subarrays and repeatedly finding minimums, which is inefficient.

To optimize, we need a way to efficiently expand the subarray from k and update the minimum value without re-scanning the whole subarray each time. Instead of checking all possible subarrays, we can start with the smallest subarray (just k itself), and then expand one element at a time to the left or right, always keeping track of the current minimum and updating the score. At each step, we choose the direction (left or right) that gives us a higher next element, so the minimum value drops as slowly as possible, maximizing the score.

Solution Approach

Let's break down the optimized algorithm step by step:

1. Initialize pointers: Set two pointers, left and right, both at k. This marks the current subarray as just the single element at k.
2. Track the minimum: Keep a variable minVal to record the minimum value in the current subarray. Initially, it's nums[k].
3. Expand window: While left can move left or right can move right:
   • If left is at 0, we can only move right (and vice versa).
   • Otherwise, compare nums[left - 1] and nums[right + 1]. Move in the direction with the larger value, because this will keep our minimum value as high as possible for longer, maximizing the score.
   • Update minVal to be the minimum of the current minVal and the new value included by expanding.
   • Calculate the current score: minVal * (right - left + 1).
   • Update the maximum score found so far if the current score is higher.
4. Finish: When neither left nor right can expand, return the maximum score found.

This approach works efficiently because each element is considered at most once as the window expands, and we always know the minimum in the current window without needing to scan it.

Example Walkthrough

Let's walk through an example with nums = [1,4,3,7,4,5] and k = 3.

1. Start with left = 3, right = 3, minVal = 7, maxScore = 7.
2. Expand. nums[2]=3 (left), nums[4]=4 (right). Since 4 > 3, expand right:
   • right = 4, minVal = min(7,4)=4, window is [7,4], score = 4*2=8, maxScore=8.
3. Expand. nums[2]=3 (left), nums[5]=5 (right). 5 > 3, expand right:
   • right = 5, minVal = min(4,5)=4, window is [7,4,5], score = 4*3=12, maxScore=12.
4. Can't expand right (at end). Expand left:
   • left = 2, minVal = min(4,3)=3, window is [3,7,4,5], score = 3*4=12, maxScore=12.
5. Expand left:
   • left = 1, minVal = min(3,4)=3, window is [4,3,7,4,5], score = 3*5=15, maxScore=15.
6. Expand left:
   • left = 0, minVal = min(3,1)=1, window is [1,4,3,7,4,5], score = 1*6=6, maxScore=15.
7. Now both ends reached. The answer is 15.

Time and Space Complexity

• Brute-force approach: For each possible subarray containing k, we scan to find the minimum (O(N) per subarray), and there are O(N²) such subarrays. So total time is O(N³).
• Optimized approach (this solution): We expand the window from k left and right, at each step moving one pointer and updating the minimum in O(1) time. Overall, each pointer moves at most N times, so the total time is O(N).
• Space complexity: Both approaches use O(1) extra space (excluding input).

Summary

The key to solving the "Maximum Score of a Good Subarray" problem efficiently is to avoid brute-force checking all possible subarrays. Instead, by expanding a window from k and always choosing to include the larger next element, we keep the minimum value high for as long as possible. This greedy approach ensures we consider all the best possible windows in linear time. The algorithm is both efficient and elegant, making use of two pointers and a running minimum to achieve optimal performance.