#1793

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximum Score of a Good Subarray

Maximize the score of a good subarray using binary search to explore the valid answer space with a focus on two-pointer optimization.

array two pointers binary search stack monotonic stack

Problem Statement

You are given an array of integers nums and an integer k. The score of a subarray (i, j) is defined as min(nums[i], ..., nums[j]) * (j - i + 1). A good subarray is one where i <= k <= j.

Return the maximum possible score of a good subarray. The challenge requires balancing two-pointer strategies with binary search over the valid answer space to achieve an optimal solution.

Examples

Example 1

Input: nums = [1,4,3,7,4,5], k = 3

Output: 15

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

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

Solution Approach

Binary Search on Valid Answer Space

Binary search helps narrow down the potential scores for subarrays efficiently. By testing different subarray sizes and checking the corresponding score, we can hone in on the maximum score without brute-forcing every possibility.

Two-Pointer Technique

By splitting the problem into two distinct segments—prefix before k and suffix after k—you can apply the two-pointer technique to evaluate possible subarrays while considering index k as part of the valid range.

Monotonic Stack for Score Calculation

A monotonic stack can be used to track the minimum value of the subarray dynamically as the pointers move. This helps calculate the score efficiently while maintaining the correct bounds for the subarray.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) because the solution processes the array in a linear scan using binary search and two-pointer techniques. Space complexity is O(1) as it uses constant extra space, making it highly efficient for large arrays.

What Interviewers Usually Probe

The candidate demonstrates an understanding of binary search and two-pointer techniques.
The candidate is able to explain how to handle index k as a fixed element in subarrays.
The candidate can describe how to efficiently calculate subarray scores without unnecessary recalculations.

Common Pitfalls or Variants

Common pitfalls

Failing to consider the entire valid subarray range that includes index k.
Not efficiently handling the score calculation for varying subarray sizes.
Confusing the logic behind subarray boundaries, leading to incorrect minimum score calculations.

Follow-up variants

Handling larger arrays with more efficient search techniques.
Exploring different ways to optimize the calculation of the minimum in subarrays.
Incorporating additional constraints that may limit subarray size or range.

FAQ

What is the key pattern in Maximum Score of a Good Subarray?

The key pattern in this problem is binary search over the valid answer space, combined with two-pointer strategies to maximize subarray scores.

How do I approach finding the maximum score?

Use binary search to test different subarray sizes and apply the two-pointer technique to evaluate subarrays containing the element at index k.

What is the time complexity of the solution?

The time complexity is O(n), achieved through linear scanning with binary search and two-pointer techniques.

How can I avoid recalculating the subarray minimum?

Use a monotonic stack to dynamically track the minimum value of the subarray as the pointers move, avoiding redundant calculations.

What are the common mistakes when solving this problem?

Common mistakes include neglecting the valid subarray range containing index k or inefficient score calculations due to incorrect subarray boundaries.

terminal

Solution

Solution 1: Monotonic Stack

We can enumerate each element $nums[i]$ in $nums$ as the minimum value of the subarray, and use a monotonic stack to find the first position $left[i]$ on the left that is less than $nums[i]$ and the first position $right[i]$ on the right that is less than or equal to $nums[i]$. Then, the score of the subarray with $nums[i]$ as the minimum value is $nums[i] \times (right[i] - left[i] - 1)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class 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

Continue Practicing

#1574 shortest subarray to be removed to make array sorted #2454 next greater element iv #962 maximum width ramp