Minimum Crossover Cells

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in companies
OracleFacebookGrab

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
2 1 2
3 1 1 1
1 3
4
2 2 2
2 2 2
2 2 2
2 2 2
Sample Output 1 :
1
0
Explanation Of Sample Input 1 :
For the first test case, if we draw the line from the one unit from the left end, it will cross only one cell. There is no lower possibility than this here.

For the second test case, if we draw the line from the two units from the left, it will cross none of the cells.
Sample Input 2 :
2
6
4 1 2 1 2
1 6
3 3 2 1
2 3 3
5 1 1 2 1 1
4 2 2 1 1
1
1 1
Sample Output 2 :
3
1
Hint

Try to think of iterating over the width of the matrix.

Approaches (1)
Straight forward approach

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:

  1. Initialize array 'endCount' to store the count of the cells ending at the particular position.
  2. Initialize variable 'width' to store the width of the matrix.
  3. Initialize variable 'minimumCrossover' with 'N' to store the minimum number of cells crossed.
  4. 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.
  5. Loop over the 'width' and update the variable 'minimumCrossover' with minimum of it and 'n' - 'endCount[i]'.
  6. Return 'minimumCrossover'.
Time Complexity

O(N ^ 2)), where 'N' is the length of the input matrix.

 

Since we are iterating over the whole matrix row, there can be maximum 'N' cells for each row. Hence worst-case time complexity will be O(N^2).

Space Complexity

O(N), where 'N' is the length of the input matrix.

 

We are using the extra array to store the 'end_count' of cells. Hence it will consume linear space. The space complexity will be O(N).

Code Solution
(100% EXP penalty)
Minimum Crossover Cells
Full screen
Console