Maximal Rectangle

                                            
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty()) {
            return 0;
        }
        
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int>> heights(rows, vector<int>(cols, 0));
        int maxArea = 0;
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (matrix[i][j] == '1') {
                    heights[i][j] = (i == 0) ? 1 : heights[i - 1][j] + 1;
                }
            }
            maxArea = max(maxArea, largestRectangleArea(heights[i]));
        }
        
        return maxArea;
    }
    
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> st;
        int maxArea = 0;
        
        for (int i = 0; i <= n; ++i) {
            while (!st.empty() && (i == n || heights[i] < heights[st.top()])) {
                int height = heights[st.top()];
                st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, height * width);
            }
            st.push(i);
        }
        
        return maxArea;
    }
};

                                            
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int[] heights = new int[n];
        int maxArea = 0;
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        
        return maxArea;
    }
    
    private int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0) {
            return 0;
        }
        
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for(int i = 0; i < n; i++) {
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        
        stack.clear();
        
        for(int i = n - 1; i >= 0; i--) {
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        
        int maxArea = 0;
        for(int i = 0; i < n; i++) {
            maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
        }
        
        return maxArea;
    }
}

                                            
class Solution(object):
    def maximalRectangle(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        
        def largestRectangleArea(heights):        
            stack = [-1]
            max_area = 0
            heights.append(0)
            
            for i in range(len(heights)):
                while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:
                    h = heights[stack.pop()]
                    w = i - stack[-1] - 1
                    max_area = max(max_area, h * w)
                stack.append(i)
            
            return max_area
        
        cols = len(matrix[0])
        heights = [0] * cols
        max_area = 0
        
        for row in matrix:
            for i in range(cols):
                heights[i] = heights[i] + 1 if row[i] == '1' else 0
            max_area = max(max_area, largestRectangleArea(heights))
            
        return max_area

                                            
int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize) {
    if (matrixSize == 0 || *matrixColSize == 0) {
        return 0;
    }

    int maxArea = 0;
    int rows = matrixSize;
    int cols = *matrixColSize;
    int heights[cols];

    for (int i = 0; i < cols; i++) {
        heights[i] = 0;
    }

    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < cols; col++) {
            if (matrix[row][col] == '1') {
                heights[col]++;
            } else {
                heights[col] = 0;
            }
        }

        int stack[cols + 1];
        int top = -1;

        for (int i = 0; i <= cols; i++) {
            while (top >= 0 && (i == cols || 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 MaximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) {
            return 0;
        }
        
        int rows = matrix.Length;
        int cols = matrix[0].Length;
        int[] heights = new int[cols];
        int maxArea = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }
            maxArea = Math.Max(maxArea, LargestRectangleArea(heights));
        }
        
        return maxArea;
    }
    
    private int LargestRectangleArea(int[] heights) {
        int maxArea = 0;
        Stack<int> stack = new Stack<int>();
        
        for (int i = 0; i <= heights.Length; i++) {
            int height = i == heights.Length ? 0 : heights[i];
            while (stack.Count > 0 && height < heights[stack.Peek()]) {
                int h = heights[stack.Pop()];
                int w = stack.Count == 0 ? i : i - stack.Peek() - 1;
                maxArea = Math.Max(maxArea, h * w);
            }
            stack.Push(i);
        }
        
        return maxArea;
    }
}

                                            
/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    if (matrix === null || matrix.length === 0) {
        return 0;
    }

    const rows = matrix.length;
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
        }
        maxArea = Math.max(maxArea, calculateMaxArea(heights));
    }

    return maxArea;
};

