Grokking Amazon Coding Interview
Ask Author
Back to course home

0% completed

Vote For New Content
Largest Submatrix With Rearrangements (medium)
On this page

Problem Statement

Examples

Try it yourself

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!

On this page

Problem Statement

Examples

Try it yourself