714125. Binary matrix having maximum number of 1s
Easy
Binary Matrix Having Maximum Number of 1s
Summary
Given a binary matrix, find the maximum number of 1's in a sub-matrix of size k x k where k is the given integer. This problem involves finding the maximum sum of sub-arrays with a specific constraint.
Detailed Explanation
The problem can be solved by using a simple algorithm that iterates over each cell in the matrix and keeps track of the maximum number of 1's seen so far. The key idea is to maintain a sliding window of size k x k and update the count whenever the window moves.
Here's the step-by-step breakdown:
- Initialize the maximum count to 0.
- Iterate over each cell
(i, j)in the matrix:- If the cell contains a 1, increment the count for the current window.
- If the window is full (i.e., its size reaches
k x k), update the maximum count if necessary and slide the window by one cell to the right.
- Return the maximum count found.
Time Complexity: O(m * n) where m and n are the dimensions of the matrix.
Space Complexity: O(1) as we only use a constant amount of space to store the maximum count and the current window.
Here's an ASCII art diagram illustrating the sliding window:
0 | 0 | 1 | 0
---------
0 | 1 | 1 | 0
---------
1 | 1 | 0 | 1
---------
0 | 0 | 0 | 0
Window: [1, 1, 0, 1]
Optimized Solutions
Java
public int maxOnes(int[][] matrix, int k) {
int maxCount = 0;
for (int i = 0; i <= matrix.length - k; i++) {
for (int j = 0; j <= matrix[0].length - k; j++) {
int count = 0;
for (int x = 0; x < k; x++) {
for (int y = 0; y < k; y++) {
if (matrix[i + x][j + y] == 1) {
count++;
}
}
}
maxCount = Math.max(maxCount, count);
}
}
return maxCount;
}