Sliding Window Maximum

🎯

Sliding Window Maximum

hardSTACKAmazonGoogleMicrosoft

Imagine monitoring the highest temperature in the last hour every minute to detect heat spikes instantly.

💡 This problem asks for the maximum value in every fixed-size sliding window over an array. Beginners often struggle because a naive approach is too slow, and the optimal solution requires understanding how to maintain useful information efficiently using a data structure like a deque.

📋

Problem Statement

Given an integer array nums and an integer k, return an array of the maximum values of each sliding window of size k moving from left to right across nums.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^41 ≤ k ≤ nums.length

💡

Example

Input"nums = [1,3,-1,-3,5,3,6,7], k = 3"

Output[3,3,5,5,6,7]

For each window of size 3, the maximums are: [1,3,-1] → 3, [3,-1,-3] → 3, [-1,-3,5] → 5, [-3,5,3] → 5, [5,3,6] → 6, [3,6,7] → 7

• k = 1 → output is the original array
• All elements are equal → output is array of that element repeated
• k equals array length → output is single max of entire array
• Array with negative and positive values → ensure max is correct

⚠️

Common Mistakes

Not removing indices outside the current window from the deque

Incorrect maximum values as outdated elements remain

✅ Always check and remove front of deque if it is out of the window

Removing elements from the deque incorrectly (e.g., removing from front instead of back)

Deque order breaks, leading to wrong max values

✅ Remove smaller elements from the back, not the front

Using a naive approach without optimization for large inputs

Time limit exceeded (TLE) in interviews

✅ Learn and implement the monotonic deque approach

Confusing indices and values when pushing/popping from data structures

Index errors or wrong max values

✅ Always store indices in deque/heap, not just values

Not handling edge cases like k=1 or k equals array length

Incorrect or incomplete output

✅ Add checks or ensure algorithm naturally handles these cases

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by directly implementing the definition, even though it is inefficient.

Intuition

For each window, scan all elements inside it to find the maximum.

Algorithm

1. Iterate over the array from index 0 to n-k.
2. For each position, scan the next k elements to find the maximum.
3. Store the maximum in the result array.
4. Return the result array after processing all windows.

💡 This approach is straightforward but inefficient because it repeats scanning overlapping parts of the array multiple times.

</>

Code

from typing import List

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    result = []
    for i in range(n - k + 1):
        window_max = nums[i]
        for j in range(i + 1, i + k):
            if nums[j] > window_max:
                window_max = nums[j]
        result.append(window_max)
    return result

# Example usage
if __name__ == '__main__':
    print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))

Line Notes

for i in range(n - k + 1):Iterate over all valid window start indices to cover every sliding window

window_max = nums[i]Initialize max for current window to the first element in the window

for j in range(i + 1, i + k):Scan all other elements in the current window to find the max

if nums[j] > window_max:Update max if a larger element is found in the window

result.append(window_max)Append the maximum found for this window to the result list

import java.util.*;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        for (int i = 0; i <= n - k; i++) {
            int windowMax = nums[i];
            for (int j = i + 1; j < i + k; j++) {
                if (nums[j] > windowMax) {
                    windowMax = nums[j];
                }
            }
            result[i] = windowMax;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] res = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(res));
    }
}

Line Notes

