Problem

You are given an array of integers nums (0-indexed) and an integer k.

The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A good subarray is a subarray where i <= k <= j.

Return the maximum possible score of a good subarray.

Examples

Example 1:

Input:
nums = [1,4,3,7,4,5], k = 3
Output:
 15
Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15.

Example 2:

Input:
nums = [5,5,4,5,4,1,1,1], k = 0
Output:
 20
Explanation: The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.

Solution

Method 1 - Two Pointer Technique

We need to find the subarray that includes the index k (from i to j where i <= k <= j) and maximizes the score defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1).

Here is the approach:

  1. Start with the subarray that only contains the element at index k.
  2. Expand the subarray to the left and right, one element at a time, while keeping track of the minimum element in the subarray.
  3. For each expansion, calculate the score and keep track of the maximum score encountered.

Code

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

        while (left > 0 || right < n - 1) {
            if (left == 0) {
                right++;
            } else if (right == n - 1) {
                left--;
            } else if (nums[left - 1] < nums[right + 1]) {
                right++;
            } else {
                left--;
            }

            minElement =
                Math.min(minElement, Math.min(nums[left], nums[right]));
            int currentScore = minElement * (right - left + 1);
            maxScore = Math.max(maxScore, currentScore);
        }

        return maxScore;
    }
}
Python
class Solution:
    def maximumScore(self, nums, k):
        n = len(nums)
        left = right = k
        minElement = nums[k]
        maxScore = minElement

        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]:
                right += 1
            else:
                left -= 1
            minElement = min(minElement, min(nums[left], nums[right]))
            currentScore = minElement * (right - left + 1)
            maxScore = max(maxScore, currentScore)

        return maxScore

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the nums array. This is because we potentially expand the subarray at most n times.
  • 🧺 Space complexity: O(1), as we use a constant amount of extra space regardless of the size of the input array.