Decode String

🎯

Decode String

mediumSTACKAmazonGoogleFacebook

Imagine receiving a compressed message where numbers indicate how many times a substring repeats, and you need to decode it to read the original message.

💡 This problem involves decoding a string with nested patterns, which can be confusing because beginners often struggle to track repeated substrings and their nesting levels without a clear method like a stack.

📋

Problem Statement

Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. Note that k is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

1 ≤ s.length ≤ 10^5s consists of lowercase English letters, digits, and square brackets '[]'.s is guaranteed to be a valid input.All the integers in s are in the range [1, 300].

💡

Example

Input"3[a]2[bc]"

Outputaaabcbc

3[a] means 'a' repeated 3 times, 2[bc] means 'bc' repeated twice.

Input"3[a2[c]]"

Outputaccaccacc

Inner 2[c] means 'cc', so 3[a2[c]] becomes 3[acc] = 'accaccacc'.

Input"2[abc]3[cd]ef"

Outputabcabccdcdcdef

2[abc] = 'abcabc', 3[cd] = 'cdcdcd', plus 'ef' at the end.

• Empty string → ''
• String without any brackets or digits → 'abc' returns 'abc'
• Nested multiple levels → '2[a2[b2[c]]]' returns 'abccbccabccbcc'
• Large repeat numbers → '100[a]' returns 'a' repeated 100 times

⚠️

Common Mistakes

Not handling multi-digit repeat counts correctly

Incorrect repeat counts leading to wrong output

✅ Accumulate digits into an integer before processing brackets

Forgetting to reset the repeat count after processing a bracket

Repeat counts carry over incorrectly to subsequent substrings

✅ Reset the count variable to zero after pushing it onto the stack

Using string concatenation inside loops without mutable structures

Time limit exceeded due to inefficient string operations

✅ Use StringBuilder, list, or array to build strings efficiently

Not handling nested brackets properly in recursion or stack

Incorrect decoding or runtime errors

✅ Ensure recursion or stack correctly tracks nested levels and returns at closing brackets

Off-by-one errors in index management during recursion

Infinite loops or skipping characters

✅ Carefully increment indices and return correct positions after recursion

🧠

Brute Force (Recursive Parsing)

💡 This approach helps understand the problem by directly parsing and expanding the string recursively, which is intuitive but inefficient for large inputs.

Intuition

Recursively parse the string: when you see a number, recursively decode the substring inside brackets and repeat it accordingly.

Algorithm

1. Define a recursive function that processes the string from a given index.
2. When a digit is encountered, parse the full number.
3. Recursively decode the substring inside the brackets following the number.
4. Repeat the decoded substring k times and append to the result.
5. Continue until the end of the string or closing bracket is reached.

💡 The recursion naturally handles nested brackets, but managing indices and returns can be tricky at first.

</>

Code

def decodeString(s: str) -> str:
    def helper(i):
        res = ''
        k = 0
        while i < len(s):
            if s[i].isdigit():
                k = k * 10 + int(s[i])
                i += 1
            elif s[i] == '[':
                i, decoded = helper(i + 1)
                res += decoded * k
                k = 0
            elif s[i] == ']':
                return i + 1, res
            else:
                res += s[i]
                i += 1
        return i, res
    return helper(0)[1]

Line Notes

def helper(i):Defines a recursive helper to decode from index i

if s[i].isdigit():Accumulate the repeat count k digit by digit

elif s[i] == '[':Start decoding the substring inside brackets recursively

elif s[i] == ']':Return the decoded substring and next index when closing bracket found

res += decoded * kRepeat the decoded substring k times and append to result

return helper(0)[1]Start decoding from index 0 and return the decoded string part

import java.util.*;
public class DecodeString {
    public String decodeString(String s) {
        int[] index = {0};
        return helper(s, index);
    }
    private String helper(String s, int[] index) {
        StringBuilder res = new StringBuilder();
        int k = 0;
        while (index[0] < s.length()) {
            char c = s.charAt(index[0]);
            if (Character.isDigit(c)) {
                k = k * 10 + (c - '0');
                index[0]++;
            } else if (c == '[') {
                index[0]++;
                String decoded = helper(s, index);
                for (int i = 0; i < k; i++) res.append(decoded);
                k = 0;
            } else if (c == ']') {
                index[0]++;
                return res.toString();
            } else {
                res.append(c);
                index[0]++;
            }
        }
        return res.toString();
    }
    public static void main(String[] args) {
        DecodeString ds = new DecodeString();
        System.out.println(ds.decodeString("3[a2[c]]")); // accaccacc
    }
}

Line Notes

int[] index = {0};Use array to pass index by reference in recursion