for (int i = 0; i <= n - k; i++) {Loop over all possible window start indices to cover every sliding window

int windowMax = nums[i];Initialize max for current window to the first element in the window

for (int j = i + 1; j < i + k; j++) {Check all elements in the current window to find the max

if (nums[j] > windowMax) {Update max if found larger element in the window

result[i] = windowMax;Store the maximum found for this window in the result array

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

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;
    for (int i = 0; i <= n - k; i++) {
        int windowMax = nums[i];
        for (int j = i + 1; j < i + k; j++) {
            if (nums[j] > windowMax) {
                windowMax = nums[j];
            }
        }
        result.push_back(windowMax);
    }
    return result;
}

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    for (int val : res) cout << val << ' ';
    cout << endl;
    return 0;
}

Line Notes

for (int i = 0; i <= n - k; i++) {Iterate over all window start positions to cover every sliding window

int windowMax = nums[i];Set initial max for the window to the first element

for (int j = i + 1; j < i + k; j++) {Scan all elements in the window to find the max

if (nums[j] > windowMax) {Update max if a bigger element is found

result.push_back(windowMax);Add the maximum found for this window to the result vector

function maxSlidingWindow(nums, k) {
    const n = nums.length;
    const result = [];
    for (let i = 0; i <= n - k; i++) {
        let windowMax = nums[i];
        for (let j = i + 1; j < i + k; j++) {
            if (nums[j] > windowMax) {
                windowMax = nums[j];
            }
        }
        result.push(windowMax);
    }
    return result;
}

// Example usage
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

Line Notes

for (let i = 0; i <= n - k; i++) {Loop over all valid window start indices to cover every sliding window

let windowMax = nums[i];Initialize max for current window to the first element

for (let j = i + 1; j < i + k; j++) {Check all elements in the current window to find the max

if (nums[j] > windowMax) {Update max if a larger element is found

result.push(windowMax);Append the maximum found for this window to the result array

⏱

Complexity

TimeO(n*k)

SpaceO(n-k+1)

For each of the n-k+1 windows, we scan k elements to find the max, resulting in O(n*k) time. The output array uses O(n-k+1) space.

💡 If n=100,000 and k=1000, this means 100 million operations, which is too slow for interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to demonstrate the problem and motivate better solutions.

🧠

Using Max Heap (Priority Queue)

💡 This approach improves over brute force by using a max heap to track the maximum in the current window, but still has overhead due to heap operations.

Intuition

Maintain a max heap of elements in the current window; the top is the maximum. Remove elements that slide out of the window.

Algorithm

1. Initialize a max heap and a result array.
2. Add the first k elements to the heap.
3. For each window starting from index k, add the new element and remove elements outside the window.
4. The top of the heap is the current window's maximum; add it to the result.
5. Return the result array.

💡 This approach uses a data structure to avoid scanning the entire window each time but requires careful removal of outdated elements.

</>

Code

from typing import List
import heapq

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    result = []
    # Python heapq is min-heap, so store negative values for max-heap behavior
    heap = []
    for i in range(k):
        heapq.heappush(heap, (-nums[i], i))
    result.append(-heap[0][0])
    for i in range(k, n):
        heapq.heappush(heap, (-nums[i], i))
        # Remove elements outside the current window
        while heap[0][1] <= i - k:
            heapq.heappop(heap)
        result.append(-heap[0][0])
    return result

# Example usage
if __name__ == '__main__':
    print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))

Line Notes

heap = []Initialize empty heap to store elements as (-value, index) for max heap simulation

for i in range(k):Add the first k elements to the heap to build initial window

heapq.heappush(heap, (-nums[i], i))Push negative value to simulate max heap and store index for window tracking

while heap[0][1] <= i - k:Remove elements outside the current window from the heap

result.append(-heap[0][0])Append current max (negated back) to result

import java.util.*;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a,b) -> b[0] - a[0]);
        for (int i = 0; i < k; i++) {
            maxHeap.offer(new int[]{nums[i], i});
        }
        result[0] = maxHeap.peek()[0];
        for (int i = k; i < n; i++) {
            maxHeap.offer(new int[]{nums[i], i});
            while (maxHeap.peek()[1] <= i - k) {
                maxHeap.poll();
            }
            result[i - k + 1] = maxHeap.peek()[0];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] res = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(res));
    }
}

Line Notes

PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a,b) -> b[0] - a[0]);Max heap based on element value to quickly get current max

for (int i = 0; i < k; i++) {Add first k elements to initialize the heap for the first window

maxHeap.offer(new int[]{nums[i], i});Add element and its index to heap for tracking

while (maxHeap.peek()[1] <= i - k) {Remove elements outside the sliding window from the heap

result[i - k + 1] = maxHeap.peek()[0];Current max is at heap top, add to result

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

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;
    priority_queue<pair<int,int>> maxHeap; // pair(value, index)
    for (int i = 0; i < k; i++) {
        maxHeap.push({nums[i], i});
    }
    result.push_back(maxHeap.top().first);
    for (int i = k; i < n; i++) {
        maxHeap.push({nums[i], i});
        while (maxHeap.top().second <= i - k) {
            maxHeap.pop();
        }
        result.push_back(maxHeap.top().first);
    }
    return result;
}

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    for (int val : res) cout << val << ' ';
    cout << endl;
    return 0;
}

Line Notes

priority_queue<pair<int,int>> maxHeap;Max heap stores pairs of (value, index) for quick max retrieval and window tracking

