LeetCode 1793 - Maximum Score of a Good Subarray

LeetCode Problem 1793

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Binary Search, Stack, Monotonic Stack

Solution

Problem Understanding

In this problem, we are given an integer array nums and a specific index k. We must find a contiguous subarray that contains index k, and among all such subarrays, maximize the following score:

$$\text{score} = \min(\text{subarray}) \times \text{length of subarray}$$

The minimum element inside the chosen subarray determines the limiting value of the score, while the subarray length determines how many elements contribute to that score. The challenge comes from balancing these two factors. Expanding the subarray increases the length, but it may also decrease the minimum value.

A subarray is considered "good" only if it includes index k. This restriction is important because we are not searching across all possible subarrays. Every candidate interval must satisfy:

$$i \le k \le j$$

The input size can be as large as:

$$1 \le n \le 10^5$$

This immediately tells us that quadratic approaches will be too slow. Any algorithm worse than roughly $O(n \log n)$ risks timing out, and an $O(n)$ solution is ideal.

The values inside nums are all positive integers, which simplifies reasoning because increasing length always helps unless the minimum becomes too small.

Several edge cases are important:

• When the array has only one element, the answer is simply that element.
• When k is at the beginning or end of the array, expansion is possible in only one direction for some steps.
• When many values are equal, care must be taken to avoid incorrect boundary handling.
• Strictly increasing or strictly decreasing arrays can expose bugs in expansion logic.
• Very small minimum values can dominate large intervals, so blindly expanding is not always optimal.

Approaches

Brute Force Approach

The most direct solution is to examine every possible subarray that contains index k.

For every left boundary i such that 0 <= i <= k, and every right boundary j such that k <= j < n, we compute:

1. The minimum value in nums[i:j+1]
2. The length (j - i + 1)
3. The score

We then keep the maximum score found.

This approach is correct because it exhaustively checks every valid good subarray. However, it is far too slow for the constraints.

There are $O(n^2)$ possible subarrays containing k, and computing the minimum for each subarray naively costs another $O(n)$. Even with incremental optimization, the total runtime remains $O(n^2)$, which is unacceptable for $n = 10^5$.

Optimal Approach

The key observation is that the score is determined by the minimum value inside the chosen interval.

Suppose we fix a particular value as the minimum. Then we want the widest possible subarray containing k where every element is at least that minimum.

This leads naturally to a two-pointer greedy expansion strategy.

We begin with the smallest possible good subarray:

$$[left, right] = [k, k]$$

The current minimum is nums[k].

We then expand outward one step at a time. At every step, we choose the side with the larger adjacent value because doing so keeps the minimum as large as possible for as long as possible.

As the window expands:

• The width increases
• The minimum value may decrease
• We continuously compute candidate scores

Since every index is visited at most once during expansion, the entire algorithm runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every valid subarray containing k
Optimal	O(n)	O(1)	Greedy two-pointer expansion maintaining window minimum

Algorithm Walkthrough

Step 1: Initialize the Window

Start with:

• left = k
• right = k

The current subarray contains only the element at index k.

The current minimum is:

$$currentMin = nums[k]$$

The initial answer is also nums[k].

Step 2: Expand Until the Entire Array Is Covered

Continue while either side can still expand.

At each iteration, we decide whether to move left or right.

Step 3: Choose the Better Direction

If both sides are available:

• Compare nums[left - 1] and nums[right + 1]
• Expand toward the larger value

Why?

Because the score depends on the minimum value in the window. Choosing the larger adjacent element delays the decrease of the minimum.

If only one side is available, expand in that direction.

Step 4: Update the Current Minimum

After expansion:

$$currentMin = \min(currentMin, newlyAddedValue)$$

This maintains the minimum value of the current window efficiently.

Step 5: Compute the Score

The current window length is:

$$right - left + 1$$

The score becomes:

$$currentMin \times (right - left + 1)$$

Update the answer if this score is larger.

Step 6: Continue Expanding

Repeat until both pointers reach the array boundaries.

Why it works

The greedy choice works because the score depends heavily on the minimum value. Expanding toward the larger neighboring value preserves a larger minimum for a longer time. Every possible window size containing k is eventually considered, and for each size, the algorithm constructs the best possible minimum obtainable through outward expansion. Since the window only expands and never shrinks, all valid candidate intervals are explored efficiently.

Python Solution

from typing import List

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

        left = k
        right = k

        current_min = nums[k]
        best_score = nums[k]

        while left > 0 or right < n - 1:

            if left == 0:
                right += 1
            elif right == n - 1:
                left -= 1
            elif nums[left - 1] > nums[right + 1]:
                left -= 1
            else:
                right += 1

            current_min = min(current_min, nums[left], nums[right])

            window_length = right - left + 1
            best_score = max(best_score, current_min * window_length)

        return best_score

The implementation begins by creating the smallest valid subarray containing index k. Both pointers start at k, meaning the window initially contains exactly one element.

The variable current_min stores the minimum value inside the current window. Instead of recomputing the minimum every time, we update it incrementally whenever the window expands.

Inside the loop, the algorithm decides which direction to expand. If one side has already reached the boundary, expansion must happen on the other side. Otherwise, we compare neighboring values and move toward the larger one.

After expansion, the minimum value and window length are updated. The score for the current window is computed and compared with the best answer seen so far.

Since each pointer moves at most n times total, the runtime remains linear.

