Last Updated: 17 Nov, 2021
Minimum Crossover Cells
Moderate
Asked in companies
Given a matrix 'MAT' of 'N' rows, each row contains some irregular cells.
The irregular cells means size of each cell in each row is not fixed. It can be any finite value. The total width of all cells is the same.
Your task is to draw a vertical line from top to bottom of the matrix to cross the minimum number of cells. The line will cross the cell only if it does not go from the edge of it. Print the minimum number of crossed cells.
Input Format :
The first line of input contains an integer 'T', denoting the number of test cases.
The first line of each test case contains a single integer 'N' size of the input matrix ‘MAT’.
Each of the next 'N' contains an integer ‘K’ number of cells in the current row followed by ‘K’ integers cell sizes.
Output format :
For each test case, print the minimum number of crossed cells after drawing the line.
Output for each test case will be printed in a separate line.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10
1 <= 'N' <= 10^2
1 <= ‘K’ <= ‘N’
1 <= 'MAT[i]' <= ‘N’
1 <= SUM('MAT[i]') <= 'N'
SUM('MAT[i]') is same for each row
Time Limit : 1 sec
Approaches
Approach:
We know the width of the matrix, also we can precalculate how many cells are ending at the ith position from the left.
So, we can iterate over the cells first and store a number of cells ending at the particular position in the hashmap array.
Again we will iterate over the width of the matrix, and for each length, we will find the number of cells that will be crossover when we draw the line from this length. We will take the minimum of all such lines.
Algorithm:
- Initialize array 'endCount' to store the count of the cells ending at the particular position.
- Initialize variable 'width' to store the width of the matrix.
- Initialize variable 'minimumCrossover' with 'N' to store the minimum number of cells crossed.
- Loop over the rows of the matrix and update 'width' and array 'endCount' with the width of the matrix and the current count of the ending position of the cell.
- Loop over the 'width' and update the variable 'minimumCrossover' with minimum of it and 'n' - 'endCount[i]'.
- Return 'minimumCrossover'.