Largest Rectangle in Histogram

🎯

Largest Rectangle in Histogram

hardMIXEDAmazonFacebookGoogle

Imagine you are given a skyline silhouette made of adjacent buildings, and you want to find the largest rectangular billboard you can place on it without overlapping the skyline edges.

💡 This problem asks for the largest rectangle area in a histogram, which is challenging because it requires understanding how to efficiently calculate areas spanning multiple bars. Beginners often struggle because a naive approach is too slow and the optimal solution uses a stack-based technique that is not immediately intuitive.

📋

Problem Statement

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

1 ≤ n ≤ 10^50 ≤ heights[i] ≤ 10^9

💡

Example

Input"[2,1,5,6,2,3]"

Output10

The largest rectangle has area 10 (bars with heights 5 and 6, width 2).

• All bars have the same height → output is height * n
• Only one bar → output is the height of that bar
• Bars with zero height → largest rectangle ignores zero height bars
• Strictly increasing or strictly decreasing heights → tests stack handling

⚠️

Common Mistakes

Not using a sentinel bar in the single pass stack approach

Some bars remain in stack and their areas are not calculated, leading to incorrect max area

✅ Add a sentinel bar of height 0 at the end to flush the stack

Using >= instead of > when popping from stack

Bars of equal height are popped prematurely, leading to incorrect width calculations

✅ Use strictly greater (>) comparison to maintain correct boundaries

Not resetting or clearing the stack between previous and next smaller computations

Stack contains stale indices causing wrong boundary calculations

✅ Clear the stack before computing next smaller elements

Calculating width incorrectly as next_smaller - prev_smaller instead of next_smaller - prev_smaller - 1

Width is overestimated, resulting in wrong area values

✅ Subtract 1 to exclude boundaries themselves from width

Not handling zero height bars properly

Zero height bars can cause infinite loops or incorrect expansions in brute force

✅ Ensure loops terminate correctly and zero height bars are considered boundaries

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by checking every possible rectangle, even though it is inefficient. It builds intuition about how rectangles form and why we need better methods.

Intuition

For each bar, expand left and right to find the maximum width where the height is at least that bar's height, then calculate the area. Repeat for all bars and track the maximum.

Algorithm

1. Initialize max_area to 0.
2. For each bar i in the histogram:
3. Expand left while bars are taller or equal to heights[i].
4. Expand right similarly.
5. Calculate area = height[i] * width and update max_area if larger.
6. Return max_area.

💡 This approach is straightforward but requires nested loops, making it slow for large inputs.

</>

Code

def largestRectangleArea(heights):
    max_area = 0
    n = len(heights)
    for i in range(n):
        height = heights[i]
        left = i
        while left > 0 and heights[left - 1] >= height:
            left -= 1
        right = i
        while right < n - 1 and heights[right + 1] >= height:
            right += 1
        width = right - left + 1
        area = height * width
        max_area = max(max_area, area)
    return max_area

# Example usage
if __name__ == '__main__':
    print(largestRectangleArea([2,1,5,6,2,3]))  # Output: 10

Line Notes

max_area = 0Initialize to track the largest rectangle found so far

for i in range(n):Iterate over each bar to consider it as the rectangle height

while left > 0 and heights[left - 1] >= height:Expand left boundary while bars are tall enough

while right < n - 1 and heights[right + 1] >= height:Expand right boundary similarly

area = height * widthCalculate area for the current rectangle

max_area = max(max_area, area)Update max_area if current area is larger

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        int n = heights.length;
        for (int i = 0; i < n; i++) {
            int height = heights[i];
            int left = i;
            while (left > 0 && heights[left - 1] >= height) {
                left--;
            }
            int right = i;
            while (right < n - 1 && heights[right + 1] >= height) {
                right++;
            }
            int width = right - left + 1;
            int area = height * width;
            maxArea = Math.max(maxArea, area);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.largestRectangleArea(new int[]{2,1,5,6,2,3})); // 10
    }
}

