Minimum Size Subarray Sum

🎯

Minimum Size Subarray Sum

mediumSLIDING_WINDOWAmazonGoogleFacebook

Imagine you are monitoring a stream of daily sales and want to find the shortest period where total sales meet a target quota.

💡 This problem asks for the smallest contiguous subarray whose sum is at least a target. Beginners often struggle because the window size varies dynamically, making fixed-size sliding window approaches insufficient. Understanding how to expand and shrink the window efficiently is key.

📋

Problem Statement

Given an array of positive integers nums and a positive integer target, find the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0.

1 ≤ nums.length ≤ 10^51 ≤ nums[i] ≤ 10^41 ≤ target ≤ 10^9

💡

Example

Input"target = 7, nums = [2,3,1,2,4,3]"

Output2

The subarray [4,3] has the minimal length under the problem constraint.

Input"target = 15, nums = [1,2,3,4,5]"

Output5

The entire array sums to 15, so minimal length is 5.

• target larger than sum of all elements → output 0
• array with one element equal to or greater than target → output 1
• all elements equal and sum just reaches target at the end → output length of subarray
• empty array (not allowed by constraints) but consider minimal input size → output 0

⚠️

Common Mistakes

Not shrinking the window properly

Leads to incorrect minimal length or TLE

✅ Use a while loop to shrink window while sum >= target

Returning min_length without checking if it was updated

Returns a large number instead of 0 when no valid subarray exists

✅ Return 0 if min_length remains infinity or max value

Using fixed-size sliding window instead of variable-size

Fails to find minimal length subarray correctly

✅ Use two pointers and adjust window size dynamically

Not handling single element arrays correctly

May return 0 incorrectly when single element meets target

✅ Ensure code checks single elements properly

Using prefix sums but not binary searching correctly

May cause incorrect indices or infinite loops

✅ Use built-in binary search or carefully implement lower bound

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem's nature by checking every possible subarray, though it's inefficient for large inputs.

Intuition

Try every possible subarray and check if its sum meets or exceeds the target, then track the minimal length found.

Algorithm

1. Initialize min_length to a large number.
2. Use two nested loops: outer loop picks start index, inner loop picks end index.
3. Calculate sum of elements between start and end.
4. If sum >= target, update min_length and break inner loop to try next start.

💡 The nested loops make it clear how subarrays are enumerated, but the repeated summations are costly.

</>

Code

def min_subarray_len(target, nums):
    n = len(nums)
    min_length = float('inf')
    for start in range(n):
        current_sum = 0
        for end in range(start, n):
            current_sum += nums[end]
            if current_sum >= target:
                min_length = min(min_length, end - start + 1)
                break
    return 0 if min_length == float('inf') else min_length

# Driver code
if __name__ == '__main__':
    print(min_subarray_len(7, [2,3,1,2,4,3]))  # Output: 2

Line Notes

n = len(nums)Get the total number of elements to control loops

min_length = float('inf')Initialize min_length to a very large number to find minimum

for start in range(n)Outer loop selects the start index of subarray

current_sum += nums[end]Accumulate sum for current subarray to check against target

if current_sum >= targetCheck if current subarray meets or exceeds target sum

min_length = min(min_length, end - start + 1)Update minimal length if current subarray is shorter

breakStop inner loop early since longer subarrays starting at same start won't be shorter

public class Solution {
    public static int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        for (int start = 0; start < n; start++) {
            int currentSum = 0;
            for (int end = start; end < n; end++) {
                currentSum += nums[end];
                if (currentSum >= target) {
                    minLength = Math.min(minLength, end - start + 1);
                    break;
                }
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        System.out.println(minSubArrayLen(7, new int[]{2,3,1,2,4,3})); // Output: 2
    }
}

Line Notes

int n = nums.length;Store array length for loop boundaries

int minLength = Integer.MAX_VALUE;Initialize minLength to max int for comparison

for (int start = 0; start < n; start++)Outer loop picks start index of subarray

currentSum += nums[end];Add current element to running sum

if (currentSum >= target)Check if current sum meets or exceeds target

minLength = Math.min(minLength, end - start + 1);Update minimal length if current subarray is shorter

break;Stop inner loop early to avoid unnecessary longer subarrays

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    int minLength = INT_MAX;
    for (int start = 0; start < n; start++) {
        int currentSum = 0;
        for (int end = start; end < n; end++) {
            currentSum += nums[end];
            if (currentSum >= target) {
                minLength = min(minLength, end - start + 1);
                break;
            }
        }
    }
    return minLength == INT_MAX ? 0 : minLength;
}