if (Character.isDigit(c)) {Parse repeat count k digit by digit

String decoded = helper(s, index);Recursively decode substring inside brackets

for (int i = 0; i < k; i++) res.append(decoded);Repeat decoded substring k times

if (c == ']') {Return when closing bracket is found

#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return helper(s, i);
    }
private:
    string helper(const string& s, int& i) {
        string res;
        int k = 0;
        while (i < s.size()) {
            if (isdigit(s[i])) {
                k = k * 10 + (s[i] - '0');
                i++;
            } else if (s[i] == '[') {
                i++;
                string decoded = helper(s, i);
                while (k--) res += decoded;
                k = 0;
            } else if (s[i] == ']') {
                i++;
                return res;
            } else {
                res += s[i++];
            }
        }
        return res;
    }
};
int main() {
    Solution sol;
    cout << sol.decodeString("3[a2[c]]") << endl; // accaccacc
    return 0;
}

Line Notes

int i = 0;Index passed by reference to track position in string

if (isdigit(s[i])) {Parse repeat count k digit by digit

string decoded = helper(s, i);Recursively decode substring inside brackets

while (k--) res += decoded;Repeat decoded substring k times

if (s[i] == ']') {Return when closing bracket is found

var decodeString = function(s) {
    let i = 0;
    function helper() {
        let res = '';
        let k = 0;
        while (i < s.length) {
            let c = s[i];
            if (!isNaN(c)) {
                k = k * 10 + Number(c);
                i++;
            } else if (c === '[') {
                i++;
                let decoded = helper();
                res += decoded.repeat(k);
                k = 0;
            } else if (c === ']') {
                i++;
                return res;
            } else {
                res += c;
                i++;
            }
        }
        return res;
    }
    return helper();
};
console.log(decodeString("3[a2[c]]")); // accaccacc

Line Notes

let i = 0;Global index to track position in string during recursion

if (!isNaN(c)) {Parse repeat count k digit by digit

let decoded = helper();Recursively decode substring inside brackets

res += decoded.repeat(k);Repeat decoded substring k times

if (c === ']') {Return when closing bracket is found

⏱

Complexity

TimeO(n * max_k) where max_k is the maximum repeat count

SpaceO(n) due to recursion stack and output string

Each character is processed once, but repeated substrings multiply output size; recursion depth depends on nesting.

💡 For n=20 and max_k=3, roughly 60 operations; but deep nesting or large repeats can cause exponential blowup.

Interview Verdict: TLE on large inputs

This approach is intuitive but inefficient for large inputs due to repeated string concatenations and recursion overhead.

🧠

Stack-Based Iterative Approach

💡 Using stacks to simulate recursion avoids overhead and clarifies the decoding process, making it more efficient and easier to debug.

Intuition

Use two stacks: one for counts and one for strings. When encountering '[', push current string and count; when ']', pop and build the repeated string.

Algorithm

1. Initialize two stacks: one for counts and one for strings.
2. Iterate over the string character by character.
3. If digit, build the current count.
4. If '[', push current string and count onto stacks and reset them.
5. If ']', pop count and previous string, append repeated current string.
6. If letter, append to current string.
7. At the end, the current string is the decoded result.

💡 Stacks help manage nested contexts explicitly, making the process iterative and easier to follow than recursion.

</>

Code

def decodeString(s: str) -> str:
    count_stack = []
    string_stack = []
    current_string = ''
    k = 0
    for char in s:
        if char.isdigit():
            k = k * 10 + int(char)
        elif char == '[':
            count_stack.append(k)
            string_stack.append(current_string)
            current_string = ''
            k = 0
        elif char == ']':
            prev_string = string_stack.pop()
            count = count_stack.pop()
            current_string = prev_string + current_string * count
        else:
            current_string += char
    return current_string

Line Notes

count_stack = []Stack to store repeat counts for nested levels

string_stack = []Stack to store strings built before '['

if char.isdigit():Build multi-digit repeat count

count_stack.append(k)Push current repeat count before entering new bracket

current_string = prev_string + current_string * countBuild repeated substring and append to previous string context

import java.util.*;
public class DecodeString {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<String> stringStack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int k = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                countStack.push(k);
                stringStack.push(currentString.toString());
                currentString = new StringBuilder();
                k = 0;
            } else if (c == ']') {
                int count = countStack.pop();
                StringBuilder temp = new StringBuilder(stringStack.pop());
                for (int i = 0; i < count; i++) temp.append(currentString);
                currentString = temp;
            } else {
                currentString.append(c);
            }
        }
        return currentString.toString();
    }
    public static void main(String[] args) {
        DecodeString ds = new DecodeString();
        System.out.println(ds.decodeString("3[a2[c]]")); // accaccacc
    }
}

Line Notes

Stack<Integer> countStack = new Stack<>();Stack to hold repeat counts for nested brackets

Stack<String> stringStack = new Stack<>();Stack to hold strings before entering brackets

k = k * 10 + (c - '0');Build multi-digit repeat count

countStack.push(k);Push repeat count before processing bracketed substring

for (int i = 0; i < count; i++) temp.append(currentString);Repeat decoded substring count times

#include <iostream>
#include <stack>
#include <string>
using namespace std;
class Solution {
public:
    string decodeString(string s) {
        stack<int> countStack;
        stack<string> stringStack;
        string currentString;
        int k = 0;
        for (char c : s) {
            if (isdigit(c)) {
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                countStack.push(k);
                stringStack.push(currentString);
                currentString = "";
                k = 0;
            } else if (c == ']') {
                int count = countStack.top(); countStack.pop();
                string prevString = stringStack.top(); stringStack.pop();
                string temp;
                for (int i = 0; i < count; i++) temp += currentString;
                currentString = prevString + temp;
            } else {
                currentString += c;
            }
        }
        return currentString;
    }
};
int main() {
    Solution sol;
    cout << sol.decodeString("3[a2[c]]") << endl; // accaccacc
    return 0;
}

Line Notes

stack<int> countStack;Stack to store repeat counts for nested substrings

stack<string> stringStack;Stack to store strings before '['

k = k * 10 + (c - '0');Build multi-digit repeat count

countStack.push(k);Push repeat count before processing bracketed substring

for (int i = 0; i < count; i++) temp += currentString;Repeat decoded substring count times

var decodeString = function(s) {
    let countStack = [];
    let stringStack = [];
    let currentString = '';
    let k = 0;
    for (let char of s) {
        if (!isNaN(char)) {
            k = k * 10 + Number(char);
        } else if (char === '[') {
            countStack.push(k);
            stringStack.push(currentString);
            currentString = '';
            k = 0;
        } else if (char === ']') {
            let count = countStack.pop();
            let prevString = stringStack.pop();
            currentString = prevString + currentString.repeat(count);
        } else {
            currentString += char;
        }
    }
    return currentString;
};
console.log(decodeString("3[a2[c]]")); // accaccacc

Line Notes

let countStack = [];Stack to hold repeat counts for nested brackets

let stringStack = [];Stack to hold strings before entering brackets

k = k * 10 + Number(char);Build multi-digit repeat count

countStack.push(k);Push repeat count before processing bracketed substring

currentString = prevString + currentString.repeat(count);Repeat decoded substring count times and append

⏱

Complexity

TimeO(n * max_k)

SpaceO(n)

Each character is processed once; repeated substrings increase output size proportionally to max_k.

💡 For n=20 and max_k=3, roughly 60 operations; this approach is efficient for typical inputs.

Interview Verdict: Accepted

This approach is efficient and practical, suitable for coding interviews and large inputs.

🧠

Optimized Stack with StringBuilder / Mutable String

💡 This approach improves performance by using mutable string structures to avoid costly string concatenations inside loops.

Intuition

Use stacks as before but use StringBuilder (Java), stringstream (C++), or arrays (JS) to build strings efficiently.

Algorithm

1. Use stacks to store counts and mutable string builders.
2. Iterate over the input string, building counts and strings.
3. Push current mutable string and count on encountering '['.
4. On ']', pop and append repeated string efficiently.
5. Return the final built string.

💡 Using mutable strings avoids repeated copying, which can be a bottleneck in large inputs.

</>

Code

def decodeString(s: str) -> str:
    count_stack = []
    string_stack = []
    current_string = []
    k = 0
    for char in s:
        if char.isdigit():
            k = k * 10 + int(char)
        elif char == '[':
            count_stack.append(k)
            string_stack.append(current_string)
            current_string = []
            k = 0
        elif char == ']':
            prev_string = string_stack.pop()
            count = count_stack.pop()
            current_string = prev_string + current_string * count
        else:
            current_string.append(char)
    return ''.join(current_string)

Line Notes

current_string = []Use list to build string efficiently

current_string.append(char)Append characters to list instead of string concatenation

current_string = prev_string + current_string * countRepeat and concatenate lists efficiently

return ''.join(current_string)Join list into final string at the end

import java.util.*;
public class DecodeString {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> stringStack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int k = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                countStack.push(k);
                stringStack.push(currentString);
                currentString = new StringBuilder();
                k = 0;
            } else if (c == ']') {
                int count = countStack.pop();
                StringBuilder prevString = stringStack.pop();
                for (int i = 0; i < count; i++) prevString.append(currentString);
                currentString = prevString;
            } else {
                currentString.append(c);
            }
        }
        return currentString.toString();
    }
    public static void main(String[] args) {
        DecodeString ds = new DecodeString();
        System.out.println(ds.decodeString("3[a2[c]]")); // accaccacc
    }
}

