{"id":1965,"date":"2020-07-01T09:47:01","date_gmt":"2020-07-01T09:47:01","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1965"},"modified":"2022-03-29T10:00:50","modified_gmt":"2022-03-29T10:00:50","slug":"max-rectangle","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/max-rectangle\/","title":{"rendered":"Max Rectangle"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used:<\/h3>\n
\n

DP\/recursion and Stack.<\/p>\n<\/blockquote>\n

Difficulty Level:<\/h3>\n
\n

Hard.<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a 2D binary matrix filled with 0\u2019s and 1\u2019s, find the largest rectangle containing all ones and print its area.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case:<\/h4>\n
Input:\n1\n5 5\n0 0 1 0 1\n0 1 1 1 1\n1 1 1 1 1\n1 1 1 1 1\n0 0 1 1 1\n\nOutput:\n12\n\nExplanation:\nThe inner matrix from index (1,1) to index (3,4) with area 12(3*4) gives the appropriate solution.<\/code><\/pre>\n
Solving Approach:<\/h3>\n
\n
The idea is to update each column of a given row with corresponding column of previous row and find largest histogram area for for that row.<\/p>\n<\/blockquote>\n
Steps:<\/code><\/p>\n
\n
    \n
  1. Find maximum area for row[0]<\/li>\n
  2. for each row in 1 to N – 1\n
    for each column in that row\nif A[row][column] == 1 then update A[row][column] with A[row][column] += A[row - 1][column]\nfind area for that row\nand update maximum area so far<\/code><\/pre>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    Solutions:<\/h3>\n
    \t\t\t\t\t\t