int main() {
    vector<int> nums = {2,3,1,2,4,3};
    cout << minSubArrayLen(7, nums) << endl; // Output: 2
    return 0;
}

Line Notes

int n = nums.size();Get the size of the input vector

int minLength = INT_MAX;Initialize minLength to max int for comparison

for (int start = 0; start < n; start++)Outer loop selects start index

currentSum += nums[end];Add current element to running sum

if (currentSum >= target)Check if current sum meets or exceeds target

minLength = min(minLength, end - start + 1);Update minimal length if current subarray is shorter

break;Stop inner loop early to avoid unnecessary longer subarrays

function minSubArrayLen(target, nums) {
    const n = nums.length;
    let minLength = Infinity;
    for (let start = 0; start < n; start++) {
        let currentSum = 0;
        for (let end = start; end < n; end++) {
            currentSum += nums[end];
            if (currentSum >= target) {
                minLength = Math.min(minLength, end - start + 1);
                break;
            }
        }
    }
    return minLength === Infinity ? 0 : minLength;
}

// Test
console.log(minSubArrayLen(7, [2,3,1,2,4,3])); // Output: 2

Line Notes

const n = nums.length;Store array length for loop limits

let minLength = Infinity;Initialize minLength to a very large number

for (let start = 0; start < n; start++)Outer loop picks start index

currentSum += nums[end];Add current element to running sum

if (currentSum >= target)Check if current sum meets or exceeds target

minLength = Math.min(minLength, end - start + 1);Update minimal length if current subarray is shorter

break;Stop inner loop early to avoid unnecessary longer subarrays

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, so O(n^2). No extra space besides variables.

💡 For n=1000, this means up to 1,000,000 operations, which is slow for large inputs.

Interview Verdict: TLE for large inputs, but useful to introduce problem

This approach is too slow for big arrays but helps understand the problem and correctness before optimizing.

🧠

Prefix Sum + Binary Search

💡 This approach improves over brute force by using prefix sums and binary search to find the minimal subarray efficiently.

Intuition

Compute prefix sums to quickly get subarray sums, then for each start index, binary search the smallest end index where sum >= target.

Algorithm

1. Compute prefix sums array where prefix[i] is sum of nums[0..i-1].
2. For each start index, calculate needed sum = target + prefix[start].
3. Use binary search on prefix sums to find minimal end index with prefix[end] >= needed sum.
4. Update minimal length if such end index found.

💡 Prefix sums let us get subarray sums in O(1), binary search finds the minimal end index efficiently.

</>

Code

import bisect

