Largest Rectangle in Histogram Using Stack in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Largest Rectangle Calculation

What is the output of the following Go code that calculates the largest rectangle area in a histogram using a stack?

DSA Go

package main

import "fmt"

func largestRectangleArea(heights []int) int {
    stack := []int{}
    maxArea := 0
    heights = append(heights, 0) // Append zero to flush stack at end

    for i, h := range heights {
        for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }
            area := height * width
            if area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }
    return maxArea
}

func main() {
    histogram := []int{2, 1, 5, 6, 2, 3}
    fmt.Println(largestRectangleArea(histogram))
}

A 12

B 10

C 8

D 6

💡 Hint

Think about the largest rectangle that can be formed by consecutive bars.

The largest rectangle area in the histogram [2,1,5,6,2,3] is 10, formed by bars with heights 5 and 6 (width 2).

❓ Predict Output

intermediate

Output of Largest Rectangle for Uniform Heights

What is the output of the following Go code for a histogram with uniform heights?

DSA Go

package main

import "fmt"

func largestRectangleArea(heights []int) int {
    stack := []int{}
    maxArea := 0
    heights = append(heights, 0)

    for i, h := range heights {
        for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }
            area := height * width
            if area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }
    return maxArea
}

func main() {
    histogram := []int{4, 4, 4, 4}
    fmt.Println(largestRectangleArea(histogram))
}

A 16

B 12

C 8

D 4

💡 Hint

All bars have the same height, so the largest rectangle covers all bars.

With all bars height 4 and count 4, the largest rectangle area is 4 * 4 = 16.

❓ Predict Output

advanced

Output for Decreasing Heights Histogram

What is the output of this Go code for a histogram with strictly decreasing heights?

DSA Go

package main

import "fmt"

func largestRectangleArea(heights []int) int {
    stack := []int{}
    maxArea := 0
    heights = append(heights, 0)

    for i, h := range heights {
        for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }
            area := height * width
            if area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }
    return maxArea
}

func main() {
    histogram := []int{6, 5, 4, 3, 2, 1}
    fmt.Println(largestRectangleArea(histogram))
}

A 6

B 15

C 12

D 9

💡 Hint

Consider the largest rectangle formed by the first few bars.

The largest rectangle area is 12, formed by the first three bars with heights 6, 5, and 4 (minimum height 4, width 3).

🧠 Conceptual

advanced

Stack Usage in Largest Rectangle Algorithm

Why does the largest rectangle in histogram algorithm use a stack to store indices of bars?

A To keep track of bars in increasing height order for area calculation

B To store the heights of bars directly for quick access

C To reverse the histogram order for easier processing

D To count the total number of bars processed

💡 Hint

Think about how the algorithm finds when to calculate areas.

The stack stores indices of bars in increasing height order. When a smaller bar is found, it calculates areas for bars taller than the current one.

❓ Predict Output

expert

Output for Complex Histogram with Multiple Peaks

What is the output of the following Go code for a histogram with multiple peaks and valleys?

DSA Go

package main

import "fmt"

func largestRectangleArea(heights []int) int {
    stack := []int{}
    maxArea := 0
    heights = append(heights, 0)

    for i, h := range heights {
        for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }
            area := height * width
            if area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }
    return maxArea
}

func main() {
    histogram := []int{2, 4, 2, 1, 10, 6, 10}
    fmt.Println(largestRectangleArea(histogram))
}

A 14

B 20

C 16

D 18

💡 Hint

Look for the largest rectangle that spans multiple bars including the peak 10.

The largest rectangle area is 18, formed by bars at indices 4, 5, and 6 with heights 10, 6, and 10 (width 3, height 6).

Practice

1. What is the main purpose of using a stack in the Largest Rectangle in Histogram problem?

easy

A. To sort the histogram bars by height

B. To store the maximum area found so far

C. To keep track of bars' indices with increasing heights

D. To reverse the order of histogram bars

Solution

1. Step 1: Understand stack usage

   The stack stores indices of bars in increasing height order to find boundaries efficiently.

2. Step 2: Purpose in algorithm

   This helps quickly calculate the largest rectangle when a smaller height bar is found.

3. Final Answer:

   To keep track of bars' indices with increasing heights -> Option C

4. Quick Check:

   Stack tracks increasing bars = B [OK]