Line Notes

Stack<StringBuilder> stringStack = new Stack<>();Stack stores mutable string builders for efficient concatenation

StringBuilder currentString = new StringBuilder();Use StringBuilder to avoid costly string concatenation

stringStack.push(currentString);Push current mutable string builder before '['

prevString.append(currentString);Append repeated substring efficiently

return currentString.toString();Convert StringBuilder to string at the end

#include <iostream>
#include <stack>
#include <string>
using namespace std;
class Solution {
public:
    string decodeString(string s) {
        stack<int> countStack;
        stack<string> stringStack;
        string currentString;
        int k = 0;
        for (char c : s) {
            if (isdigit(c)) {
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                countStack.push(k);
                stringStack.push(currentString);
                currentString.clear();
                k = 0;
            } else if (c == ']') {
                int count = countStack.top(); countStack.pop();
                string prevString = stringStack.top(); stringStack.pop();
                string temp;
                temp.reserve(prevString.size() + currentString.size() * count);
                temp = prevString;
                for (int i = 0; i < count; i++) temp += currentString;
                currentString = move(temp);
            } else {
                currentString += c;
            }
        }
        return currentString;
    }
};
int main() {
    Solution sol;
    cout << sol.decodeString("3[a2[c]]") << endl; // accaccacc
    return 0;
}