def min_subarray_len(target, nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    min_length = float('inf')
    for start in range(n):
        needed = target + prefix[start]
        end = bisect.bisect_left(prefix, needed)
        if end <= n:
            min_length = min(min_length, end - start)
    return 0 if min_length == float('inf') else min_length

# Driver code
if __name__ == '__main__':
    print(min_subarray_len(7, [2,3,1,2,4,3]))  # Output: 2

Line Notes

import bisectImport binary search module for efficient searching

prefix = [0] * (n + 1)Initialize prefix sums array with extra space for 0 prefix

prefix[i+1] = prefix[i] + nums[i]Build prefix sums cumulatively

needed = target + prefix[start]Calculate required prefix sum to reach target from start

end = bisect.bisect_left(prefix, needed)Binary search for minimal end index with sufficient sum

if end <= nCheck if valid end index found within array bounds

min_length = min(min_length, end - start)Update minimal length if better subarray found

import java.util.*;

public class Solution {
    public static int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int minLength = Integer.MAX_VALUE;
        for (int start = 0; start < n; start++) {
            int needed = target + prefix[start];
            int end = Arrays.binarySearch(prefix, needed);
            if (end < 0) {
                end = -end - 1;
            }
            if (end <= n) {
                minLength = Math.min(minLength, end - start);
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        System.out.println(minSubArrayLen(7, new int[]{2,3,1,2,4,3})); // Output: 2
    }
}

Line Notes

int[] prefix = new int[n + 1];Create prefix sums array with extra space

prefix[i + 1] = prefix[i] + nums[i];Build prefix sums cumulatively

int needed = target + prefix[start];Calculate required prefix sum for subarray

int end = Arrays.binarySearch(prefix, needed);Binary search for minimal end index

if (end < 0) { end = -end - 1; }Adjust insertion point if exact match not found

if (end <= n)Check if end index is valid

minLength = Math.min(minLength, end - start);Update minimal length if better subarray found

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    int minLength = INT_MAX;
    for (int start = 0; start < n; start++) {
        int needed = target + prefix[start];
        auto it = lower_bound(prefix.begin(), prefix.end(), needed);
        if (it != prefix.end()) {
            int end = it - prefix.begin();
            minLength = min(minLength, end - start);
        }
    }
    return minLength == INT_MAX ? 0 : minLength;
}

int main() {
    vector<int> nums = {2,3,1,2,4,3};
    cout << minSubArrayLen(7, nums) << endl; // Output: 2
    return 0;
}

Line Notes

vector<int> prefix(n + 1, 0);Initialize prefix sums vector with zeroes

prefix[i + 1] = prefix[i] + nums[i];Build prefix sums cumulatively

int needed = target + prefix[start];Calculate required prefix sum for subarray

auto it = lower_bound(prefix.begin(), prefix.end(), needed);Binary search for minimal end index

if (it != prefix.end())Check if valid end index found

int end = it - prefix.begin();Calculate index from iterator

minLength = min(minLength, end - start);Update minimal length if better subarray found

function minSubArrayLen(target, nums) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    let minLength = Infinity;
    function binarySearch(arr, x) {
        let left = 0, right = arr.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (arr[mid] >= x) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
    for (let start = 0; start < n; start++) {
        let needed = target + prefix[start];
        let end = binarySearch(prefix, needed);
        if (end <= n) {
            minLength = Math.min(minLength, end - start);
        }
    }
    return minLength === Infinity ? 0 : minLength;
}

// Test
console.log(minSubArrayLen(7, [2,3,1,2,4,3])); // Output: 2

Line Notes

const prefix = new Array(n + 1).fill(0);Initialize prefix sums array with zeroes

prefix[i + 1] = prefix[i] + nums[i];Build prefix sums cumulatively

function binarySearch(arr, x)Custom binary search to find minimal index with value >= x

let needed = target + prefix[start];Calculate required prefix sum for subarray

let end = binarySearch(prefix, needed);Find minimal end index using binary search

if (end <= n)Check if end index is valid

minLength = Math.min(minLength, end - start);Update minimal length if better subarray found

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Prefix sums take O(n), and for each start index we do a binary search O(log n), total O(n log n). Extra space for prefix sums.

💡 For n=1000, this means about 10,000 operations, much faster than brute force.

Interview Verdict: Accepted, but sliding window is more optimal

This approach is a good intermediate step but sliding window is preferred for linear time.

🧠

Sliding Window (Two Pointers)

💡 Sliding window is the optimal approach here because it dynamically adjusts the window size to find the minimal subarray efficiently in linear time.

Intuition

Expand the window by moving the right pointer and accumulate sum until it reaches or exceeds target, then shrink from the left to find smaller valid windows.

Algorithm

1. Initialize two pointers left and right at 0, and current_sum = 0.
2. Expand right pointer, adding nums[right] to current_sum.
3. While current_sum >= target, update min_length and move left pointer forward, subtracting nums[left] from current_sum.
4. Repeat until right reaches end of array.

💡 The key is to maintain a valid window and shrink it as much as possible to find minimal length.

</>

Code

def min_subarray_len(target, nums):
    n = len(nums)
    left = 0
    current_sum = 0
    min_length = float('inf')
    for right in range(n):
        current_sum += nums[right]
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1
    return 0 if min_length == float('inf') else min_length

# Driver code
if __name__ == '__main__':
    print(min_subarray_len(7, [2,3,1,2,4,3]))  # Output: 2

Line Notes

left = 0Initialize left pointer at start of array

current_sum = 0Initialize sum of current window

for right in range(n)Expand window by moving right pointer

current_sum += nums[right]Add new element to current sum

while current_sum >= targetShrink window from left while sum is sufficient

min_length = min(min_length, right - left + 1)Update minimal length with current window size

current_sum -= nums[left]Remove left element from sum as window shrinks

left += 1Move left pointer forward to shrink window

public class Solution {
    public static int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0, currentSum = 0, minLength = Integer.MAX_VALUE;
        for (int right = 0; right < n; right++) {
            currentSum += nums[right];
            while (currentSum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                currentSum -= nums[left];
                left++;
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        System.out.println(minSubArrayLen(7, new int[]{2,3,1,2,4,3})); // Output: 2
    }
}

Line Notes

int left = 0, currentSum = 0, minLength = Integer.MAX_VALUE;Initialize pointers and variables

for (int right = 0; right < n; right++)Expand window by moving right pointer

currentSum += nums[right];Add new element to current sum

while (currentSum >= target)Shrink window from left while sum is sufficient

minLength = Math.min(minLength, right - left + 1);Update minimal length with current window size

currentSum -= nums[left];Remove left element from sum as window shrinks

left++;Move left pointer forward to shrink window

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    int left = 0, currentSum = 0, minLength = INT_MAX;
    for (int right = 0; right < n; right++) {
        currentSum += nums[right];
        while (currentSum >= target) {
            minLength = min(minLength, right - left + 1);
            currentSum -= nums[left];
            left++;
        }
    }
    return minLength == INT_MAX ? 0 : minLength;
}

int main() {
    vector<int> nums = {2,3,1,2,4,3};
    cout << minSubArrayLen(7, nums) << endl; // Output: 2
    return 0;
}

Line Notes

int left = 0, currentSum = 0, minLength = INT_MAX;Initialize pointers and variables

for (int right = 0; right < n; right++)Expand window by moving right pointer

currentSum += nums[right];Add new element to current sum

while (currentSum >= target)Shrink window from left while sum is sufficient

minLength = min(minLength, right - left + 1);Update minimal length with current window size

currentSum -= nums[left];Remove left element from sum as window shrinks

left++;Move left pointer forward to shrink window

function minSubArrayLen(target, nums) {
    const n = nums.length;
    let left = 0, currentSum = 0, minLength = Infinity;
    for (let right = 0; right < n; right++) {
        currentSum += nums[right];
        while (currentSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            currentSum -= nums[left];
            left++;
        }
    }
    return minLength === Infinity ? 0 : minLength;
}

// Test
console.log(minSubArrayLen(7, [2,3,1,2,4,3])); // Output: 2

Line Notes

let left = 0, currentSum = 0, minLength = Infinity;Initialize pointers and variables

for (let right = 0; right < n; right++)Expand window by moving right pointer

currentSum += nums[right];Add new element to current sum

while (currentSum >= target)Shrink window from left while sum is sufficient

minLength = Math.min(minLength, right - left + 1);Update minimal length with current window size

currentSum -= nums[left];Remove left element from sum as window shrinks

left++;Move left pointer forward to shrink window

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most twice by left and right pointers, so linear time. Only constant extra space used.

💡 For n=100,000, this means about 200,000 operations, efficient for large inputs.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, implement sliding window for best balance of speed and simplicity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Prefix Sum + Binary Search	O(n log n)	O(n)	No	N/A	Good to mention as intermediate optimization
3. Sliding Window	O(n)	O(1)	No	N/A	Code this approach in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know what interviewers expect.

How to Present

Clarify problem constraints and input types.Explain brute force approach to show understanding.Discuss prefix sums + binary search as an improvement.Present sliding window as the optimal solution.Write clean code and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Ability to optimize from brute force to linear time, understanding of sliding window technique, and handling edge cases.

Common Follow-ups

• What if array contains negative numbers? → Sliding window may not work; prefix sums or other methods needed.
• Can you return the subarray itself? → Track indices when updating min_length.

💡 These follow-ups test deeper understanding and adaptability of your solution.

🔍

Pattern Recognition

When to Use

1) Asked for shortest/longest subarray or substring, 2) Condition involves sum or count, 3) Input array/string, 4) Need efficient O(n) or O(n log n) solution

