Skip to main content
Talentd

Maximum Score of a Good Subarray - Solution & Explanation

HardArrayTwo PointersBinary SearchStack11 min readAsked at: Google, Bloomberg
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 2 * 104
  • 0 <= k < nums.length

Approach Overview

Problem 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.

Approach 1: Sliding Window with Two Pointers

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Monotonic Stack

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.

Code

JavaJavaScriptPythonC++GoTypeScript

Java

JavaScript

Python

C++

Go

TypeScript

Complexity

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.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window with Two Pointers

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.

Monotonic Stack

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.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window with Two PointersO(n)O(1)Best choice when the subarray must include a fixed index. Simple greedy expansion and constant space.
Monotonic StackO(n)O(n)Useful when analyzing ranges where each element acts as the minimum. Good for problems similar to histogram or next smaller element.

Video Solution

Maximum Score of a Good Subarray - Leetcode 1793 - Python • NeetCodeIO • 13,387 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Score of a Good Subarray easy or hard?
The problem is classified as Hard on LeetCode. The difficulty comes from recognizing that the optimal subarray must include index k and designing a strategy that maximizes length while controlling the minimum value. Once the greedy expansion idea is understood, the implementation becomes straightforward.
How to solve Maximum Score of a Good Subarray in O(n)?
Initialize two pointers at index k and maintain the minimum value in the current window. Expand the window left or right depending on which side has the larger neighbor value. After every expansion, update the minimum and compute the score as minValue multiplied by the window length. Since each pointer moves at most n times, the algorithm runs in O(n).
What is the best approach for Maximum Score of a Good Subarray?
The most practical approach is expanding a sliding window from index k using two pointers. At each step, extend the side with the larger adjacent value so the minimum element decreases as slowly as possible. This greedy strategy scans the array once and runs in O(n) time with O(1) space.
Is Maximum Score of a Good Subarray asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Amazon and Google because it tests greedy reasoning, two pointers, and monotonic stack patterns. Candidates are expected to recognize the relationship between window expansion and maintaining a running minimum.
What data structure is used in Maximum Score of a Good Subarray?
Two common techniques are used. The greedy solution relies on two pointers and a running minimum while scanning the array. The alternative solution uses a monotonic stack to compute nearest smaller elements and determine the largest valid interval for each value.
What is the time complexity of Maximum Score of a Good Subarray?
The optimal solutions run in O(n) time. The two‑pointer method expands the window outward from k and visits each index at most once. The monotonic stack method also processes each element once while computing nearest smaller elements, resulting in linear time.
Maximum Score of a Good Subarray Python or Java solution available?
Implementations are typically written using a two‑pointer sliding window in Python or C++ because the logic is concise and uses constant space. A monotonic stack version is often shown in Java or JavaScript to demonstrate the next-smaller-element technique.

Ready to solve this problem?

Practice Maximum Score of a Good Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Largest Rectangle in Histogram