const calculateMaxArea = (heights) => {
    const stack = [];
    let maxArea = 0;

    for (let i = 0; i <= heights.length; i++) {
        while (stack.length !== 0 && (i === heights.length || 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 maximalRectangle(matrix: string[][]) {
    if (matrix.length === 0) {
        return 0;
    }

    let maxArea = 0;
    const heights = Array(matrix[0].length).fill(0);
    
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
        }
        maxArea = Math.max(maxArea, calculateMaxArea(heights));
    }
    
    return maxArea;
};

function calculateMaxArea(heights: number[]) {
    const stack = [];
    let maxArea = 0;
    
    for (let i = 0; i <= heights.length; i++) {
        while (stack.length !== 0 && (i === heights.length || 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;
}

                                            
class Solution {
    /**
     * @param String[][] $matrix
     * @return Integer
     */
    function maximalRectangle($matrix) {
        $maxArea = 0;
        if (empty($matrix)) {
            return $maxArea;
        }
        
        $rows = count($matrix);
        $cols = count($matrix[0]);
        $heights = array_fill(0, $cols, 0);
        
        for ($i = 0; $i < $rows; $i++) {
            for ($j = 0; $j < $cols; $j++) {
                $heights[$j] = $matrix[$i][$j] == '1' ? $heights[$j] + 1 : 0;
            }
            $maxArea = max($maxArea, $this->largestRectangleArea($heights));
        }
        
        return $maxArea;
    }
    
    function largestRectangleArea($heights) {
        $heights[] = 0;
        $stack = [];
        $maxArea = 0;
        
        for ($i = 0; $i < count($heights); $i++) {
            while (!empty($stack) && $heights[$i] < $heights[end($stack)]) {
                $height = array_pop($stack);
                $width = empty($stack) ? $i : $i - end($stack) - 1;
                $maxArea = max($maxArea, $heights[$height] * $width);
            }
            $stack[] = $i;
        }
        
        return $maxArea;
    }
}

                                            
class Solution {
    func maximalRectangle(_ matrix: [[Character]]) -> Int {
        guard matrix.count > 0 && matrix[0].count > 0 else {
            return 0
        }
        
        let rows = matrix.count
        let cols = matrix[0].count
        var heights = Array(repeating: 0, count: cols)
        var maxArea = 0
        
        for i in 0..<rows {
            for j in 0..<cols {
                if matrix[i][j] == "1" {
                    heights[j] += 1
                } else {
                    heights[j] = 0
                }
            }
            maxArea = max(maxArea, largestRectangleArea(heights))
        }
        
        return maxArea
    }
    
    func largestRectangleArea(_ heights: [Int]) -> Int {
        var stack = [Int]()
        var maxArea = 0
        var i = 0
        
        while i < heights.count {
            if stack.isEmpty || heights[i] >= heights[stack.last!] {
                stack.append(i)
                i += 1
            } else {
                let height = heights[stack.removeLast()]
                let width = stack.isEmpty ? i : i - stack.last! - 1
                maxArea = max(maxArea, height * width)
            }
        }
        
        while !stack.isEmpty {
            let height = heights[stack.removeLast()]
            let width = stack.isEmpty ? i : i - stack.last! - 1
            maxArea = max(maxArea, height * width)
        }
        
        return maxArea
    }
}

                                            
class Solution {
    fun maximalRectangle(matrix: Array<CharArray>): Int {
        if(matrix.isEmpty()) return 0
        
        val n = matrix.size
        val m = matrix[0].size
        val heights = IntArray(m)
        var maxArea = 0
        
        for (i in 0 until n) {
            for (j in 0 until m) {
                heights[j] = if (matrix[i][j] == '1') heights[j] + 1 else 0
            }
            maxArea = maxOf(maxArea, largestRectangleArea(heights))
        }
        
        return maxArea
    }
    
    private fun largestRectangleArea(heights: IntArray): Int {
        val stack = LinkedList<Int>()
        var maxArea = 0
        var i = 0
        
        while (i <= heights.size) {
            val h = if (i == heights.size) 0 else heights[i]
            if (stack.isEmpty() || h >= heights[stack.peek()]) {
                stack.push(i)
                i++
            } else {
                val height = heights[stack.pop()]
                val width = if (stack.isEmpty()) i else i - stack.peek() - 1
                maxArea = maxOf(maxArea, height * width)
            }
        }
        
        return maxArea
    }
}

                                            
import 'dart:math';

class Solution {
  int maximalRectangle(List<List<String>> matrix) {
    if (matrix.isEmpty) return 0;
    
    int rows = matrix.length;
    int cols = matrix[0].length;
    
    List<List<int>> heights = List.generate(rows, (_) => List.filled(cols, 0));
    
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        if (matrix[i][j] == '1') {
          heights[i][j] = i == 0 ? 1 : heights[i - 1][j] + 1;
        }
      }
    }
    
    int maxArea = 0;
    for (int i = 0; i < rows; i++) {
      maxArea = max(maxArea, largestRectangleArea(heights[i]));
    }
    
    return maxArea;
  }
  
  int largestRectangleArea(List<int> heights) {
    List<int> stack = [];
    heights = List.from(heights)..add(0);
    int maxArea = 0;
    
    for (int i = 0; i < heights.length; i++) {
      while (stack.isNotEmpty && heights[i] < heights[stack.last]) {
        int h = heights[stack.removeLast()];
        int w = stack.isEmpty ? i : i - stack.last - 1;
        maxArea = max(maxArea, h * w);
      }
      stack.add(i);
    }
    
    return maxArea;
  }
}

                                            
func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 {
        return 0
    }
    rows, cols := len(matrix), len(matrix[0])
    heights := make([]int, cols)
    maxArea := 0

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if matrix[i][j] == '0' {
                heights[j] = 0
            } else {
                heights[j]++
            }
        }
        maxArea = max(maxArea, largestRectangleArea(heights))
    }

    return maxArea
}

func largestRectangleArea(heights []int) int {
    if len(heights) == 0 {
        return 0
    }

    stack := make([]int, 0)
    heights = append(heights, 0)
    maxArea := 0

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

    return maxArea
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# @param {Character[][]} matrix
# @return {Integer}
def maximal_rectangle(matrix)
    return 0 if matrix.empty?

    rows = matrix.size
    cols = matrix[0].size
    max_area = 0
    heights = Array.new(cols, 0)
    left = Array.new(cols, 0)
    right = Array.new(cols, cols)

    (0...rows).each do |i|
        cur_left = 0
        cur_right = cols

        (0...cols).each do |j|
            heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0
        end

        (0...cols).each do |j|
            if matrix[i][j] == '1'
                left[j] = [left[j], cur_left].max
            else
                left[j] = 0
                cur_left = j + 1
            end
        end

        (cols-1).downto(0).each do |j|
            if matrix[i][j] == '1'
                right[j] = [right[j], cur_right].min
            else
                right[j] = cols
                cur_right = j
            end
        end

        (0...cols).each do |j|
            max_area = [max_area, (right[j] - left[j]) * heights[j]].max
        end
    end

    return max_area
end

                                            
object Solution {
    def maximalRectangle(matrix: Array[Array[Char]]): Int = {
        if (matrix.isEmpty) return 0
        val rows = matrix.length
        val cols = matrix(0).length
        val heights = Array.fill(cols)(0)
        var maxArea = 0
        
        def largestRectangleArea(heights: Array[Int]): Int = {
            var stack = List.empty[Int]
            var maxArea = 0
            
            for (i <- 0 to heights.length) {
                while (stack.nonEmpty && (i == heights.length || heights(i) < heights(stack.head))) {
                    val h = heights(stack.head)
                    stack = stack.tail
                    val w = if (stack.isEmpty) i else i - stack.head - 1
                    maxArea = math.max(maxArea, h * w)
                }
                stack = i :: stack
            }
            maxArea
        }
        
        for (i <- 0 until rows) {
            for (j <- 0 until cols) {
                heights(j) = if (matrix(i)(j) == '1') heights(j) + 1 else 0
            }
            maxArea = math.max(maxArea, largestRectangleArea(heights))
        }
        
        maxArea
    }
}

                                            
impl Solution {
    pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
        let rows = matrix.len();
        if rows == 0 {
            return 0;
        }
        let cols = matrix[0].len();
        
        let mut left = vec![0; cols];
        let mut right = vec![cols; cols];
        let mut height = vec![0; cols];
        
        let mut max_area = 0;
        
        for i in 0..rows {
            let mut cur_left = 0;
            let mut cur_right = cols;
            
            for j in 0..cols {
                if matrix[i][j] == '1' {
                    height[j] += 1;
                } else {
                    height[j] = 0;
                }
            }
            
            for j in 0..cols {
                if matrix[i][j] == '1' {
                    left[j] = left[j].max(cur_left);
                } else {
                    left[j] = 0;
                    cur_left = j + 1;
                }
            }
            
            for j in (0..cols).rev() {
                if matrix[i][j] == '1' {
                    right[j] = right[j].min(cur_right);
                } else {
                    right[j] = cols;
                    cur_right = j;
                }
            }
            
            for j in 0..cols {
                max_area = max_area.max(height[j] * (right[j] - left[j]));
            }
        }
        
        max_area as i32
    }
}

To solve this coding challenge, we need to find the largest rectangle containing only 1's within a given binary matrix and return its area. The approach to solving this problem involves leveraging a helper function that computes the largest rectangle in a histogram. The primary strategy revolves around constructing histograms for each row in the matrix and then calculating the maximal rectangle for each of these histograms. Here's a step-by-step breakdown of how we can approach this problem, followed by the detailed steps in pseudocode.

Explanation:

Initial Validations : Check whether the given matrix is empty or its first row is empty. If either is true, return an area of 0 since there can be no rectangles.
Helper Function -
largestRectangleArea

:

This function computes the largest rectangle area in a histogram.
Use a stack to keep track of the indices of bars in the histogram.
Add a sentinel value (a zero) to the end of the heights array to trigger processing of any remaining bars in the stack.
As we iterate through the heights, if the current height is less than the height of the bar at the stack's top, calculate the area with the height of the bar at the top of the stack as the smallest (height).
Update the maximum area with the calculated area.

Iterate Through Rows :

Create an array
heights

where each element corresponds to the height of the histogram bar for the current column up to the current row.
If matrix[i][j] is '1', increment the corresponding
heights[j]

by 1, otherwise reset it to 0.
After updating the
heights

for a given row, call the
largestRectangleArea

function to find the maximal rectangle for that histogram and update the maximum rectangle area if the result is larger than the current maximum.

Return the Maximum Area :

After processing all rows, return the maximum rectangle area found.

Detailed Steps in Pseudocode:

                                            
# Define the main function to find the maximal rectangle in a binary matrix
function maximalRectangle(matrix):
    # Check if the matrix or the first row of the matrix is empty
    if matrix is empty or matrix[0] is empty:
        return 0 

    # Helper function to calculate the largest rectangle area in a histogram
    function largestRectangleArea(heights):
        stack = [-1]  # Initialize stack with a sentinel value
        max_area = 0  # Variable to store the maximum area
        append 0 to heights  # Add a sentinel value to heights array

        for i from 0 to length of heights:
            # Calculate area for current bar and bars in stack
            while stack's top is not -1 and heights[stack's top] >= heights[i]:
                height = heights[pop from stack]  # Get and remove the top height from stack
                width = i - stack's top - 1  # Calculate the width of the rectangle
                max_area = max(max_area, height * width)  # Update max_area if necessary
            append i to stack  # Push the current index to stack

        return max_area  # Return the maximum area found

    columns = length of matrix[0]  # Get the number of columns
    heights = array of size columns initialized to 0  # Heights array initialized to 0
    max_area = 0  # Variable to store the maximum rectangle area

    # Iterate over each row in the matrix
    for row in matrix:
        for i from 0 to columns - 1:
            # Update heights: increment if '1', reset if '0'
            if row[i] is '1':
                heights[i] += 1
            else:
                heights[i] = 0

        # Calculate the maximum rectangle area for the current histogram
        max_area = max(max_area, largestRectangleArea(heights))

    return max_area  # Return the maximum rectangle area found

In this pseudocode, we have both the main function

maximalRectangle

and the helper function

largestRectangleArea

robustly commented to ensure a thorough understanding of each step. The pseudocode approach closely follows the actual logic without being tied to any specific programming language syntax.