LeetCode Solutions Blog

Maximum Score of a Good Subarray

Number: 1918

Difficulty: Hard

Paid? No

Problem Description

Given an integer array and an index k, the task is to find the maximum score of any subarray that contains the index k. The score of a subarray is defined as the minimum element in that subarray multiplied by the subarray’s length.

Key Insights

The subarray must include the given index k.
Starting from k, we can expand the subarray greedily to include as many elements as possible while keeping track of the running minimum.
At every step, the expansion is limited by the smaller neighbor, as that will determine the new subarray minimum.
The problem can be solved in O(n) time by two pointers expanding from the fixed index.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(1)

Solution

The approach begins at index k with a subarray that only contains nums[k]. Two pointers (left and right) are initialized at k. At each step, decide whether to move the left pointer one step left or the right pointer one step right. Choose the direction that has a larger neighbor so that the running minimum does not drop too quickly. Update the running minimum with the minimum between the current value and the newly added element. Calculate the subarray score at every step and update the best score. Continue until both pointers have spanned the entire array.

Code Solutions

# Function to calculate the maximum score of a good subarray
def maximumScore(nums, k):
    # Initialize pointers to the given index
    left, right = k, k
    # Current minimum is the element at index k
    current_min = nums[k]
    # Initial best score is just nums[k] (subarray of length 1)
    best_score = current_min

    # Expand the subarray boundaries while there are elements on either side
    while left > 0 or right < len(nums) - 1:
        # Check if we can move left and right, and choose the direction which has a higher value
        if right < len(nums) - 1 and (left == 0 or nums[left - 1] < nums[right + 1]):
            # Expand to the right
            right += 1
            current_min = min(current_min, nums[right])
        else:
            # Expand to the left
            left -= 1
            current_min = min(current_min, nums[left])
        
        # Calculate the new score: current minimum * current subarray length
        best_score = max(best_score, current_min * (right - left + 1))
    
    return best_score

# Example usage
if __name__ == '__main__':
    print(maximumScore([1,4,3,7,4,5], 3))  # Expected output: 15