1793. Maximum Score of a Good Subarray

Problem Description

Given an array nums of integers and an integer k, we need to find the maximum score of a "good" subarray. A subarray is defined by its start and end indices (i, j), and its score is calculated as the minimum value in the subarray multiplied by the subarray's length, which is (j - i + 1). A "good" subarray is one where the index k is included in the subarray; therefore, i <= k <= j.

The problem asks for the maximum score that can be achieved by any "good" subarray. To solve this problem, we must efficiently find subarrays that include k and also have high scores, which are a product of its minimum element and its length.

Intuition

To find the maximum possible score of a good subarray, we can use a two-step approach:

1. First, we need to precompute for each index in the array, the nearest indices on the left and on the right that have a value lesser than the value at the current index. To perform this, we use two passes with the help of a stack.

   In the first pass, from left to right, we use the stack to track indices with increasing values. For each index i, if there's a lesser value than nums[i], we pop from the stack until we find the correct position where the value at nums[i] should be. The element that would be at the top of the stack after popping would be the nearest smaller element on the left. We store this index in an array left[].

   Similarly, we perform another pass, this time from right to left to fill out the right[] array for the nearest smaller element on the right.

2. With left[] and right[] arrays at hand, we can iterate over all indices of the array again, and for each index, we check if the good subarray criteria are met i.e., left[i] < k < right[i]. If the criteria are met for an index i, we calculate the score for the subarray using nums[i] as the minimum value and (right[i] - left[i] - 1) as the length of the subarray, and we keep track of the maximum score found so far.

This method works because we are iterating through all possible subarrays that include the index k while efficiently computing their minimums using the preprocessed left and right arrays, avoiding redundant calculations.

Learn more about Stack, Two Pointers, Binary Search and Monotonic Stack patterns.

Solution Approach

The solution uses a monotonic stack and two auxiliary arrays (left and right) to find the maximum score of a good subarray. A monotonic stack is a stack where the elements are arranged according to a clear hierarchical order, either strictly increasing or decreasing. This characteristic of the monotonic stack is a key component of the solution and here is a detailed walk-through:

1. Auxiliary Arrays (left and right):

   • Create two arrays left and right of the same length as the input array nums, initialized to -1 and n respectively, where n is the length of nums. These arrays will store for each element in nums the index of the nearest smaller element on the left and on the right, respectively.

2. Finding Nearest Smaller Elements on the Left:

   • Initialize an empty list stk to be used as a stack.
   • Iterate over each index i (from 0 to n-1) of nums:
     • While the stack is not empty and the top element of the stack (nums[stk[-1]]) is greater than or equal to the current element (nums[i]), pop elements from the stack since they are not the nearest smaller elements for the current index i.
     • If the stack is not empty after the popping process, the top element of the stack (stk[-1]) is the nearest smaller element on the left of the current element. We record this index in left[i].
     • Push the current index i onto the stack.

3. Finding Nearest Smaller Elements on the Right:

   • Clear the stack stk for reuse in this step.
   • Iterate over each index i starting from the last index (n-1) to the first index (0):
     • While the stack is not empty and the top element of the stack (nums[stk[-1]]) is greater than the current element (nums[i]), pop elements from the stack.
     • If the stack is not empty after popping, the top element of the stack (stk[-1]) is the nearest smaller element on the right of the current element. We record this index in right[i].
     • Push the current index i onto the stack.

4. Calculating the Maximum Score:

   • Initialize ans to 0 which will store the result.
   • Iterate over each index i of nums:
     • Check if i can be a starting index for a good subarray by ensuring the conditions left[i] < k < right[i] are satisfied.
     • If i can be a starting index for a good subarray, calculate the score as the product of nums[i] (minimum value for this subarray) and the length of the subarray (right[i] - left[i] - 1).
     • Update ans if the calculated score is greater than the current value of ans.

5. Return the Maximum Score:

   • After iterating over all indices, ans holds the maximum score for a good subarray, and we return it as the result.

The algorithms and data structures used in this solution—namely, the stack for finding the nearest smaller elements and the efficient iteration over the indices—ensure that every good subarray is considered, and the maximum score is calculated without redundant computations, leading to an optimal solution.

