Largest sub-matrix containing most 1s with at least one 1 per row
Filed under Expedia
Free read 3 of 3Identify 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
Identify rows that contain at least one 1.
Use a sliding window approach on the valid row segments.
Calculate the area for valid contiguous row blocks and track the maximum.
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.