Given a 2D array of size n x n with k2 1's and rest all 0's, find the minimum number of swaps to bring all k2 1's in a k x k box.
Example test case:
Input:
1 0 1
1 0 0
0 0 1
n = 3, k = 2
Output: 2
Explanation: We can swap the 1 at [0, 2] -> [0,1] and the 1 at [2, 2] -> [1, 1]. Then we will have the array:
1 1 0
1 1 0
0 0 0
My idea was to iterate over all the k x k boxes to find the box with the maximum number of 1s. The answer would then be the number of 0s in that particular box. My code:
from itertools import product
# Take as input
n, k = 3, 2
arr = [[1, 0, 1], [1, 0, 0], [0, 0, 1]]
max_ones = 0
for row, col in product(range(n-k+1), range(n-k+1)):
sub_count = 0
for sub_row, sub_col in product(range(k), range(k)):
sub_count += arr[row+sub_row][col+sub_col]
max_ones = max(max_ones, sub_count)
print(k**2 - max_ones)Time Complexity: O(n2*k2)
Couldn't come up with a more optimal solution on the spot. Maybe a way to store the information of the position of 1s?
Comments (0)