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.lengthProblem Overview: You are given an array nums and an index k. A subarray is considered good if it includes index k. The score of a subarray equals min(nums[i..j]) * (j - i + 1). The goal is to find the maximum score among all good subarrays.
Approach 1: Sliding Window with Two Pointers (O(n) time, O(1) space)
Start with both pointers at index k. The current subarray always includes k, so the score depends on the minimum value in the window and its length. Expand the window outward by choosing the side with the larger adjacent value (nums[left-1] vs nums[right+1]). This greedy choice delays reducing the minimum element as long as possible, which helps maximize the product. After each expansion, update the running minimum and compute minVal * windowLength. Continue until the window covers the entire array. This approach relies on careful pointer movement and constant-time comparisons, making it an efficient linear pass using the two pointers pattern on an array.
Approach 2: Monotonic Stack (O(n) time, O(n) space)
Another perspective treats each element as the potential minimum of a subarray. Using a monotonic stack, compute the nearest smaller element to the left and right for every index. This gives the maximum range where nums[i] remains the minimum. For each index i, the valid subarray range is (left[i] + 1, right[i] - 1). Only consider ranges that include index k. If the interval covers k, compute the score using nums[i] * (right[i] - left[i] - 1). The stack ensures each element is pushed and popped once, giving linear time complexity.
Recommended for interviews: The sliding window expansion from k is usually the expected solution. It demonstrates strong intuition about greedy pointer movement and window expansion. The monotonic stack approach is more general and mirrors the pattern used in problems like Largest Rectangle in Histogram, but it requires additional arrays and reasoning about boundaries. Showing the greedy two‑pointer idea first proves you understand the structure of the problem, while the stack solution shows deeper algorithmic flexibility.
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.
This 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.
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.
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.
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.
Java
JavaScript
Python
C++
Go
TypeScript
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.
| Approach | Complexity |
|---|---|
| Sliding Window with Two Pointers | Time Complexity: O(n), because each element is processed at most twice, once by each pointer. |
| Monotonic Stack | Time Complexity: O(n), for constructing boundaries with stacks and iterating through the arrays. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Two Pointers | O(n) | O(1) | Best choice when the subarray must include a fixed index. Simple greedy expansion and constant space. |
| Monotonic Stack | O(n) | O(n) | Useful when analyzing ranges where each element acts as the minimum. Good for problems similar to histogram or next smaller element. |
Maximum Score of a Good Subarray - Leetcode 1793 - Python • NeetCodeIO • 13,167 views views
Watch 9 more video solutions →Practice Maximum Score of a Good Subarray with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor