1793. Maximum Score of a Good Subarray - Explanation

1. Brute Force

Intuition

A "good" subarray must contain index k. The score is the minimum element multiplied by the subarray length. The straightforward approach is to try all possible subarrays that include k, tracking the minimum as we extend each one. For each starting point at or before k, we extend rightward past k, updating the minimum and calculating the score at each step.

Algorithm

For each starting index i from 0 to k:
- Initialize minEle with nums[i].
- Extend the subarray rightward from i to n-1.
- Update minEle as we encounter each new element.
- Once j reaches k or beyond, calculate the score and update the result.
Return the maximum score found.

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0

        for i in range(k + 1):
            minEle = nums[i]
            for j in range(i, n):
                minEle = min(minEle, nums[j])
                if j >= k:
                    res = max(res, minEle * (j - i + 1))

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.

2. Binary Search

Intuition

For any subarray containing k, the minimum value decreases (or stays the same) as we expand outward from k. We can preprocess the array so that arr[i] represents the minimum value in the subarray from i to k (for left side) or from k to i (for right side). This creates sorted arrays on each side, allowing binary search to quickly find how far we can extend while maintaining at least a given minimum value.

Algorithm

Create a copy of the array and modify it:
- From k-1 down to 0, set arr[i] = min(arr[i], arr[i+1]).
- From k+1 to n-1, set arr[i] = min(arr[i], arr[i-1]).
For each unique minimum value in the modified array:
- Binary search the left array to find the leftmost index with value >= minVal.
- Binary search the right array to find the rightmost index with value >= minVal.
- Calculate the score and update the result.
Return the maximum score.

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0
        arr = nums[:]

        for i in range(k - 1, -1, -1):
            arr[i] = min(arr[i], arr[i + 1])
        for i in range(k + 1, n):
            arr[i] = min(arr[i], arr[i - 1])

        left_arr = arr[:k+1]
        right_arr = arr[k:]

        def find_right(target):
            lo, hi = 0, len(right_arr) - 1
            pos = 0
            while lo <= hi:
                mid = (lo + hi) // 2
                if right_arr[mid] >= target:
                    pos = mid
                    lo = mid + 1
                else:
                    hi = mid - 1
            return pos

        for minVal in set(arr):
            l = bisect_left(left_arr, minVal)
            r = find_right(minVal)
            res = max(res, minVal * (k - l + 1 + r))
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Binary Search (Overwriting the Input)

Intuition

This is a space-optimized version of the previous approach. Instead of creating a separate array, we modify the input array directly. The left portion becomes non-decreasing toward k, and the right portion becomes non-increasing from k. We can then binary search directly on the modified input array.

Algorithm

Modify the input array in place:
- From k-1 down to 0, set nums[i] = min(nums[i], nums[i+1]).
- From k+1 to n-1, set nums[i] = min(nums[i], nums[i-1]).
For each unique value in the modified array:
- Binary search to find the leftmost index (in range [0, k]) with value >= target.
- Binary search to find the rightmost index (in range [k, n-1]) with value >= target.
- Calculate and track the maximum score.
Return the result.

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0

        for i in range(k - 1, -1, -1):
            nums[i] = min(nums[i], nums[i + 1])
        for i in range(k + 1, n):
            nums[i] = min(nums[i], nums[i - 1])

        def find_left(target):
            lo, hi = 0, k
            while lo <= hi:
                mid = (lo + hi) // 2
                if nums[mid] < target:
                    lo = mid + 1
                else:
                    hi = mid - 1
            return lo

        def find_right(target):
            lo, hi = k, n - 1
            while lo <= hi:
                mid = (lo + hi) // 2
                if nums[mid] >= target:
                    lo = mid + 1
                else:
                    hi = mid - 1
            return hi

        for minVal in set(nums):
            i = find_left(minVal)
            j = find_right(minVal)
            res = max(res, minVal * (j - i + 1))
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Monotonic Stack

Intuition

This problem is related to finding the largest rectangle in a histogram. For each element, we want to know how far left and right it can extend as the minimum. A monotonic stack helps us find the "next smaller element" boundaries efficiently. When we pop an element from the stack, we know its valid range, and we only count it if that range includes index k.

Algorithm

Iterate from index 0 to n (using n as a sentinel to flush the stack).
Maintain a stack of indices in increasing order of values.
When we encounter a smaller element (or reach the end):
- Pop from the stack. The popped element's value is the minimum for some range.
- The range extends from the element below it in the stack (or -1) to the current index.
- If this range contains k, calculate the score.
Return the maximum score found.

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0
        stack = []

        for i in range(n + 1):
            while stack and (i == n or nums[stack[-1]] >= nums[i]):
                mini = nums[stack.pop()]
                j = stack[-1] if stack else -1
                if j < k < i:
                    res = max(res, mini * (i - j - 1))
            stack.append(i)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Greedy + Two Pointers

Intuition

Start with just the element at index k as our subarray. To expand, we have two choices: go left or go right. The key insight is that we should always expand toward the larger neighbor. This greedy choice maximizes the minimum value we can maintain for as long as possible, leading to higher scores. We continue until we have expanded to cover the entire array.

Algorithm

Initialize pointers l = r = k and track the current minimum starting with nums[k].
While we can still expand (l > 0 or r < n-1):
- Compare the left neighbor (if exists) with the right neighbor (if exists).
- Expand toward the larger one (or whichever exists).
- Update the current minimum with the newly included element.
- Calculate the score and update the result.
Return the maximum score.

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        l = r = k
        res = nums[k]
        cur_min = nums[k]

        while l > 0 or r < len(nums) - 1:
            left = nums[l - 1] if l > 0 else 0
            right = nums[r + 1] if r < len(nums) - 1 else 0

            if left > right:
                l -= 1
                cur_min = min(cur_min, left)
            else:
                r += 1
                cur_min = min(cur_min, right)

            res = max(res, cur_min * (r - l + 1))

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Forgetting the Subarray Must Include Index k

The problem requires the subarray to contain index k. A common mistake is computing the maximum score over all subarrays without enforcing this constraint. In the monotonic stack approach, you must check that the range [left, right] actually contains k before updating the result. Skipping this check leads to incorrect answers when the global maximum rectangle doesn't include k.

Off-by-One Errors in Boundary Calculations

When computing the left and right boundaries of a valid subarray, it's easy to be off by one. The valid range for an element at index i extends from prev_smaller + 1 to next_smaller - 1, not from prev_smaller to next_smaller. Miscalculating these boundaries causes incorrect subarray lengths and wrong scores.

Expanding in the Wrong Direction with Two Pointers

In the greedy two-pointer approach, you should always expand toward the larger neighbor to maintain the highest possible minimum for as long as possible. Expanding toward the smaller neighbor prematurely reduces the minimum value, potentially missing the optimal score. Always compare nums[l-1] with nums[r+1] and expand toward the larger one.

Not Handling Edge Cases at Array Boundaries

When the left pointer reaches 0 or the right pointer reaches n-1, you can only expand in one direction. Failing to handle these boundary conditions (e.g., accessing nums[-1] or nums[n]) causes index out of bounds errors. Use sentinel values or explicit boundary checks to handle these cases gracefully.

Misunderstanding the Score Formula

The score is min(subarray) * length(subarray), not min(subarray) * sum(subarray). Confusing this formula with similar problems leads to computing the wrong value entirely. Always verify you're multiplying the minimum element by the subarray length, not its sum.