Maximum Score of a Good Subarray

Hard

#1640Time: O(N^2), where N is the length of the `nums` array. The outer loop runs `k+1` times, and the inner loops combined run in `O(N)` time for each `i`, leading to a total complexity of `O(k*N)`, which is `O(N^2)` in the worst case.Space: O(1), as we only use a constant amount of extra space for variables.

Patterns

Two Pointers

Algorithms

Binary Search

Data structures

Array Stack Monotonic Stack

Prompt

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.

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.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 2 * 10⁴
0 <= k < nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to check every possible "good" subarray. A subarray (i, j) is considered good if it contains the index k, which means i <= k <= j. We can use nested loops to generate all such subarrays, calculate their scores, and keep track of the maximum score.

Algorithm

Initialize maxScore to 0.
Iterate through all possible start indices i from 0 to k.
For each i, start an inner loop for all possible end indices j from k to n-1.
For each pair of (i, j), we have a "good" subarray.
To calculate the score, find the minimum element currentMin in the subarray nums[i...j].
Calculate the score as currentMin * (j - i + 1).
Update maxScore with the maximum score found so far.
To avoid a third loop which would make the complexity O(N^3), we can optimize finding the minimum. For a fixed i, as j increases, we can update the minimum in O(1) time.
The refined algorithm iterates i from 0 to k. For each i, it calculates the minimum from i to k, then extends to the right towards n-1, updating the minimum and score at each step.

Walkthrough

This method involves a brute-force check of all valid subarrays. We can set up two nested loops: the outer loop iterates through all possible start indices i from 0 to k, and the inner loop iterates through all possible end indices j from k to n-1.

A naive implementation would find the minimum of nums[i...j] in a third loop, leading to an O(N^3) complexity. We can optimize this to O(N^2) by noticing that for a fixed start i, as we expand the end j, the minimum of the subarray can be updated incrementally.

Here is the O(N^2) algorithm:

Initialize maxScore = 0.
Loop i from 0 to k.
Initialize min_i_to_k by finding the minimum in nums[i...k].
Loop j from k to n-1.
In this loop, update the overall minimum for nums[i...j] based on the previous minimum and nums[j].
Calculate the score for (i, j) and update maxScore.