Go Solution

func maximumScore(nums []int, k int) int {
    n := len(nums)

    left := k
    right := k

    currentMin := nums[k]
    bestScore := nums[k]

    for left > 0 || right < n-1 {

        if left == 0 {
            right++
        } else if right == n-1 {
            left--
        } else if nums[left-1] > nums[right+1] {
            left--
        } else {
            right++
        }

        currentMin = min(currentMin, nums[left])
        currentMin = min(currentMin, nums[right])

        windowLength := right - left + 1
        bestScore = max(bestScore, currentMin*windowLength)
    }

    return bestScore
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go implementation follows the same logic as the Python version. Since Go does not provide built-in min and max functions for integers, helper functions are defined manually.

Slices in Go behave similarly to dynamic arrays, so pointer manipulation works naturally. Integer overflow is not a concern here because the maximum possible score is:

$$2 \times 10^4 \times 10^5 = 2 \times 10^9$$

which fits safely inside a 32-bit signed integer, and Go's int type is sufficient.

Worked Examples

Example 1

Input:

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

Initial state:

left	right	currentMin	score
3	3	7	7

Compare neighbors:

• left neighbor = 3
• right neighbor = 4

Expand right.

left	right	currentMin	length	score
3	4	4	2	8

Now compare:

• left neighbor = 3
• right neighbor = 5

Expand right again.

left	right	currentMin	length	score
3	5	4	3	12

Right boundary reached, expand left.

left	right	currentMin	length	score
2	5	3	4	12

Expand left again.

left	right	currentMin	length	score
1	5	3	5	15

Expand left again.

left	right	currentMin	length	score
0	5	1	6	6

Maximum score found is:

15

Example 2

Input:

nums = [5,5,4,5,4,1,1,1]
k = 0

Initial state:

left	right	currentMin	score
0	0	5	5

Since left boundary is fixed, keep expanding right.

left	right	currentMin	length	score
0	1	5	2	10
0	2	4	3	12
0	3	4	4	16
0	4	4	5	20
0	5	1	6	6
0	6	1	7	7
0	7	1	8	8

Maximum score:

20

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer moves at most n times
Space	O(1)	Only a few variables are maintained

The algorithm performs a single outward expansion process. Each iteration moves either the left pointer or the right pointer exactly once, so the total number of iterations is bounded by n. No auxiliary data structures proportional to input size are used.

Test Cases

from typing import List

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

        left = k
        right = k

        current_min = nums[k]
        best_score = nums[k]

        while left > 0 or right < n - 1:

            if left == 0:
                right += 1
            elif right == n - 1:
                left -= 1
            elif nums[left - 1] > nums[right + 1]:
                left -= 1
            else:
                right += 1

            current_min = min(current_min, nums[left], nums[right])

            best_score = max(
                best_score,
                current_min * (right - left + 1)
            )

        return best_score

sol = Solution()

assert sol.maximumScore([1,4,3,7,4,5], 3) == 15  # provided example 1
assert sol.maximumScore([5,5,4,5,4,1,1,1], 0) == 20  # provided example 2

assert sol.maximumScore([5], 0) == 5  # single element array

assert sol.maximumScore([1,2,3,4,5], 2) == 9  # increasing sequence
assert sol.maximumScore([5,4,3,2,1], 2) == 9  # decreasing sequence

assert sol.maximumScore([2,2,2,2], 1) == 8  # all equal values

assert sol.maximumScore([1,1,100,1,1], 2) == 100  # peak at k

assert sol.maximumScore([3,3,3,1,3], 3) == 5  # minimum at k

assert sol.maximumScore([10,9,8,7,6,5], 0) == 30  # k at left edge

assert sol.maximumScore([5,6,7,8,9,10], 5) == 30  # k at right edge

assert sol.maximumScore([4,3,2,6,5,1], 3) == 8  # mixed values

print("All tests passed!")

Test	Why
[1,4,3,7,4,5], k=3	Validates provided example
[5,5,4,5,4,1,1,1], k=0	Tests left boundary expansion
[5], k=0	Smallest possible input
Increasing array	Ensures greedy expansion behaves correctly
Decreasing array	Tests opposite ordering
All equal values	Verifies stable minimum handling
Large peak at k	Best answer may be single element
Minimum located at k	Window expansion still required
k at left edge	One-sided expansion
k at right edge	Opposite one-sided expansion
Mixed random values	General correctness stress case

Edge Cases

One important edge case occurs when the array contains only a single element. In this situation, the only possible subarray is the element itself, and the score equals that value. Implementations that assume expansion is always possible may accidentally access invalid indices. This solution handles the case naturally because the loop condition immediately fails.

Another tricky case happens when k lies at the beginning or end of the array. Since expansion is only possible in one direction, careless pointer logic can cause out-of-bounds errors. The implementation explicitly checks boundary conditions before comparing neighboring values, ensuring safe movement.

Arrays with many duplicate values can also introduce subtle bugs. If the algorithm incorrectly assumes strict inequality during expansion decisions, it may skip valid intervals or produce inconsistent behavior. This implementation handles equal neighboring values correctly by allowing expansion in either direction when values are equal.

A final important edge case occurs when the optimal answer is a very small interval, possibly just the single element at k. Expanding the window may drastically reduce the minimum value and destroy the score. The implementation correctly checks the score after every expansion while preserving the initial single-element score as a candidate.