for (int i = 0; i < k; i++) {Push first k elements to initialize the heap for the first window

maxHeap.push({nums[i], i});Push current element with index into the heap

while (maxHeap.top().second <= i - k) {Pop elements outside the window to keep heap valid

result.push_back(maxHeap.top().first);Top of heap is current max, add to result

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    parent(i) { return Math.floor((i - 1) / 2); }
    left(i) { return 2 * i + 1; }
    right(i) { return 2 * i + 2; }
    swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }
    push(val) {
        this.heap.push(val);
        let i = this.heap.length - 1;
        while (i > 0 && this.heap[this.parent(i)][0] < this.heap[i][0]) {
            this.swap(i, this.parent(i));
            i = this.parent(i);
        }
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapify(0);
        return top;
    }
    heapify(i) {
        let largest = i;
        const l = this.left(i);
        const r = this.right(i);
        if (l < this.heap.length && this.heap[l][0] > this.heap[largest][0]) largest = l;
        if (r < this.heap.length && this.heap[r][0] > this.heap[largest][0]) largest = r;
        if (largest !== i) {
            this.swap(i, largest);
            this.heapify(largest);
        }
    }
    top() {
        return this.heap[0];
    }
}

function maxSlidingWindow(nums, k) {
    const n = nums.length;
    const maxHeap = new MaxHeap();
    const result = [];
    for (let i = 0; i < k; i++) {
        maxHeap.push([nums[i], i]);
    }
    result.push(maxHeap.top()[0]);
    for (let i = k; i < n; i++) {
        maxHeap.push([nums[i], i]);
        while (maxHeap.top()[1] <= i - k) {
            maxHeap.pop();
        }
        result.push(maxHeap.top()[0]);
    }
    return result;
}

// Example usage
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

Line Notes

class MaxHeap {Custom max heap implementation to support pairs of (value, index)

for (let i = 0; i < k; i++) {Insert first k elements to initialize the heap for the first window

maxHeap.push([nums[i], i]);Insert element with index into heap for tracking

while (maxHeap.top()[1] <= i - k) {Remove elements outside the window to keep heap valid

result.push(maxHeap.top()[0]);Add current max to result

⏱

Complexity

TimeO(n log k)

SpaceO(n)

Each insertion and removal from the heap costs O(log k), done n times, so total O(n log k). However, due to lazy removals, heap size can grow up to O(n), so space is O(n).

💡 For n=100,000 and k=1000, this is about 1.5 million operations, better than brute force but still not optimal.

Interview Verdict: Accepted but not optimal

This approach passes but is slower than the optimal deque method; it shows how data structures can improve brute force.

🧠

Optimal: Monotonic Deque

💡 This approach uses a deque to maintain indices of elements in decreasing order, allowing O(n) time by efficiently tracking the max in each window.

Intuition

Keep a deque that stores indices of elements in decreasing order of their values. The front is always the max. Remove indices that are out of the current window or smaller than the current element.

Algorithm

1. Initialize an empty deque and a result list.
2. Iterate over each element index i in nums.
3. Remove indices from the back of the deque while nums[i] is greater than nums at those indices.
4. Add current index i to the back of the deque.
5. Remove the front index if it is out of the current window (i - k).
6. If i >= k - 1, append nums at the front index of the deque to the result.
7. Return the result list.

💡 This algorithm cleverly maintains a data structure that always knows the max in O(1) time per step, avoiding repeated scanning.

</>

Code

from typing import List
from collections import deque

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    dq = deque()  # stores indices
    result = []
    for i in range(n):
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()  # remove smaller elements
        dq.append(i)
        if dq[0] == i - k:
            dq.popleft()  # remove out of window
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# Example usage
if __name__ == '__main__':
    print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))

Line Notes

dq = deque()Initialize deque to store indices of candidates for max in decreasing order

while dq and nums[dq[-1]] < nums[i]:Remove indices whose values are less than current element to maintain decreasing order

dq.append(i)Add current index as a candidate for max in future windows

if dq[0] == i - k:Remove front if it is out of the current window to keep window valid

result.append(nums[dq[0]])Append current max (front of deque) to result

import java.util.*;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> dq = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);
            if (dq.peekFirst() == i - k) {
                dq.pollFirst();
            }
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] res = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(res));
    }
}

Line Notes

