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. Consider the following Python function implementing space-optimized bottom-up DP for edit distance. What is the value of current[1] after the first iteration of the inner loop when calling minDistance("abc", "ac") during the iteration where i = 2?

easy

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Identify iteration i=2 corresponds to last character 'c' in "abc"

   At i=2, word1[i] = 'c'. The inner loop runs j=1 to 0 for word2="ac".

2. Step 2: Compute current[1] when j=1 (word2[1] = 'c')

   Since word1[2] == word2[1] ('c' == 'c'), current[1] = next_row[2]. Initially, next_row = [2,1,0], so next_row[2] = 0.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matching chars yield current[j] = next_row[j+1] = 0 [OK]

Hint: Matching chars copy diagonal DP value [OK]

Common Mistakes:

• Off-by-one indexing in j or i
• Confusing current and next_row arrays

2. Consider the following Python code snippet implementing the optimal backtracking solution for Expression Add Operators. Given input num = "123" and target = 6, what is the final list of expressions returned by the function?

easy

A. ["1+2+3", "1*2*3"]

B. ["1+2+3", "1*2*3", "12-6"]

C. ["1+2+3", "1*2*3", "1+23"]

D. ["1+2+3", "1*2*3", "1-2+3"]

Solution

1. Step 1: Trace backtrack calls for num="123", target=6

   At index 0, path starts with "1". Then operators +, -, * are tried with "2" and "3". Valid expressions that evaluate to 6 are "1+2+3" and "1*2*3".

2. Step 2: Verify no other expressions equal 6

   Expressions like "12-6" or "1+23" do not evaluate to 6. "1-2+3" equals 2, so not included.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only "1+2+3" and "1*2*3" sum to 6 [OK]

Hint: Trace small input carefully to confirm valid expressions [OK]

Common Mistakes:

• Including invalid expressions with wrong evaluation
• Missing multiplication precedence

3. Consider the following Python code implementing the Trie-based palindrome pairs solution. Given the input words = ["bat", "tab", "cat"], what is the final output of palindromePairs(words)?

easy

A. [[0, 1], [1, 0], [2, 0]]

B. [[1, 0], [0, 1], [2, 2]]

C. [[0, 1]]

D. [[0, 1], [1, 0]]

Solution

1. Step 1: Add words to Trie in reversed order

   "bat" added reversed as "tab", "tab" as "bat", "cat" as "tac" with palindrome suffixes recorded.

2. Step 2: Search for palindrome pairs

   "bat" matches with "tab" forming "battab" palindrome, and "tab" matches with "bat" forming "tabbat" palindrome. "cat" has no palindrome pairs.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected palindrome pairs indices [OK]

Hint: Pairs are symmetric and exclude self-pairing [OK]

Common Mistakes:

• Including self-pairs like (2,2)
• Missing symmetric pairs
• Confusing order of pairs

4. Given the following code snippet implementing the two-pointer approach for trapping rain water, what is the value of the variable water after the first iteration of the while loop when the input is [2, 0, 2]?

easy

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Initialize variables

   left=0, right=2, left_max=0, right_max=0, water=0

2. Step 2: First iteration of while loop

   height[left]=2, height[right]=2, since height[left] is not less than height[right], else branch runs. height[right]=2 ≥ right_max=0, so right_max=2, right decrements to 1, water remains 0.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Water not added on first iteration because max updated [OK]

Hint: Water added only when current height < max height on that side [OK]

Common Mistakes:

• Adding water before max height is updated
• Confusing left and right pointer conditions
• Off-by-one errors in pointer movement

5. The following code attempts to implement the bidirectional BFS with state compression for the shortest path visiting all nodes problem. Identify the line containing the subtle bug that causes incorrect results or inefficiency.

medium

A. Line updating next_mask in backward BFS: next_mask = mask & ~(1 << nei)

B. Line initializing visited1 dictionary

C. Line updating next_mask in forward BFS: next_mask = mask

D. Line checking if (node, mask) in visited2

Solution

1. Step 1: Analyze forward BFS mask update

   The forward BFS must update the visited mask to include the neighbor node: next_mask = mask | (1 << nei). The code incorrectly assigns next_mask = mask, missing the neighbor.

2. Step 2: Consequences of bug

   Without updating the mask, states do not reflect actual visited nodes, causing incorrect results or infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct bitmask update is critical for state correctness [OK]

Hint: Forward BFS must update visited mask to include neighbor [OK]

Common Mistakes:

• Forgetting to update bitmask when moving to neighbor
• Confusing forward and backward mask updates
• Not checking visited states properly