Signature Phrases

minimal length of contiguous subarraysum is greater than or equal to target

NOT This Pattern When

Fixed-size window problems or problems requiring sorting or hashing without contiguous constraints

Similar Problems

3. Longest Substring Without Repeating Characters - sliding window to find longest substring76. Minimum Window Substring - sliding window to find minimal substring containing all chars

Practice

1. You manage a bookstore where customers arrive each minute, but the owner sometimes gets grumpy and ignores customers during certain minutes. You can choose a continuous time window of fixed length to calm the owner, making them satisfied during that window. Which algorithmic approach guarantees finding the maximum total satisfied customers?

easy

A. Sliding window to find the window maximizing extra satisfied customers plus base satisfaction

B. Dynamic programming over all subsets of minutes to maximize satisfaction

C. Greedy approach selecting the largest single minute with grumpy customers

D. Sorting customers by count and picking top X minutes regardless of continuity

Solution

1. Step 1: Understand problem constraints

   The problem requires selecting a continuous window of fixed length to maximize extra satisfaction, so continuity matters.

2. Step 2: Identify suitable algorithm

   Sliding window efficiently finds the maximum sum of grumpy customers in any continuous window, combined with base satisfaction from non-grumpy minutes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window handles continuous windows optimally [OK]

Hint: Continuous window optimization -> sliding window [OK]