1class Solution {2    public int maximumScore(int[] nums, int k) {3        int n = nums.length;4        int maxScore = 0;5 6        // Iterate through all possible start indices i <= k7        for (int i = 0; i <= k; i++) {8            int currentMin = nums[k];9            // Find minimum in the left part of the subarray [i, k]10            for (int p = k; p >= i; p--) {11                currentMin = Math.min(currentMin, nums[p]);12            }13 14            // Now expand to the right part [k, j]15            // The minimum from i to k is already computed in currentMin16            int minForSubarray = currentMin;17            for (int j = k; j < n; j++) {18                minForSubarray = Math.min(minForSubarray, nums[j]);19                int score = minForSubarray * (j - i + 1);20                maxScore = Math.max(maxScore, score);21            }22        }23        return maxScore;24    }25}

Complexity

Time

O(N^2), where N is the length of the `nums` array. The outer loop runs `k+1` times, and the inner loops combined run in `O(N)` time for each `i`, leading to a total complexity of `O(k*N)`, which is `O(N^2)` in the worst case.

Space

O(1), as we only use a constant amount of extra space for variables.

Trade-offs

Pros

It's relatively simple to understand and implement.
It correctly explores all possibilities and guarantees finding the optimal solution.

Cons

This approach is too slow for the given constraints (N up to 10^5) and will likely result in a 'Time Limit Exceeded' error on most platforms.

A much more efficient solution uses a two-pointer, greedy approach. We start with the smallest possible good subarray, which is just the element at index k. We then expand this subarray one element at a time, either to the left or to the right. The greedy choice at each step is to expand in the direction of the larger element. This strategy aims to keep the minimum value of the subarray as high as possible for as long as possible, which helps in maximizing the score.

Algorithm

Initialize two pointers, i and j, at index k.
Initialize maxScore and currentMin with the value nums[k].
Start a loop that continues as long as the subarray can be expanded (i.e., i > 0 or j < n-1).
Inside the loop, decide which pointer to move. Compare the values at the neighbors nums[i-1] and nums[j+1] (handling boundary cases where a neighbor doesn't exist).
Greedily move the pointer that points towards the larger neighbor. This is done to keep the currentMin as high as possible, thus maximizing the score.
If i is at the start (i=0), you must move j right.
If j is at the end (j=n-1), you must move i left.
Otherwise, if nums[i-1] > nums[j+1], move i left. Else, move j right.
After moving a pointer, update currentMin with the new element.
Calculate the score for the new subarray (i, j) as currentMin * (j - i + 1).
Update maxScore if the new score is greater.
Return maxScore after the loop finishes.

Walkthrough

We can think of this problem as finding an optimal balance between the minimum value of a subarray and its length. The two-pointer approach elegantly explores this trade-off.

We initialize pointers i and j to k. This represents the initial subarray (k, k). We then iteratively expand this window (i, j). At each step, we look at the elements just outside our current window, nums[i-1] and nums[j+1]. To maximize the score min * length, we want to increase the length while keeping min high. By expanding towards the larger of nums[i-1] and nums[j+1], we make a greedy choice that is less likely to decrease our current minimum. This process continues until the window has expanded to cover all elements that could potentially form a better-scoring subarray.

1class Solution {2    public int maximumScore(int[] nums, int k) {3        int n = nums.length;4        int i = k, j = k;5        int maxScore = nums[k];6        int currentMin = nums[k];7 8        // Expand the window [i, j] until it can't be expanded further9        while (i > 0 || j < n - 1) {10            // Get the values of potential next elements, handle boundaries by using 011            int leftVal = (i > 0) ? nums[i - 1] : 0;12            int rightVal = (j < n - 1) ? nums[j + 1] : 0;13 14            // Greedily expand towards the larger element15            if (leftVal > rightVal) {16                i--;17                currentMin = Math.min(currentMin, nums[i]);18            } else {19                j++;20                currentMin = Math.min(currentMin, nums[j]);21            }22            23            // Update the maximum score24            maxScore = Math.max(maxScore, currentMin * (j - i + 1));25        }26 27        return maxScore;28    }29}

Complexity

Time

O(N), where N is the length of the `nums` array. The pointers `i` and `j` start at `k` and together they traverse the rest of the array elements exactly once.

Space

O(1), as it only requires a few variables to keep track of the pointers and scores.

Trade-offs

Pros

This approach is highly efficient, with a linear time complexity.
It uses constant extra space, making it very memory-efficient.
It is the optimal solution for this problem.

Cons

The greedy logic, while correct, might not be immediately obvious and can be harder to reason about than a simple brute-force approach.

Solutions

Solution

1class Solution { public int maximumScore ( int [] nums , int k ) { int n = nums . length ; int [] left = new int [ n ]; int [] right = new int [ n ]; Arrays . fill ( left , - 1 ); Arrays . fill ( right , n ); Deque < Integer > stk = new ArrayDeque <>(); for ( int i = 0 ; i < n ; ++ i ) { int v = nums [ i ]; while (! stk . isEmpty () && nums [ stk . peek ()] >= v ) { stk . pop (); } if (! stk . isEmpty ()) { left [ i ] = stk . peek (); } stk . push ( i ); } stk . clear (); for ( int i = n - 1 ; i >= 0 ; -- i ) { int v = nums [ i ]; while (! stk . isEmpty () && nums [ stk . peek ()] > v ) { stk . pop (); } if (! stk . isEmpty ()) { right [ i ] = stk . peek (); } stk . push ( i ); } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( left [ i ] + 1 <= k && k <= right [ i ] - 1 ) { ans = Math . max ( ans , nums [ i ] * ( right [ i ] - left [ i ] - 1 )); } } return ans ; } }

1class Solution { public: int maximumScore ( vector < int >& nums , int k ) { int n = nums . size (); vector < int > left ( n , - 1 ); vector < int > right ( n , n ); stack < int > stk ; for ( int i = 0 ; i < n ; ++ i ) { int v = nums [ i ]; while ( ! stk . empty () && nums [ stk . top ()] >= v ) { stk . pop (); } if ( ! stk . empty ()) { left [ i ] = stk . top (); } stk . push ( i ); } stk = stack < int > (); for ( int i = n - 1 ; i >= 0 ; -- i ) { int v = nums [ i ]; while ( ! stk . empty () && nums [ stk . top ()] > v ) { stk . pop (); } if ( ! stk . empty ()) { right [ i ] = stk . top (); } stk . push ( i ); } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( left [ i ] + 1 <= k && k <= right [ i ] - 1 ) { ans = max ( ans , nums [ i ] * ( right [ i ] - left [ i ] - 1 )); } } return ans ; } };

1class Solution : def maximumScore ( self , nums : List [ int ], k : int ) -> int : n = len ( nums ) left = [ - 1 ] * n right = [ n ] * n stk = [] for i , v in enumerate ( nums ): while stk and nums [ stk [ - 1 ]] >= v : stk . pop () if stk : left [ i ] = stk [ - 1 ] stk . append ( i ) stk = [] for i in range ( n - 1 , - 1 , - 1 ): v = nums [ i ] while stk and nums [ stk [ - 1 ]] > v : stk . pop () if stk : right [ i ] = stk [ - 1 ] stk . append ( i ) ans = 0 for i , v in enumerate ( nums ): if left [ i ] + 1 <= k <= right [ i ] - 1 : ans = max ( ans , v * ( right [ i ] - left [ i ] - 1 )) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem