Largest Rectangle In Histogram

                                            
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int maxArea = 0;
        heights.push_back(0);
        for (int i = 0; i < heights.size(); ++i) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int h = heights[st.top()];
                st.pop();
                int w = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            st.push(i);
        }
        return maxArea;
    }
};

                                            
class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int i = 0;
        while (i < heights.length) {
            if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
        }
        
        while (!stack.isEmpty()) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        
        return maxArea;
    }
}

                                            
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        """
        stack = []
        max_area = 0
        heights.append(0)
        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, h * w)
            stack.append(i)
        return max_area

                                            
int largestRectangleArea(int* heights, int heightsSize) {
    int maxArea = 0;
    int stack[heightsSize + 1];
    int top = -1;
    for (int i = 0; i <= heightsSize; i++) {
        while (top != -1 && (i == heightsSize || heights[i] < heights[stack[top]])) {
            int height = heights[stack[top--]];
            int width = top == -1 ? i : i - stack[top] - 1;
            maxArea = fmax(maxArea, height * width);
        }
        stack[++top] = i;
    }
    return maxArea;
}

                                            
public class Solution {
    public int LargestRectangleArea(int[] heights) {
        if (heights == null || heights.Length == 0) {
            return 0;
        }
        
        int maxArea = 0;
        Stack<int> stack = new Stack<int>();
        
        for (int i = 0; i <= heights.Length; i++) {
            int h = (i == heights.Length) ? 0 : heights[i];
            if (stack.Count == 0 || h >= heights[stack.Peek()]) {
                stack.Push(i);
            } else {
                int top = stack.Pop();
                int width = stack.Count == 0 ? i : i - 1 - stack.Peek();
                maxArea = Math.Max(maxArea, heights[top] * width);
                i--;
            }
        }
        
        return maxArea;
    }
}

                                            
/**
 * @param {number[]} heights
 * @return {number}
 */
const largestRectangleArea = (heights) => {
    let maxArea = 0;
    const stack = [];
    heights.push(0);

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

    return maxArea;
};

                                            
function largestRectangleArea(heights: number[]): number {
    let maxArea = 0;
    const stack: number[] = [];
    heights.push(0);
    for (let i = 0; i < heights.length; i++) {
        while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
            const height = heights[stack.pop() as number];
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
};

                                            
class Solution {
    /**
     * @param Integer[] $heights
     */
    function largestRectangleArea($heights) {
        $heights[] = 0;
        $stack = [];
        $maxArea = 0;
        for ($i = 0; $i < count($heights); $i++) {
            while (!empty($stack) && $heights[$i] < $heights[end($stack)]) {
                $height = $heights[array_pop($stack)];
                $width = empty($stack) ? $i : $i - end($stack) - 1;
                $maxArea = max($maxArea, $height * $width);
            }
            $stack[] = $i;
        }
        return $maxArea;
    }
}

                                            
class Solution {
    func largestRectangleArea(_ heights: [Int]) -> Int {
        
        var stack: [Int] = []
        var maxArea = 0
        var current = 0
        
        while current < heights.count {
            if stack.isEmpty || heights[current] >= heights[stack.last ?? 0] {
                stack.append(current)
                current += 1
            } else {
                let height = heights[stack.removeLast()]
                let width = stack.isEmpty ? current : current - stack.last! - 1
                maxArea = max(maxArea, height * width)
            }
        }
        
        while !stack.isEmpty {
            let height = heights[stack.removeLast()]
            let width = stack.isEmpty ? current : current - stack.last! - 1
            maxArea = max(maxArea, height * width)
        }
        
        return maxArea
    }
}

                                            
class Solution {
    fun largestRectangleArea(heights: IntArray): Int {
        var maxArea = 0
        val stack = Stack<Int>()
        val updatedHeights = IntArray(heights.size + 2)
        
        for (i in 0 until heights.size) {
            updatedHeights[i + 1] = heights[i]
        }
        
        stack.push(0)
        
        for (i in 1 until updatedHeights.size) {
            while (updatedHeights[i] < updatedHeights[stack.peek()]) {
                val height = updatedHeights[stack.pop()]
                val width = i - stack.peek() - 1
                maxArea = maxOf(maxArea, height * width)
            }
            stack.push(i)
        }
        
        return maxArea
    }
}

                                            
class Solution {
  int largestRectangleArea(List<int> heights) {
    int maxArea = 0;
    List<int> stack = [];
    heights.insert(0, 0);
    heights.add(0);

    for (int i = 0; i < heights.length; i++) {
      while (stack.isNotEmpty && heights[i] < heights[stack.last]) {
        int height = heights[stack.removeLast()];
        int width = i - stack.last - 1;
        maxArea = max(maxArea, height * width);
      }
      stack.add(i);
    }

    return maxArea;
  }
}

                                            
func largestRectangleArea(heights []int) int {
    if len(heights) == 0 {
        return 0
    }
    
    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]
            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
}

                                            
def largest_rectangle_area(heights)
    stack = []
    max_area = 0
    heights.push(0)
    
    heights.each_with_index do |height, i|
        while !stack.empty? && heights[stack.last] > height
            h = heights[stack.pop]
            w = stack.empty? ? i : i - stack.last - 1
            max_area = [max_area, h * w].max
        end
        stack.push(i)
    end
    
    return max_area
end

                                            
object Solution {
    def largestRectangleArea(heights: Array[Int]): Int = {
        var maxArea = 0
        val stack = scala.collection.mutable.Stack[Int]()

        for (i <- heights.indices) {
            while (stack.nonEmpty && heights(i) < heights(stack.top)) {
                val height = heights(stack.pop())
                val width = if (stack.isEmpty) i else i - stack.top - 1
                maxArea = maxArea.max(height * width)
            }
            stack.push(i)
        }

        while (stack.nonEmpty) {
            val height = heights(stack.pop())
            val width = if (stack.isEmpty) heights.length else heights.length - stack.top - 1
            maxArea = maxArea.max(height * width)
        }

        maxArea
    }
}

                                            
impl Solution {
    pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
        let mut stack = vec![];
        let mut max_area = 0;
        let mut i = 0;

        while i < heights.len() {
            if stack.is_empty() || heights[i] >= heights[*stack.last().unwrap()] {
                stack.push(i);
                i += 1;
            } else {
                let top = stack.pop().unwrap();
                let width = if stack.is_empty() {
                    i as i32
                } else {
                    (i - stack.last().unwrap() - 1) as i32
                };
                max_area = max_area.max(heights[top] * width);
            }
        }

        while !stack.is_empty() {
            let top = stack.pop().unwrap();
            let width = if stack.is_empty() {
                i as i32
            } else {
                (i - stack.last().unwrap() - 1) as i32
            };
            max_area = max_area.max(heights[top] * width);
        }

        max_area
    }
}

To solve this coding challenge, it is essential to understand the underlying concepts and the steps required to find the area of the largest rectangle within a histogram. Below, I break down the approach and the steps involved with detailed explanations and pseudocode.

Explanation

The problem is to determine the area of the largest rectangle contained within a histogram represented by an array of integers where each element corresponds to the height of a bar and the width of each bar is 1.

Problem Breakdown

Histogram Representation :

Each element of the array represents a bar's height.
The width of each bar is uniformly 1.

Goal :

To find the maximum rectangular area which can be formed by one or more contiguous bars.

Approach

The problem can be efficiently solved using a monotonic stack . Here is why:

A stack helps keep track of the indices of the bars in an increasing order of their heights.
By maintaining this order, when a bar of lower height is encountered, it triggers the calculation of the potential largest rectangle formed with the heights stored in the stack.

Detailed Steps in Pseudocode

The core idea is to iterate through the histogram and utilize the stack to manage the heights and their indices, calculating the potential largest areas dynamically.

Initialize :

A stack to keep track of bar indices.
A variable
max_area

to store the maximum rectangle area found.

Append a Sentinel Value :

Append a
0

height to ensure all heights are processed and the stack is emptied by the end of the iteration.

Iterate Through Each Height :

For each height in the histogram, if it is lower than the height of the bar represented by the index at the top of the stack, it implies a boundary for potential rectangles.

Calculate Area :

Pop the index from the stack, calculate the height of the rectangle using the popped index.
Calculate the width based on the current index and the index of the remaining top stack element.
Update
max_area

with the maximum value of the current calculated area and the previous
max_area

.

Return the Maximum Area :

Finally, after processing all bars, return the maximum area calculated.

Pseudocode

                                            
# Initialize an empty stack to store bar indices
stack = []

# Initialize max_area to keep track of the largest rectangle
max_area = 0

# Append 0 to heights to ensure the stack is emptied at the end
heights.append(0)

# Iterate over each bar in the histogram, including the appended 0 height
for current_index in range(length of heights):
    
    # While stack is not empty and current height is less than height at stack's top index
    while stack is not empty and heights[current_index] < heights[stack's top index]:
        
        # Pop the top index from the stack, calculate height using this index
        height_of_bar = heights[stack.pop()]
        
        # Calculate width: If stack is empty, width is the current index, else width is difference between current index and new top index - 1
        if stack is empty:
            width = current_index
        else:
            width = current_index - stack's top index - 1
        
        # Calculate area using height and width
        area = height_of_bar * width
        
        # Update max_area if current area is larger
        max_area = max(max_area, area)
    
    # Push the current index to the stack
    stack.append(current_index)

# Return the max_area found
return max_area

This pseudocode provides a clear step-by-step method to find the largest rectangular area within the histogram. Each step is annotated to ensure that anyone reading can understand the purpose behind each operation. By using a stack to keep track of indices and dynamically calculating potential areas, we efficiently solve the problem with optimal time complexity.