Scale Engineer

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
ArrayStackMonotonic 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 <= 105
  • 1 <= nums[i] <= 2 * 104
  • 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:

  1. Initialize maxScore = 0.
  2. Loop i from 0 to k.
  3. Initialize min_i_to_k by finding the minimum in nums[i...k].
  4. Loop j from k to n-1.
  5. In this loop, update the overall minimum for nums[i...j] based on the previous minimum and nums[j].
  6. Calculate the score for (i, j) and update maxScore.
class Solution {    public int maximumScore(int[] nums, int k) {        int n = nums.length;        int maxScore = 0;         // Iterate through all possible start indices i <= k        for (int i = 0; i <= k; i++) {            int currentMin = nums[k];            // Find minimum in the left part of the subarray [i, k]            for (int p = k; p >= i; p--) {                currentMin = Math.min(currentMin, nums[p]);            }             // Now expand to the right part [k, j]            // The minimum from i to k is already computed in currentMin            int minForSubarray = currentMin;            for (int j = k; j < n; j++) {                minForSubarray = Math.min(minForSubarray, nums[j]);                int score = minForSubarray * (j - i + 1);                maxScore = Math.max(maxScore, score);            }        }        return maxScore;    }}

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.

Solutions

class 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 ; } }

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 →

Next problem