Common Mistakes:

• Thinking greedy picking largest single minute suffices
• Ignoring continuity of window
• Trying DP over subsets unnecessarily

2. Consider the following code snippet implementing the optimal sliding window approach for longest substring with at most k distinct characters. What is the returned value when calling length_of_longest_substring_k_distinct('aabbcc', 2)?

easy

A. 6

B. 3

C. 2

D. 4

Solution

1. Step 1: Trace window expansion and last_seen updates

   For 'aabbcc' with k=2, the longest substring with at most 2 distinct chars is 'aabb' or 'bbcc', length 4.

2. Step 2: Confirm max_length calculation

   max_length updates to 4 when window covers 'aabb' or 'bbcc'. The function returns 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Longest valid substring length is 4 [OK]

Hint: Longest substring with 2 distinct chars in 'aabbcc' is length 4 [OK]

Common Mistakes:

• Off-by-one errors counting substring length
• Confusing distinct character count when shrinking window

3. You are given an array of positive integers and a positive integer k. The task is to count the number of contiguous subarrays where the product of all elements is less than k. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Use a sliding window with two pointers to dynamically adjust the window size while maintaining the product less than k.

B. Use a brute force nested loop to check all subarrays and count those with product less than k.

C. Use dynamic programming to store products of subarrays and count valid ones.

D. Use a greedy approach to pick elements until the product exceeds k, then restart.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting subarrays with product less than k efficiently.

2. Step 2: Identify optimal approach

   Sliding window with two pointers maintains a variable-size window and updates product in O(1) per step, achieving O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window adjusts window size dynamically -> O(n) time [OK]

Hint: Sliding window handles variable-size subarrays efficiently [OK]

Common Mistakes:

• Thinking brute force is optimal
• Confusing DP with product constraints

4. Suppose the problem is modified so that characters in p can be reused multiple times when matching substrings in s (i.e., find substrings in s that can be formed by repeating characters from p any number of times). Which of the following algorithmic changes correctly adapts the sliding window approach?

hard

A. Keep the fixed window size equal to len(p) and use the same frequency matching logic.

B. Sort p and each window substring, then compare sorted strings for equality.

C. Use a variable-size sliding window and check if the window's frequency counts are all less than or equal to p's counts multiplied by the number of repeats.

D. Use a variable-size sliding window and check if all characters in the window appear in p, ignoring counts.

Solution

1. Step 1: Understand reuse of characters

   Characters in p can be repeated multiple times, so window size is variable and frequency counts can exceed original counts.

2. Step 2: Adapt sliding window logic

   Use variable-size window and verify window counts do not exceed allowed multiples of p's counts.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Variable window and count comparison with multiples handles reuse correctly [OK]

Hint: Variable window size with count limits handles reuse [OK]

Common Mistakes:

• Keeping fixed window size
• Ignoring counts and only checking character presence
• Sorting substrings repeatedly

5. Suppose the sliding window maximum problem is modified so that elements can be reused multiple times (i.e., the window can slide but elements may appear multiple times in the output). Which of the following statements about the monotonic deque approach is true?

hard

A. The monotonic deque approach fails because it assumes each element appears only once; a max-heap is required instead.

B. The monotonic deque approach must be modified to track counts of elements to handle reuse correctly.

C. The monotonic deque approach works without any changes since it only depends on indices.

D. The problem reduces to a different pattern; monotonic deque is not applicable and a segment tree is needed.

Solution

1. Step 1: Understand the reuse modification

   Allowing elements to be reused means the same element can contribute multiple times as the window slides, potentially overlapping.

2. Step 2: Analyze monotonic deque assumptions

   The original deque stores indices assuming each element appears once per position. To handle reuse, counts or frequency tracking is needed to maintain correctness.

3. Step 3: Evaluate other options

   Monotonic deque without modification fails; max-heap alone is inefficient; segment tree is overkill for this variant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Tracking counts allows correct max maintenance with reuse [OK]

Hint: Reuse breaks unique index assumption; track counts to fix [OK]

Common Mistakes:

• Assuming no changes needed for reuse
• Switching to max-heap without efficiency gain
• Thinking monotonic deque is inapplicable