Deque<Integer> dq = new LinkedList<>();Deque stores indices of elements in decreasing order for max tracking

while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {Remove smaller elements from the back to maintain decreasing order

dq.offerLast(i);Add current index as candidate for max in future windows

if (dq.peekFirst() == i - k) {Remove front if it is out of the window to keep window valid

result[i - k + 1] = nums[dq.peekFirst()];Current max is at front of deque, add to result

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

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    deque<int> dq; // stores indices
    vector<int> result;
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (dq.front() == i - k) {
            dq.pop_front();
        }
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    for (int val : res) cout << val << ' ';
    cout << endl;
    return 0;
}

Line Notes

deque<int> dq;Deque stores indices of elements in decreasing order for efficient max tracking

while (!dq.empty() && nums[dq.back()] < nums[i]) {Remove smaller elements from the back to maintain decreasing order

dq.push_back(i);Add current index as candidate for max in future windows

if (dq.front() == i - k) {Remove front if it is out of the window to keep window valid

result.push_back(nums[dq.front()]);Add current max (front of deque) to result

function maxSlidingWindow(nums, k) {
    const n = nums.length;
    const dq = [];
    const result = [];
    for (let i = 0; i < n; i++) {
        while (dq.length && nums[dq[dq.length - 1]] < nums[i]) {
            dq.pop();
        }
        dq.push(i);
        if (dq[0] === i - k) {
            dq.shift();
        }
        if (i >= k - 1) {
            result.push(nums[dq[0]]);
        }
    }
    return result;
}

// Example usage
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

Line Notes

const dq = [];Deque implemented as array storing indices for max tracking

while (dq.length && nums[dq[dq.length - 1]] < nums[i]) {Remove smaller elements from the back to maintain decreasing order

dq.push(i);Add current index as candidate for max in future windows

if (dq[0] === i - k) {Remove front if it is out of the window to keep window valid

result.push(nums[dq[0]]);Add current max (front of deque) to result

⏱

Complexity

TimeO(n)

SpaceO(k)

Each element is pushed and popped at most once from the deque, so total O(n) time. Space is O(k) for the deque storing indices of window elements.

💡 For n=100,000, this means about 200,000 operations, which is efficient for interviews.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews due to its linear time and minimal space usage.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the monotonic deque approach for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*k)	O(n-k+1)	No	N/A	Mention only - never code
2. Max Heap	O(n log k)	O(n)	No	N/A	Mention as improvement, but not optimal
3. Monotonic Deque	O(n)	O(k)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal solution, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding.Discuss the max heap approach as an improvement but note its overhead.Present the monotonic deque approach as the optimal solution.Code the monotonic deque solution carefully and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test & Optimize: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your ability to identify inefficiencies, knowledge of data structures like heaps and deques, and your skill in implementing the optimal O(n) solution.

Common Follow-ups

• What if k = 1? → Return the original array immediately.
• Can you solve it with O(n) time and O(k) space? → Use the monotonic deque approach.

💡 These follow-ups check if you handle edge cases and if you know the optimal data structure solution.

🔍

Pattern Recognition

When to Use

1) Asked for max/min in every fixed-size sliding window; 2) Need efficient O(n) or O(n log k) solution; 3) Problem involves contiguous subarrays; 4) Constraints too large for brute force.

Signature Phrases

sliding window maximumwindow size kmaximum in each subarray

NOT This Pattern When

Problems asking for maximum subarray sum or variable window sizes without fixed k are different patterns.

Similar Problems

239. Sliding Window Maximum - classic problem using monotonic deque862. Shortest Subarray with Sum at Least K - uses monotonic queue for sums

Practice

1. Consider the following Python function implementing the optimized monotonic stack approach for sum of subarray minimums. What is the final returned value when calling sumSubarrayMins([3,1,2,4])?

easy

A. 17

B. 15

C. 14

D. 10

Solution

1. Step 1: Trace stack operations for input [3,1,2,4]

   Push indices 0(3), then at i=1(1), pop 0 because 1<3, add 3*(1-(-1))*(1-0)=3*1*1=3; push 1. Continue similarly for indices 2 and 3.

2. Step 2: Calculate final result after processing sentinel

   After processing all elements and sentinel, sum is 17 modulo 10^9+7.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known correct output for this input [OK]

Hint: Sentinel ensures all elements processed; final sum is 17 [OK]

Common Mistakes:

• Off-by-one in counting subarrays
• Forgetting sentinel element

2. What is the time and space complexity of the optimal stack-less solution for evaluating a Basic Calculator II expression of length n?

medium

A. O(n) time and O(1) space because it processes the string once and uses only a few variables.

B. O(n^2) time and O(n) space due to repeated string slicing and stack usage.

C. O(n) time and O(n) space because it uses a stack to store intermediate results.

D. O(n log n) time due to sorting operators by precedence and O(1) space.

Solution

1. Step 1: Identify time complexity

   The algorithm scans the input string once, performing constant-time operations per character, so time is O(n).

2. Step 2: Identify space complexity

   Only a fixed number of variables are used (total, last_num, current_num, current_op), so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass and constant variables confirm O(n) time and O(1) space [OK]

Hint: Single pass with fixed vars means O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming stack usage means O(n) space
• Confusing recursion stack with iteration
• Thinking sorting operators is needed

3. Consider this buggy implementation of the pop method in the two-stack queue. What is the bug?

def pop(self) -> int:
    while self.push_stack:
        self.pop_stack.append(self.push_stack.pop())
    return self.pop_stack.pop()

medium

A. The push_stack should be cleared after transfer to avoid duplicates.

B. The pop_stack.pop() call should be replaced with pop_stack[-1] to peek instead of pop.

C. The transfer loop should only run if pop_stack is empty, otherwise elements are transferred every pop causing inefficiency.

D. The method should check if both stacks are empty before popping to avoid runtime errors.

Solution

1. Step 1: Identify transfer condition

   The code transfers elements from push_stack to pop_stack on every pop, regardless of pop_stack state.

2. Step 2: Understand impact

   This causes O(n) time on every pop, losing amortized O(1) efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Transfer only when pop_stack empty -> amortized O(1) [OK]

Hint: Transfer only if pop_stack empty to keep amortized O(1) [OK]

Common Mistakes:

• Transferring every pop causes O(n) pop time
• Not checking empty queue before pop

4. The following code attempts to find the longest valid parentheses substring using a stack-based approach. Identify the line containing the subtle bug that causes incorrect results for inputs starting with valid parentheses at index 0.

def longestValidParentheses(s: str) -> int:
    stack = []
    max_len = 0
    stack.append(-1)  # Initialize stack with -1
    for i, ch in enumerate(s):
        if ch == '(': 
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])
    return max_len

medium

A. Line 4: stack initialized with -1

B. Line 9: popping from stack without checking if empty

C. Line 3: stack initialized as empty list

D. Line 12: resetting stack with current index when empty

Solution

1. Step 1: Analyze stack pop operation

   Line 9 pops from stack without checking if stack is empty, which can cause runtime error or incorrect behavior if stack is empty.

2. Step 2: Understand initialization and reset logic

   Stack initialized with -1 (line 4) is correct to handle valid substrings starting at index 0; resetting stack with current index (line 12) is also correct.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pop without empty check leads to subtle bugs on edge cases [OK]

Hint: Popping stack without empty check causes subtle bugs [OK]

Common Mistakes:

• Forgetting to initialize stack with -1
• Not checking stack emptiness before pop
• Incorrect reset of stack after imbalance

5. Suppose the input array can contain negative numbers and duplicates, and you want to find the previous smaller element for each position. Which modification to the monotonic stack algorithm is necessary to handle duplicates correctly and maintain O(n) time?

hard

A. Change the popping condition to pop elements strictly greater than current (arr[stack[-1]] > num)

B. Store values instead of indexes in the stack to simplify comparisons

C. Use a balanced binary search tree instead of a stack to handle duplicates

D. Change the popping condition to pop elements greater than or equal to current (arr[stack[-1]] >= num)

Solution

1. Step 1: Understand the role of popping condition

   To correctly handle duplicates, the stack must pop elements that are greater than or equal to the current element to maintain strictly increasing order.

2. Step 2: Evaluate options for duplicates and negative numbers

   Using '>=' ensures duplicates are popped, preventing incorrect previous smaller elements; other options either break correctness or efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Pop equal or greater elements to maintain correct monotonic stack with duplicates [OK]

Hint: Pop >= current to handle duplicates correctly [OK]

Common Mistakes:

• Using '>' only causes duplicates to remain on stack
• Replacing stack with BST increases complexity unnecessarily
• Pushing values instead of indexes loses position info