← Expedia questions

Largest sub-matrix containing most 1s with at least one 1 per row

Filed under Expedia

Free read 3 of 3

Identify rows that contain at least one 1.

The question

Given a binary matrix, find the largest sub-matrix containing the maximum number of 1s such that every row in the sub-matrix contains at least one 1.

Constraints

  • Matrix size M x N
  • Sub-matrix must be contiguous

Approach

  1. Identify rows that contain at least one 1.

Tips

  • What they are testing: Consider matrices with all 0s or all 1s.
  • Common mistake: Overcomplicating the row-constraint; focus on identifying valid rows first.

Related Expedia questions

Collected from public candidate posts and coding forums. Updated Nov 2026.