Example Walkthrough

Let's illustrate the solution approach using a small example. Suppose our input array nums is [3, 1, 5, 2, 4], and k is 3 (which means nums[k] is 2).

1. Auxiliary Arrays (left and right):

   • Initialize left to [-1, -1, -1, -1, -1]
   • Initialize right to [5, 5, 5, 5, 5]
   • Length of nums is 5.

2. Finding Nearest Smaller Elements on the Left:

   • stk is [].
   • We iterate over the indices and build left:
     • i = 0: Stack is empty, push 0.
     • i = 1: nums[1] is less than nums[0], pop 0 from stack, push 1.
     • i = 2: nums[2] is greater than nums[1], push 2.
     • i = 3: nums[3] is less than nums[2], pop 2, nums[3] is less than nums[1], pop 1, stk is now empty, push 3.
     • i = 4: nums[4] is greater than nums[3], push 4.
   • Now, left is [-1, -1, 1, -1, 3].

3. Finding Nearest Smaller Elements on the Right:

   • stk is cleared and is [] again.
   • We iterate in reverse and build right:
     • i = 4: Stack is empty, push 4.
     • i = 3: nums[3] is less than nums[4], push 3.
     • i = 2: nums[2] is greater than nums[3], pop 3, stack is empty, push 2.
     • i = 1: nums[1] is less than nums[2], push 1.
     • i = 0: nums[0] is greater than nums[1], pop 1, now stk is empty, push 0.
   • Now, right is [1, 2, 5, 5, 5].

4. Calculating the Maximum Score:

   • Initialize ans to 0.
   • Iterate over each index i of nums:
     • For i = 0: left[0] < k < right[0] doesn't hold, so skip.
     • For i = 1: left[1] < k < right[1] holds (-1 < 3 < 2), score is nums[1] * (right[1] - left[1] - 1) which is 1 * (2 - (-1) - 1) equal to 1.
     • For i = 2: left[2] < k < right[2] holds (1 < 3 < 5), score is nums[2] * (right[2] - left[2] - 1) which is 5 * (5 - 1 - 1) equal to 15. Update ans = 15.
     • For i = 3: left[3] < k < right[3] holds (-1 < 3 < 5), score is nums[3] * (right[3] - left[3] - 1) which is 2 * (5 - (-1) - 1) equal to 8. ans remains 15.
     • For i = 4: left[4] < k < right[4] doesn't hold, so skip.

5. Return the Maximum Score:

   • After iterating over all indices, we found the maximum score to be 15, so we return 15.

Using this approach, even with a small example, we're able to find the maximum score of a "good" subarray efficiently.

Solution Implementation

Time and Space Complexity

The given Python code finds the maximum score of a subarray within the given list nums where the score is defined as the minimum integer in the subarray times the length of the subarray. The range of indices for the subarray should include the index k. The code uses a stack to find the next smaller elements for each element in the list to determine the possible subarray ranges where the element is the smallest within those ranges.

Time Complexity:

The time complexity of the code is O(n).

Here's the breakdown:

• The first loop, where left boundaries for each element are calculated, iterates over the n elements. For each element, it performs a constant number of actions – checking and popping from the stack, and occasionally appending to the stack. While the popping might seem like it could lead to more than O(n) time, each element is added and removed from the stack at most once, which gives us O(n) for this loop.
• The second loop is similar to the first but in reverse to find right boundaries. Its complexity is also O(n) for the same reasons.
• The final loop again iterates over n elements and performs O(1) work for each by just checking indices and calculating the area if the conditions are met.

Summing these complexities gives us O(n) + O(n) + O(n) = O(n).

Space Complexity:

The space complexity of the code is O(n).

Here's the rationale:

• Two additional lists are created, left and right, each of size n, giving us 2n space usage.
• There is also a single stack used twice. However, the stack size will at most grow to n in the worst case (though not at the same time for both uses).
• Other than these, only a constant amount of additional space is used for variables such as i, v, and ans.

As such, the dominant term is O(n), making the overall space complexity O(n) as well.

Learn more about how to find time and space complexity quickly using problem constraints.