Line Notes

int maxArea = 0;Initialize max area to zero

for (int i = 0; i < n; i++) {Loop over each bar as candidate height

while (left > 0 && heights[left - 1] >= height) {Expand left boundary while possible

while (right < n - 1 && heights[right + 1] >= height) {Expand right boundary similarly

maxArea = Math.max(maxArea, area);Update max area if current area is larger

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

int largestRectangleArea(vector<int>& heights) {
    int max_area = 0;
    int n = heights.size();
    for (int i = 0; i < n; i++) {
        int height = heights[i];
        int left = i;
        while (left > 0 && heights[left - 1] >= height) {
            left--;
        }
        int right = i;
        while (right < n - 1 && heights[right + 1] >= height) {
            right++;
        }
        int width = right - left + 1;
        int area = height * width;
        max_area = max(max_area, area);
    }
    return max_area;
}

int main() {
    vector<int> hist = {2,1,5,6,2,3};
    cout << largestRectangleArea(hist) << endl; // 10
    return 0;
}

Line Notes

int max_area = 0;Initialize max area to zero

for (int i = 0; i < n; i++) {Iterate over each bar as candidate height

while (left > 0 && heights[left - 1] >= height) {Expand left boundary while bars are tall enough

while (right < n - 1 && heights[right + 1] >= height) {Expand right boundary similarly

max_area = max(max_area, area);Update max area if current area is larger

function largestRectangleArea(heights) {
    let maxArea = 0;
    const n = heights.length;
    for (let i = 0; i < n; i++) {
        const height = heights[i];
        let left = i;
        while (left > 0 && heights[left - 1] >= height) {
            left--;
        }
        let right = i;
        while (right < n - 1 && heights[right + 1] >= height) {
            right++;
        }
        const width = right - left + 1;
        const area = height * width;
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}

// Example usage
console.log(largestRectangleArea([2,1,5,6,2,3])); // 10

Line Notes

let maxArea = 0;Initialize max area to zero

for (let i = 0; i < n; i++) {Loop over each bar as candidate height

while (left > 0 && heights[left - 1] >= height) {Expand left boundary while possible

while (right < n - 1 && heights[right + 1] >= height) {Expand right boundary similarly

maxArea = Math.max(maxArea, area);Update max area if current area is larger

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each bar, we scan left and right which can take O(n) each, repeated for n bars leads to O(n^2).

💡 For n=20, this means up to 400 operations, which is okay, but for n=100000 it is 10 billion operations, too slow.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Using Stack to Find Next Smaller Elements

💡 This approach introduces a stack to efficiently find the nearest smaller bars on left and right for each bar, reducing the time complexity drastically.

Intuition

For each bar, find the index of the first smaller bar to the left and right. The width of the largest rectangle with this bar as height is between these two indices.

Algorithm

1. Use a stack to find the index of the previous smaller element for each bar.
2. Use a stack to find the index of the next smaller element for each bar.
3. Calculate the width for each bar as next_smaller_index - prev_smaller_index - 1.
4. Calculate area = height * width and track the maximum.

💡 This approach avoids nested loops by precomputing boundaries using stacks.

</>

Code

def largestRectangleArea(heights):
    n = len(heights)
    stack = []
    prev_smaller = [-1] * n
    next_smaller = [n] * n

    # Find previous smaller
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        prev_smaller[i] = stack[-1] if stack else -1
        stack.append(i)

    stack.clear()

    # Find next smaller
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        next_smaller[i] = stack[-1] if stack else n
        stack.append(i)

    max_area = 0
    for i in range(n):
        width = next_smaller[i] - prev_smaller[i] - 1
        area = heights[i] * width
        max_area = max(max_area, area)
    return max_area

# Example usage
if __name__ == '__main__':
    print(largestRectangleArea([2,1,5,6,2,3]))  # Output: 10

Line Notes

prev_smaller = [-1] * nInitialize previous smaller indices to -1 (none found)

while stack and heights[stack[-1]] >= heights[i]:Pop from stack until a smaller bar is found on the left

prev_smaller[i] = stack[-1] if stack else -1Set previous smaller index or -1 if none

stack.clear()Clear stack to reuse for next smaller element calculation

next_smaller[i] = stack[-1] if stack else nSet next smaller index or n if none

width = next_smaller[i] - prev_smaller[i] - 1Calculate width of rectangle for bar i

max_area = max(max_area, area)Update max area if current area is larger

import java.util.*;

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] prevSmaller = new int[n];
        int[] nextSmaller = new int[n];
        Arrays.fill(prevSmaller, -1);
        Arrays.fill(nextSmaller, n);
        Deque<Integer> stack = new ArrayDeque<>();

        // Previous smaller
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            prevSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        // Next smaller
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            nextSmaller[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            int width = nextSmaller[i] - prevSmaller[i] - 1;
            int area = heights[i] * width;
            maxArea = Math.max(maxArea, area);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.largestRectangleArea(new int[]{2,1,5,6,2,3})); // 10
    }
}

Line Notes

Arrays.fill(prevSmaller, -1);Initialize previous smaller indices to -1

while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {Pop from stack until smaller bar found on left

prevSmaller[i] = stack.isEmpty() ? -1 : stack.peek();Set previous smaller index or -1 if none

stack.clear();Clear stack to reuse for next smaller element calculation

nextSmaller[i] = stack.isEmpty() ? n : stack.peek();Set next smaller index or n if none

int width = nextSmaller[i] - prevSmaller[i] - 1;Calculate width of rectangle for bar i

maxArea = Math.max(maxArea, area);Update max area if current area is larger

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

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> prevSmaller(n, -1);
    vector<int> nextSmaller(n, n);
    stack<int> st;

    // Previous smaller
    for (int i = 0; i < n; i++) {
        while (!st.empty() && heights[st.top()] >= heights[i]) {
            st.pop();
        }
        prevSmaller[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }

    while (!st.empty()) st.pop();

    // Next smaller
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && heights[st.top()] >= heights[i]) {
            st.pop();
        }
        nextSmaller[i] = st.empty() ? n : st.top();
        st.push(i);
    }

    int maxArea = 0;
    for (int i = 0; i < n; i++) {
        int width = nextSmaller[i] - prevSmaller[i] - 1;
        int area = heights[i] * width;
        maxArea = max(maxArea, area);
    }
    return maxArea;
}

int main() {
    vector<int> hist = {2,1,5,6,2,3};
    cout << largestRectangleArea(hist) << endl; // 10
    return 0;
}

Line Notes

vector<int> prevSmaller(n, -1);Initialize previous smaller indices to -1

while (!st.empty() && heights[st.top()] >= heights[i]) {Pop from stack until smaller bar found on left

prevSmaller[i] = st.empty() ? -1 : st.top();Set previous smaller index or -1 if none

while (!st.empty()) st.pop();Clear stack to reuse for next smaller element calculation

nextSmaller[i] = st.empty() ? n : st.top();Set next smaller index or n if none

int width = nextSmaller[i] - prevSmaller[i] - 1;Calculate width of rectangle for bar i

maxArea = max(maxArea, area);Update max area if current area is larger

function largestRectangleArea(heights) {
    const n = heights.length;
    const prevSmaller = new Array(n).fill(-1);
    const nextSmaller = new Array(n).fill(n);
    const stack = [];

    // Previous smaller
    for (let i = 0; i < n; i++) {
        while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {
            stack.pop();
        }
        prevSmaller[i] = stack.length ? stack[stack.length - 1] : -1;
        stack.push(i);
    }

    stack.length = 0;

    // Next smaller
    for (let i = n - 1; i >= 0; i--) {
        while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {
            stack.pop();
        }
        nextSmaller[i] = stack.length ? stack[stack.length - 1] : n;
        stack.push(i);
    }

    let maxArea = 0;
    for (let i = 0; i < n; i++) {
        const width = nextSmaller[i] - prevSmaller[i] - 1;
        const area = heights[i] * width;
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}

// Example usage
console.log(largestRectangleArea([2,1,5,6,2,3])); // 10

Line Notes

const prevSmaller = new Array(n).fill(-1);Initialize previous smaller indices to -1

while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {Pop from stack until smaller bar found on left

prevSmaller[i] = stack.length ? stack[stack.length - 1] : -1;Set previous smaller index or -1 if none

stack.length = 0;Clear stack to reuse for next smaller element calculation

nextSmaller[i] = stack.length ? stack[stack.length - 1] : n;Set next smaller index or n if none

const width = nextSmaller[i] - prevSmaller[i] - 1;Calculate width of rectangle for bar i

maxArea = Math.max(maxArea, area);Update max area if current area is larger

⏱

Complexity

TimeO(n)

SpaceO(n)

Each element is pushed and popped at most once from the stack, so total operations are linear.

💡 For n=100000, this means roughly 200000 stack operations, which is efficient and feasible.

Interview Verdict: Accepted

This approach is efficient and accepted for large inputs, making it a strong candidate for interviews.

🧠

Single Pass Stack-Based Solution

💡 This approach further optimizes by computing the largest rectangle in a single pass using a stack, pushing bars in increasing order and calculating areas when a smaller bar is found.

Intuition

Maintain a stack of indices of bars in ascending height order. When a bar is lower than the top of the stack, pop from stack and calculate area with popped bar as smallest height, using current index as right boundary.

Algorithm

1. Initialize an empty stack and max_area = 0.
2. Iterate over bars with index i from 0 to n (inclusive, with a sentinel 0 height at end).
3. While stack not empty and current bar height < height at stack top, pop from stack and calculate area.
4. Push current index onto stack.
5. Return max_area.

💡 This approach cleverly uses a sentinel and stack to handle all bars in one pass without separate boundary arrays.

</>

Code

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel to flush stack at end
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    heights.pop()  # Restore original list
    return max_area

# Example usage
if __name__ == '__main__':
    print(largestRectangleArea([2,1,5,6,2,3]))  # Output: 10

Line Notes

heights.append(0)Add sentinel to ensure all bars are processed and stack is flushed

for i, h in enumerate(heights):Iterate over bars including sentinel to handle all cases

while stack and heights[stack[-1]] > h:Pop bars taller than current to calculate area

height = heights[stack.pop()]Height of bar to calculate area for

left = stack[-1] if stack else -1Left boundary index for width calculation

width = i - left - 1Width of rectangle with popped bar as height

max_area = max(max_area, height * width)Update max area if current area is larger

stack.append(i)Push current bar index onto stack to maintain ascending order

import java.util.*;

public class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;
        int n = heights.length;
        int[] extended = Arrays.copyOf(heights, n + 1);
        extended[n] = 0; // Sentinel

        for (int i = 0; i <= n; i++) {
            while (!stack.isEmpty() && extended[stack.peek()] > extended[i]) {
                int height = extended[stack.pop()];
                int left = stack.isEmpty() ? -1 : stack.peek();
                int width = i - left - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.largestRectangleArea(new int[]{2,1,5,6,2,3})); // 10
    }
}

Line Notes

int[] extended = Arrays.copyOf(heights, n + 1);Create extended array with sentinel to flush stack

extended[n] = 0;Sentinel bar of height 0 to process all bars

for (int i = 0; i <= n; i++) {Iterate over all bars including sentinel

while (!stack.isEmpty() && extended[stack.peek()] > extended[i]) {Pop taller bars to calculate area

int left = stack.isEmpty() ? -1 : stack.peek();Left boundary index for width calculation

int width = i - left - 1;Calculate width for popped bar

maxArea = Math.max(maxArea, height * width);Update max area if larger

stack.push(i);Push current index onto stack to maintain ascending order

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

int largestRectangleArea(vector<int>& heights) {
    stack<int> st;
    int maxArea = 0;
    heights.push_back(0); // Sentinel
    int n = heights.size();

    for (int i = 0; i < n; i++) {
        while (!st.empty() && heights[st.top()] > heights[i]) {
            int height = heights[st.top()];
            st.pop();
            int left = st.empty() ? -1 : st.top();
            int width = i - left - 1;
            maxArea = max(maxArea, height * width);
        }
        st.push(i);
    }
    heights.pop_back(); // Restore original vector
    return maxArea;
}

int main() {
    vector<int> hist = {2,1,5,6,2,3};
    cout << largestRectangleArea(hist) << endl; // 10
    return 0;
}

Line Notes

heights.push_back(0);Add sentinel bar to flush stack at end

for (int i = 0; i < n; i++) {Iterate over bars including sentinel

while (!st.empty() && heights[st.top()] > heights[i]) {Pop taller bars to calculate area

int left = st.empty() ? -1 : st.top();Left boundary index for width calculation

int width = i - left - 1;Calculate width for popped bar

maxArea = max(maxArea, height * width);Update max area if larger

st.push(i);Push current index onto stack to maintain ascending order

function largestRectangleArea(heights) {
    const stack = [];
    let maxArea = 0;
    heights.push(0); // Sentinel
    const n = heights.length;

    for (let i = 0; i < n; i++) {
        while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
            const height = heights[stack.pop()];
            const left = stack.length ? stack[stack.length - 1] : -1;
            const width = i - left - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    heights.pop(); // Restore original array
    return maxArea;
}

// Example usage
console.log(largestRectangleArea([2,1,5,6,2,3])); // 10

Line Notes

heights.push(0);Add sentinel bar to flush stack at end

for (let i = 0; i < n; i++) {Iterate over bars including sentinel

while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {Pop taller bars to calculate area

const left = stack.length ? stack[stack.length - 1] : -1;Left boundary index for width calculation

const width = i - left - 1;Calculate width for popped bar

maxArea = Math.max(maxArea, height * width);Update max area if larger

stack.push(i);Push current index onto stack to maintain ascending order

⏱

Complexity

TimeO(n)

SpaceO(n)

Each bar is pushed and popped at most once, so total operations are linear.

💡 This is the most efficient approach, suitable for very large inputs.

Interview Verdict: Accepted

This is the optimal solution commonly expected in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always start by explaining brute force, then code the single pass stack solution for best results.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Two Pass Stack (Prev/Next Smaller)	O(n)	O(n)	No	Yes	Good to explain optimization, but single pass preferred for coding
3. Single Pass Stack	O(n)	O(n)	No	Yes	Code this approach for optimal solution

💼

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.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the stack-based approach to find boundaries efficiently.Step 4: Present the single pass stack solution as the optimal method.Step 5: Code the optimal solution and test with examples.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from brute force, knowledge of stack usage, and clean coding skills.

Common Follow-ups

• How to handle very large heights without overflow → use long/int64 types
• Can you solve it without extra space? → No, stack is needed for O(n) time
• What if bars have varying widths? → Problem changes, requires different approach
• How to find the rectangle coordinates, not just area? → Track indices during calculation

💡 These follow-ups test your understanding of edge cases, data types, and problem variations.

🔍

Pattern Recognition

When to Use

1) Problem involves largest rectangle or area in histogram-like structure, 2) Input is array of heights, 3) Need to find max area rectangle, 4) Constraints require better than O(n^2) solution.

Signature Phrases

largest rectangle in histogramwidth of each bar is 1max area rectangle

NOT This Pattern When

Problems asking for maximum sum subarray or longest increasing subsequence are different patterns.

Similar Problems

Maximal Rectangle - extension to 2D matrix using histogram approachTrapping Rain Water - uses stack to find boundariesContainer With Most Water - similar area calculation with two pointers

Practice

1. Given the following Python code implementing the optimal stack-less calculator, what is the final returned value when the input string is "3+2*2"?

easy

A. 5

B. 10

C. 8

D. 7

Solution

1. Step 1: Trace first number and operator

   Read '3', current_op='+', total=0, last_num=0. On '+', total += last_num (0), last_num=3.

2. Step 2: Process '2*2'

   Read '2', operator '*', current_op='+', so total += last_num (3), last_num=2. Then read '2' after '*', current_op='*', last_num=2*2=4.

3. Step 3: End of string

   Add last_num (4) to total (3), total=7.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   3 + (2*2) = 7 matches traced total [OK]

Hint: Multiplication evaluated before addition, total accumulates last_num [OK]

Common Mistakes:

• Adding numbers before multiplication
• Off-by-one in loop end
• Not adding last_num at end

2. You are given an array of integers and need to find, for each element, the closest smaller element that appears before it in the array. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Monotonic stack maintaining indexes of elements in increasing order

B. Dynamic Programming with memoization to store previous results

C. Greedy approach scanning from left to right without extra data structures

D. Sorting the array and using binary search to find smaller elements

Solution

1. Step 1: Understand the problem requirement

   We need to find the closest smaller element to the left for each element efficiently.

2. Step 2: Identify the approach that supports O(n) time

   Monotonic stacks maintain a strictly increasing sequence of indexes, allowing popping of larger or equal elements and pushing current index, ensuring each element is pushed and popped at most once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is well-known for O(n) time in previous smaller element problems [OK]

Hint: Monotonic stacks solve closest smaller element in O(n) [OK]

Common Mistakes:

• Assuming greedy scanning without stack is enough
• Thinking sorting helps since order matters
• Confusing DP with this problem

3. Consider the following Python code implementing the Remove K Digits algorithm. What is the final returned value when calling removeKdigits("10200", 1)?

easy

A. "0"

B. "100"

C. "200"

D. "2000"

Solution

1. Step 1: Trace builder and k during iteration

   Digits: '1', '0', '2', '0', '0' - '1': builder = ['1'], k=1 - '0': '1' > '0', pop '1', k=0, builder = [] - Append '0': builder = ['0'] - '2': builder = ['0', '2'] - '0': '2' > '0', but k=0, no pop - Append '0': builder = ['0', '2', '0'] - '0': builder = ['0', '2', '0', '0']

2. Step 2: Remove leading zeros and finalize

   k=0, so no slice. Join builder: '0200'. Strip leading zeros: '200'. Return '200'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected minimal number after removing one digit [OK]

Hint: Pop digits while next digit is smaller and k>0 [OK]

Common Mistakes:

• Forgetting to strip leading zeros
• Removing wrong digits due to off-by-one in loop

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 you want to extend the circular queue to support a 'peekRear' operation that returns the last inserted element in O(1) time. Which modification to the optimal approach is correct?

hard

A. Return queue[tail] directly, since tail points to the last element inserted.

B. Return queue[(tail - 1 + capacity) % capacity], since tail points to the next insertion position.

C. Return queue[head], because head always points to the rear element.

D. Return queue[size - 1], since size tracks the number of elements.

Solution

1. Step 1: Understand tail pointer semantics

   Tail points to the next insertion index, not the last inserted element.

2. Step 2: Calculate rear element index

   The last inserted element is at (tail - 1 + capacity) modulo capacity to handle wrap-around.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Rear element index is tail - 1 modulo capacity [OK]

Hint: Rear element is at (tail - 1) mod capacity [OK]

Common Mistakes:

• Using tail index directly
• Confusing head with rear
• Using size as index