Line Notes

currentString.clear();Clear string efficiently before building new substring

temp.reserve(...)Reserve memory to avoid reallocations during concatenation

temp = prevString;Start with previous string before appending repeated substring

for (int i = 0; i < count; i++) temp += currentString;Append repeated substring efficiently

currentString = move(temp);Move temporary string to currentString to avoid copying

var decodeString = function(s) {
    let countStack = [];
    let stringStack = [];
    let currentString = [];
    let k = 0;
    for (let char of s) {
        if (!isNaN(char)) {
            k = k * 10 + Number(char);
        } else if (char === '[') {
            countStack.push(k);
            stringStack.push(currentString);
            currentString = [];
            k = 0;
        } else if (char === ']') {
            let count = countStack.pop();
            let prevString = stringStack.pop();
            currentString = prevString.concat(Array(count).fill(currentString).flat());
        } else {
            currentString.push(char);
        }
    }
    return currentString.join('');
};
console.log(decodeString("3[a2[c]]")); // accaccacc

Line Notes

let currentString = [];Use array to build string efficiently

currentString.push(char);Append characters to array instead of string concatenation

stringStack.push(currentString);Push current array before '['

currentString = prevString.concat(Array(count).fill(currentString).flat());Repeat and concatenate arrays efficiently

return currentString.join('');Join array into final string at the end

⏱

Complexity

TimeO(n * max_k)

SpaceO(n)

Using mutable strings reduces overhead of repeated concatenations, improving runtime.

💡 For large inputs, this approach is faster and uses less memory than naive concatenation.

Interview Verdict: Accepted with improved performance

This is the preferred approach in interviews for languages where string concatenation is costly.

📊

All Approaches - One-Glance Tradeoffs

💡 The stack-based iterative approach with mutable strings is the best choice for most interviews due to its balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive Parsing)	O(n * max_k)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code due to inefficiency
2. Stack-Based Iterative Approach	O(n * max_k)	O(n)	No	Yes	Code this approach in interviews
3. Optimized Stack with Mutable Strings	O(n * max_k)	O(n)	No	Yes	Mention as optimization if language string concatenation is costly

💼

Interview Strategy

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

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force recursive approach to show understanding of nested decoding.Step 3: Explain the stack-based iterative approach to improve efficiency and avoid recursion.Step 4: Mention string builder optimizations for better performance in certain languages.Step 5: Code the stack-based iterative approach, test with examples, and discuss edge cases.

Time Allocation

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

What the Interviewer Tests

Ability to handle nested structures, use stacks effectively, optimize string operations, and write clean, bug-free code.

Common Follow-ups

• How would you handle invalid inputs or malformed strings? → Add validation and error handling.
• Can you optimize space usage? → Use a single stack or in-place decoding if possible.

💡 Follow-ups test robustness and deeper understanding of stack usage and string manipulation.

🔍

Pattern Recognition

When to Use

