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 <= 1051 <= nums[i] <= 2 * 1040 <= k < nums.lengthThe key challenge in #1793 Maximum Score of a Good Subarray is maximizing the score defined as minimum element in subarray × length while ensuring the subarray includes a specific index k. A useful observation is that the minimum value of the subarray determines the score, so we want to expand the window in a way that keeps the minimum as large as possible.
A common approach uses a two‑pointer expansion from index k. Start with both pointers at k and gradually expand left or right. At each step, choose the direction that keeps the current minimum value as high as possible. Track the minimum value in the window and update the score using the current window length.
Another perspective relates to the classic largest rectangle in a histogram problem using a monotonic stack, where each element acts as the minimum for a valid range containing k. Both strategies aim to efficiently evaluate candidate ranges without checking every subarray.
The optimal implementations typically run in O(n) time with O(1) or O(n) auxiliary space depending on the technique.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers Expansion from k | O(n) | O(1) |
| Monotonic Stack (Histogram-style boundaries) | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Try thinking about the prefix before index k and the suffix after index k as two separate arrays.
Using two pointers or binary search, we can find the maximum prefix of each array where the numbers are less than or equal to a certain value
This approach involves expanding the subarray to the left and right of index k using two pointers. The objective is to maintain the minimum value in the subarray which can be computed incrementally. Extend the window until further expansion leads to a reduced score.
Time Complexity: O(n), because each element is processed at most twice, once by each pointer.
Space Complexity: O(1), as we are using only a constant amount of extra space.
1def maximumScore(nums, k):
2 n = len(nums)
3 left = right = k
4 min_val = nums[k]
5 max_score = 0
6
7 while left >= 0 or right < n:
8 while left >= 0 and (right == n or nums[left] >= nums[right]):
9 min_val = min(min_val, nums[left])
10 left -= 1
11 while right < n and (left < 0 or nums[right] > nums[left]):
12 min_val = min(min_val, nums[right])
13 right += 1
14 max_score = max(max_score, min_val * (right - left - 1))
15
16 return max_scoreThis Python solution uses two pointers to expand the subarray from the index k. It continuously calculates the score for each valid subarray, updating the maximum score found. The min_val is maintained as the window expands.
This approach involves using a monotonic stack to efficiently determine the range of the smallest element in which it acts as the minimum of a subarray. Thus, it can be used to calculate the potential maximum score by determining the largest possible width for each minimum value.
Time Complexity: O(n), for constructing boundaries with stacks and iterating through the arrays.
Space Complexity: O(n), due to usage of additional arrays and stack.
1import java.util.Stack;
2
3
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of problem appears in high-level technical interviews because it combines greedy thinking, two-pointer techniques, and monotonic stack concepts. It tests a candidate's ability to optimize subarray evaluation efficiently.
The optimal approach expands a window starting at index k using two pointers. By always expanding toward the side with the larger neighboring value, the minimum element of the window stays as large as possible, maximizing the score. This solution runs in O(n) time.
The score is defined as the minimum value in the subarray multiplied by its length. Because the minimum limits the entire product, strategies aim to keep this value as large as possible while expanding the window size.
A monotonic stack can be used to compute the nearest smaller elements on both sides, similar to the largest rectangle in a histogram problem. This helps determine the maximum range where each element acts as the minimum while still containing index k.
This Java implementation uses infix traversals and tracks potential boundaries of minimal elements. With left and right arrays, we define valid subarray bounds, ensuring it includes k and updating the max score accordingly.