Grokking Amazon Coding Interview
Ask Author
Back to course home

0% completed

Vote For New Content
Largest Submatrix With Rearrangements (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given a binary matrix matrix of size m x n. You are allowed to shuffle the columns of the matrix in any order.

Return the area of the largest submatrix, whose all elements are 1 after shuffling the columns of the matrix.

Examples

Example 1:

  • Input:
[[1,0,1],
 [1,1,1],
 [1,0,1]]
  • Expected Output: 6
Image
  • Justification: By swapping the 2<sup>nd</sup> and 3<sup>rd</sup> columns, we can form a 2x2 rectangle of 1s. It forms the largest rectangle of 1s with an area of 6.

Example 2:

  • Input:
[[0,1],
 [1,1]]
  • Expected Output: 2
Image
  • Justification: The columns can be rearranged (although in this case, it's not necessary) to form the largest rectangle of 1s that is 1x2 or 2x1. The area is 2.

Example 3:

  • Input:
[[1,1,0,0],
 [1,0,1,1], 
 [1,1,1,1],
 [0,1,1,0]]
  • Expected Output: 6
Image
  • Justification: By swapping the 2<sup>nd</sup> and 4<sup>th</sup> column, we can form a 3x2 rectangle of 1s. It forms the largest rectangle of 1s with an area of 6.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible