1793. Maximum Score of a Good Subarray

Problem¶

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 <= 10**5
1 <= nums[i] <= 2 * 10**4
0 <= k < nums.length

Solve¶

White board¶

Looking at the problem, I saw that:

A score of a sub-array is calculate by multiple the minimum number in that sub-array with the length of that sub-array.
We also need to have k’th element in the sub-array too.

We may need to find minimum value in any given range quickly, this could be done by using a min-max binary tree data structure.

Ideally, we want to try all possible length and range, but nums.length <= 10**5, which mean the submit need at least a time complexity of O(n log(n)) to be accepted.

Now let come up with a sample algorithm and start from there:

We always need k’th element. So we start with result sub-array res = [ nums[k] ] with score = 1 * nums[k]
We try to expanding res array. Normally, we only care about the expanding only when the minimum value to be change, which start with minElement = nums[k] (inherits from step 1 as we only have one element from start).
This lead to a loop of process:
- Expanding util we need to change the minimum value
- We store the current score, compare to current maximum value, and update if necessary
- Repeat until we can’t add new element into our started sub-array.

From the first glance, this look like a O(n) time complexity, which is way better than the minimum O(n log(n)) time complexity.

I start with draft code implementation right away

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        l, r = k, k # Start with a subarray nums[k:k] (inclusive, python is exlusive tho)
        # Init some defaul value
        minElement = nums[k]
        score = nums[k]
        # Loop until all possible nums is add to the subarray
        while (l >= 0 or r < len(nums)):
            # Expanding to the left until `l` is out of array scope, and not changing the minimum value
            while l >= 0:
                if nums[l] >= minElement:
                    l -= 1
                else:
                    break
            # Doing so with the right too
            while r < len(nums):
                if nums[r] >= minElement:
                    r += 1
                else:
                    break
            # Calulating current score and update the maximum score value
            currScore = minElement * (r - l + 1)
            if score < currScore:
                score = currScore

            # Handle the updating minElement expanding
            # Case 1: No more element to add
            if l == -1 and r == len(nums):
                break
            # Case 2: Left or Right can't expanding any more (l or r out of scope).
            if l == -1:
                r += 1
                minElement = nums[r]
                continue
            if r == len(nums):
                l -= 1
                minElement = nums[l]
                continue
            # Case 3: We piority the side where it have the bigger value.
            if nums[l] > nums[r]:
                l -= 1
                minElement = nums[l]
            else:
                r += 1
                minElement = nums[r]

        return score

I’m not adding any tracking yet, so let try with some value:

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.

Let trace the value of minElement and the current score, left right position of each one, expected value is here:

minElement = nums[3] = 7; left = 3; right = 3; currScore = 7
-> minElement = 4; left = 3; right = 6; currScore = 4*3
-> minElement = 3; left = 1; right = 6; currScore = 3*5
-> minElement = 1; left = -1; right = 6; currScore = 1*6

After quick look, it seem my implement need to be clear about inclusive and exclusive or the length value could be wrong. I need to add handle where left or right goes out of scope.

Which explain the formula currScore = minElement * (min(r, len(nums) -1) - max(0, l) + 1)

Update version

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        l, r = k, k # Start with a subarray nums[k:k] (inclusive, python is exlusive tho)
        # Init some defaul value
        minElement = nums[k]
        score = nums[k]
        # Loop until all possible nums is add to the subarray
        while (l >= 0 or r < len(nums)):
            # Expanding to the left until `l` is out of array scope, and not changing the minimum value
            while l >= 0:
                if nums[l] >= minElement:
                    l -= 1
                else:
                    break
            # Doing so with the right too
            while r < len(nums):
                if nums[r] >= minElement:
                    r += 1
                else:
                    break
            # Calulating current score and update the maximum score value
            currScore = minElement * (min(r, len(nums) -1) - max(0, l) + 1)
            # Debug line
            print(f"minElement = {minElement}; left = {l}; right = {r}; score = {currScore}")
            if score < currScore:
                score = currScore

            # Handle the updating minElement expanding
            # Case 1: No more element to add
            if l == -1 and r == len(nums):
                break
            # Case 2: Left or Right can't expanding any more (l or r out of scope).
            if l == -1:
                r += 1
                minElement = nums[r]
                continue
            if r == len(nums):
                l -= 1
                minElement = nums[l]
                continue
            # Case 3: We piority the side where it have the bigger value.
            if nums[l] > nums[r]:
                l -= 1
                minElement = nums[l]
            else:
                r += 1
                minElement = nums[r]

        return score

Output

minElement = 7; left = 2; right = 4; score = 21
minElement = 5; left = 2; right = 6; score = 20
minElement = 4; left = 0; right = 6; score = 24

This doen’t seem right at all tho?

minElement = nums[3] = 7; left = 3; right = 3; currScore = 7
-> minElement = 4; left = 3; right = 6; currScore = 4*3
-> minElement = 3; left = 1; right = 6; currScore = 3*5
-> minElement = 1; left = -1; right = 6; currScore = 1*6

I sawing that left and right equal to 2 and 4 right away, while minElement being the same at initial value (equal nums[k] = 7). After some looking, my expanding code is wrong, i need to compare nums[l-1] and nums[r+1] instead:

Wrong code:

            while l >= 0:
                if nums[l] >= minElement:
                    l -= 1
                else:
                    break
            # Doing so with the right too
            while r < len(nums):
                if nums[r] >= minElement:
                    r += 1
                else:
                    break

This lead to a lot more on how to handle range. So here is the new implementation:

The left and right can only expanding till 0 and len(nums) - 1 now instead of -1 and len(nums)
Making most of scope check now reduce by 1 on each side

We no longer need to handle currScore out of scope case

from typing import List


class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        # Start with a subarray nums[k:k] (inclusive, python is exlusive tho)
        l, r = k, k
        # Init some defaul value
        minElement = nums[k]
        score = nums[k]
        # Loop until all possible nums is add to the subarray
        while (l >= 0 or r < len(nums)):
            # Expanding to the left until `l` is out of array scope, and not changing the minimum value
            while l > 0:
                if nums[l-1] >= minElement:
                    l -= 1
                else:
                    break
            # Doing so with the right too
            while r < len(nums) - 1:
                if nums[r+1] >= minElement:
                    r += 1
                else:
                    break
            # Calulating current score and update the maximum score value
            currScore = minElement * (r - l + 1)
            # Debug line
            print(
                f"minElement = {minElement}; left = {l}; right = {r}; score = {currScore}")
            if score < currScore:
                score = currScore

            # Handle the updating minElement expanding
            # Case 1: No more element to add
            if l == 0 and r == len(nums) - 1:
                break
            # Case 2: Left or Right can't expanding any more (l or r out of scope).
            if l == 0:
                r += 1
                minElement = nums[r]
                continue
            if r == len(nums) - 1:
                l -= 1
                minElement = nums[l]
                continue
            # Case 3: We piority the side where it have the bigger value.
            if nums[l] > nums[r]:
                l -= 1
                minElement = nums[l]
            else:
                r += 1
                minElement = nums[r]

        return score


a = Solution()
nums = [1, 4, 3, 7, 4, 5]
k = 3
a.maximumScore(nums=nums, k=k)

Output:

minElement = 7; left = 3; right = 3; score = 7
minElement = 4; left = 3; right = 5; score = 12
minElement = 3; left = 1; right = 5; score = 15
minElement = 1; left = 0; right = 5; score = 6

Needed value, seem about right:

We no longer have out of scope value so r = 6 reduce to r = 5 and l = -1 now up to l = 0

minElement = nums[3] = 7; left = 3; right = 3; currScore = 7
-> minElement = 4; left = 3; right = 5 (6); currScore = 4*3
-> minElement = 3; left = 1; right = 5 (6); currScore = 3*5
-> minElement = 1; left = 0 (-1); right = 5 (6); currScore = 1*6

There is pretty much no special case so we can use our draft to summit now.

Well, wrong answer, i over look and forgot to update the Case 3:

    # Case 3: We piority the side where it have the bigger value.
    if nums[l] > nums[r]:
        l -= 1
        minElement = nums[l]
    else:
        r += 1
        minElement = nums[r]

Which need to be l-1 and r+1 here. Update that and we got:

Implementation: Sliding window¶

c
O(n)
O(1)

Just re implement my python draft code into another language. Anything language can be possible be use here:

int maximumScore(int* nums, int numsSize, int k){
    int l = k;
    int r = k;
    int minElement = nums[k];
    int score = nums[k];
    int currScore = -1;
    while (l >= 0 && r < numsSize) {
        while (l > 0) {
            if (nums[l-1] >= minElement) {
                l --;
            } else {
                break;
            }
        }
        while (r < numsSize-1) {
            if (nums[r+1] >= minElement) {
                r ++;
            } else {
                break;
            }
        }

        currScore = minElement * (r - l + 1);
        if (score < currScore) {
            score = currScore;
        }

        if (l == 0 && r == numsSize -1) {
            break;
        }
        if (l == 0) {
            r ++;
            minElement = nums[r];
            continue;
        }
        if (r == numsSize - 1) {
            l --;
            minElement = nums[l];
            continue;
        }
        if (nums[l-1] > nums[r+1]) {
            l --;
            minElement = nums[l];
        } else {
            r ++;
            minElement = nums[r];
        }
    }

    return score;
}

Here is go lang, which quite identical to c

go

name="__codelineno-11-1">func maximumScore(nums []int, k int) int { l := k r := k minElement := nums[k] score := nums[k] currScore := -1 for l >= 0 && r < len(nums) { for l > 0 { if nums[l-1] >= minElement { l -- } else { break; } } for r < len(nums)-1 { if nums[r+1] >= minElement { r ++ } else { break } } currScore = minElement * (r - l + 1) if score < currScore { score = currScore } if l == 0 && r == len(nums) -1 { break } if l == 0 { r ++ minElement = nums[r] continue } if r == len(nums) - 1 { l -- minElement = nums[l] continue } if nums[l-1] > nums[r+1] { l -- minElement = nums[l] } else { r ++ minElement = nums[r] } } return score }

Last update : October 26, 2023
Created : October 26, 2023