Hint: Stack stores indices of increasing heights [OK]

Common Mistakes:

• Thinking stack sorts bars by height
• Using stack to store areas instead of indices
• Ignoring the order of bars in stack

2. Which Go syntax correctly declares a stack to hold indices for the histogram bars?

easy

A. var stack []int

B. stack := make(map[int]int)

C. stack := []string{}

D. var stack int

Solution

1. Step 1: Identify stack type

   The stack holds indices, which are integers, so it should be a slice of int.

2. Step 2: Check syntax correctness

   "var stack []int" declares an empty slice of int, suitable for stack operations.

3. Final Answer:

   var stack []int -> Option A

4. Quick Check:

   Stack as []int slice = C [OK]

Hint: Use slice of int for stack indices [OK]

Common Mistakes:

• Using map instead of slice for stack
• Declaring stack as int instead of slice
• Using string slice for integer indices

3. What is the output of the following Go code snippet for histogram heights [2, 1, 5, 6, 2, 3]?

func largestRectangleArea(heights []int) int {
    stack := []int{}
    maxArea := 0
    for i := 0; i <= len(heights); i++ {
        var h int
        if i == len(heights) {
            h = 0
        } else {
            h = heights[i]
        }
        for len(stack) > 0 && h < heights[stack[len(stack)-1]] {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            var width int
            if len(stack) == 0 {
                width = i
            } else {
                width = i - stack[len(stack)-1] - 1
            }
            area := height * width
            if area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }
    return maxArea
}

fmt.Println(largestRectangleArea([]int{2, 1, 5, 6, 2, 3}))

medium

A. 6

B. 12

C. 8

D. 10

Solution

1. Step 1: Trace stack and area calculation

   Process bars: max area found is 10 (from bars 5 and 6 with width 2).

2. Step 2: Confirm max area

   No larger rectangle found; 10 is the largest rectangle area.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Largest rectangle area = 10 [OK]

Hint: Largest area is max of all popped rectangles [OK]

Common Mistakes:

• Forgetting to add a zero height bar at end
• Incorrect width calculation after popping stack
• Not updating maxArea correctly

4. Identify the bug in this Go code snippet for Largest Rectangle in Histogram:

for i := 0; i < len(heights); i++ {
    for len(stack) > 0 && heights[i] < heights[stack[len(stack)-1]] {
        height := heights[stack[len(stack)-1]]
        stack = stack[:len(stack)-1]
        width := i
        if len(stack) > 0 {
            width = i - stack[len(stack)-1] - 1
        }
        area := height * width
        if area > maxArea {
            maxArea = area
        }
    }
    stack = append(stack, i)
}
return maxArea

medium

A. Loop should run until i <= len(heights) with a sentinel zero height

B. Width calculation is incorrect when stack is empty

C. Stack should store heights, not indices

D. maxArea should be reset inside the loop

Solution

1. Step 1: Check loop boundary

   The loop misses processing the last bars fully without a sentinel zero height at the end.

2. Step 2: Fix loop to include sentinel

   Loop should run until i <= len(heights) and treat i == len(heights) as height 0 to pop all remaining bars.

3. Final Answer:

   Loop should run until i <= len(heights) with a sentinel zero height -> Option A

4. Quick Check:

   Loop boundary with sentinel zero fixes bug [OK]

Hint: Add sentinel zero height to process all bars [OK]

Common Mistakes:

• Not adding sentinel zero height
• Incorrect width calculation when stack empty
• Resetting maxArea inside loop incorrectly

5. Given a histogram with heights [6, 2, 5, 4, 5, 1, 6], what is the largest rectangle area using the stack method?

hard

A. 12

B. 15

C. 8

D. 10

Solution

1. Step 1: Analyze bars and stack operations

   Largest rectangle is formed by bars with min height 5 spanning width 3 (indices 2 to 4: heights 5,4,5), area = 5*3 = 15.

2. Step 2: Confirm no larger area

   Other rectangles like 4*3=12 or 2*5=10 are smaller; 15 is maximum.

3. Final Answer:

   15 -> Option B

4. Quick Check:

   Max rectangle area = 15 [OK]

Hint: Check width between popped bars for max area [OK]

Common Mistakes:

• Calculating width incorrectly
• Missing wider rectangle spanning multiple bars
• Not popping all bars at the end