1) Input contains nested brackets or parentheses; 2) Repetitions indicated by numbers; 3) Need to decode or expand strings; 4) Stack or recursion naturally fits nested structure.

Signature Phrases

k[encoded_string]repeat substringnested brackets

NOT This Pattern When

Problems with flat string manipulation or simple substring search without nesting

Similar Problems

Evaluate Reverse Polish Notation - uses stack to evaluate nested expressionsBasic Calculator II - uses stack to handle operator precedence and nested expressions

Practice

1. What is the time complexity of the optimal Remove K Digits algorithm using a monotonic stack on an input string of length n?

medium

A. O(n * k), because each digit can be popped up to k times

B. O(n), because each digit is pushed and popped at most once

C. O(n log n), due to sorting or priority queue operations inside the stack

D. O(n^2), because nested loops remove digits repeatedly

Solution

1. Step 1: Analyze push and pop operations

   Each digit is pushed exactly once onto the stack. Each digit can be popped at most once when a smaller digit arrives.

2. Step 2: Conclude overall complexity

   Since each digit is pushed and popped at most once, total operations are O(n), linear in input size.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Monotonic stack ensures linear time by amortized analysis [OK]

Hint: Each digit pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming worst case k pops per digit -> O(n*k)
• Thinking sorting or nested loops are involved

2. The following code attempts to compute the sum of subarray minimums using a monotonic stack. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 11: count = (mid - left) * (i - mid)

B. Line 7: current = arr[i] if i < n else 0

C. Line 6: for i in range(n + 1):

D. Line 8: while stack and (i == n or current <= arr[stack[-1]]):

Solution

1. Step 1: Understand the condition in the while loop

   The condition uses <= instead of <, causing incorrect boundaries for next less element.

2. Step 2: Explain impact of using <=

   Using <= merges equal elements incorrectly, leading to wrong counts of subarrays and incorrect sum.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing <= to < fixes the bug and matches expected outputs [OK]

Hint: Use <, not <=, to find next less element correctly [OK]

Common Mistakes:

• Using >= or <= instead of strict inequalities
• Mixing previous less and next less boundaries

3. Suppose the asteroid collision problem is modified so that asteroids can split into smaller asteroids upon collision instead of simply exploding. Which of the following algorithmic changes correctly adapts the stack simulation to handle this variant efficiently?

hard

A. Modify the while loop to push the smaller split asteroid back onto the stack and continue collision checks with the remaining part

B. Replace the stack with a queue to process asteroids in order and handle splits by enqueuing new smaller asteroids

C. Use recursion to simulate all possible splits and collisions, returning the final stable configuration

D. Preprocess the input to split all asteroids into smallest units before running the original stack simulation

Solution

1. Step 1: Understand splitting behavior

   When an asteroid splits, the remaining part may still collide with others, requiring continued checks.

2. Step 2: Adapt stack simulation

   By pushing the smaller split asteroid back onto the stack and continuing the while loop, the algorithm correctly simulates ongoing collisions.

3. Step 3: Evaluate other options

   Queue breaks order assumptions; recursion risks TLE; preprocessing loses collision dynamics.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack with adjusted loop handles splits and collisions efficiently [OK]

Hint: Push remaining split asteroid back to stack for continued checks [OK]

Common Mistakes:

• Switching to queue breaks collision order
• Recursion causes inefficiency
• Preprocessing loses dynamic collisions

4. Suppose the problem changes so that for each element in nums1, you want to find the next greater element in nums2 but elements in nums2 can appear multiple times and you want the next greater element after the first occurrence of nums1's element. Which modification to the algorithm is necessary to handle this correctly?

hard

A. Precompute next greater elements for all indices in nums2, then for each nums1 element, find its first occurrence index and return the precomputed next greater at that index.

B. Use the same monotonic stack approach without changes, since it handles duplicates naturally.

C. Use a hashmap from element to next greater element ignoring positions, since duplicates don't affect the answer.

D. Sort nums2 and use binary search to find the next greater element after the first occurrence.

Solution

1. Step 1: Understand the impact of duplicates

   Duplicates mean the next greater element depends on the position of the specific occurrence, not just the element value.

2. Step 2: Modify approach to track next greater per index

   Precompute next greater elements for each index in nums2 using a monotonic stack, then for each nums1 element, find its first occurrence index and return the corresponding next greater element.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mapping element to next greater alone fails with duplicates; index-based precomputation is needed [OK]

Hint: Duplicates require next greater per index, not per element [OK]

Common Mistakes:

• Ignoring duplicates and mapping element to next greater element only
• Assuming monotonic stack handles duplicates without index tracking
• Using sorting which breaks original order constraints

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