Last Updated: 26 Nov, 2020
Minimum Sum in matrix
Moderate
Asked in companies
You are given a 2D matrix ‘ARR’ of size ‘N x 3’ having integers, where ‘N’ is the number of rows.
Your task is to find the smallest sum possible while taking one element from each row.
The rules for selecting elements are as follows-
1. In a row, after selecting an element at a given position, you cannot select the element directly below it
2. You can only select elements that are not directly below the previously selected element.
Input format:
The first line contains a single integer ‘T’ denoting the number of test cases.
The first line of every test case contains a single integer, ‘N’ denoting the number of rows.
Then each of the ‘N’ rows contains three elements.
Output format:
For each test case, return the smallest sum possible as per the rules.
Output for each test case is printed on a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^3
0 <= ARR[i][j] <= 10^3
Where ‘ARR[i][j]’ denotes the matrix element at the jth column in the ith row
Time Limit: 1 sec
Approaches
Approach:
- The idea here is to find all possible combinations with the help of recursion.
- Let say we are currently at (i, j). Now we want to move to the (i+1)th row. We can go to any column that means we have a total of 3 options available in that row.
- By the definition of the problem, no two chosen elements belong to the same column. In other words, if we are at (i, j) we can go to (i+1, k) provided k != j.
- At each iteration, we keep track of the minimum value of that function call.
- The base condition of this recursive function is when i == N-1 (i.e., the last row). So, we just return the matrix entry at (i, j).
Algorithm:
- Create a variable ans initialized to a large integer value.
- Now call the recursive solve() function on every value in the 0th row and update the answer as min(ans, solve(0, col, N, ARR)).
- Now the solve() function takes 4 parameters i.e (currentRow, currentColumn, N, ARR).
- Inside the solve() function perform the following steps:
- First, check the base condition that if we reach the last row then return ARR[currentRow][currentColumn].
- Now solve for the current state and for each state there are 3 options available.
- Make a variable current initialized to infinity.
- Now iterate through all 3 options from k = 0 to k = 3 and where k is not equal to currentColumn update current as min(current, ARR[currentRow][currentColumn] + solve(currentRow + 1, k, N, ARR).
- Finally, return the value of current from the solve() function.
- Finally, return the ans.
Approach:
- If you look closely at ‘approach 1’, there are repeated subproblems. So we will use Dynamic Programming to handle these repeated subproblems.
- We can store the result of each function call in some new array, and if we encounter a repeated subproblem, then simply return the previously saved result. This technique is known as memoization.
Algorithm:
- Create a 2D array memo of size (N+1)*(4), to store the result of the function calls. Here, memo[i][j] implies that if we are at (i, j) then what would be the minimum value after that.
- Initialize the memo array with -1.
- Declare a variable ans initialized with a large integer value.
- Define a function solve(currentRow, currentColumn, N, ARR, memo), where currentRow is the current row, currentColumn is the current column, N is the number of rows and columns in the matrix, ARR is the given matrix and memo is the array to store the already calculated result.
- Run a loop from col = 0 to col < 3, in each iteration do:
- ans = min(ans, solve(0, i, N, ARR, memo))
- Inside the function solve() perform the following steps:
- First, check the base condition that if we reach the last row then return ARR[currentRow][currentColumn].
- If we have already solved the current function call i.e memo[currentRow][currentCol] is not equal to -1 then return the stored value i.e memo[currentRow][currentCol].
- Create a variable current initialized to infinity.
- Now, run a loop from k = 0 to k < 3, in each iteration do:
- k is not equal to currentColumn update current as min(current, ARR[currentRow][currentColumn] + solve(currentRow + 1, k, N, ARR, memo).
- While retuning the value of current store them in memo[currentRow][currentCol] for later use.
- Return the ans.
Approach:
- Since in each row, there are 3 elements and if we take 2 rows at a time and find all possible sum as per the rules there could be 6 combinations.
- So, we will iterate over all the N-1 rows, and for each row, we will find all the possible sums with respect to the row next to the current row.
- The possible sums will be:
- ARR[i][1] + ARR[i+1][0]
- ARR[i][2] + ARR[i+1][0]
- ARR[i][0] + ARR[i+1][1]
- ARR[i][2] + ARR[i+1][1]
- ARR[i][0] + ARR[i+1][2]
- ARR[i][1] + ARR[i+1][2]
- These sums are stored in a temporary array temp of size 6 and then we will update the row next to the current row i.e (i+1)th row with sums we calculated above such that each column has a minimum sum. This will be done:
- ARR[i+1][0] = minimum(temp[0], temp[1])
- ARR[i+1][1] = minimum(temp[2], temp[3])
- ARR[i+1][2] = minimum(temp[4], temp[5])
- You can visualize it in this way that if we have two rows and we have to find the minimum sum then there will be 6 combinations as mentioned above and in the 2nd row, each column will have two possible values of sums calculated above out of which we have to consider the minimum value for each column. Now if we find the minimum value in the whole 2nd row then that will be our required answer.
- Similarly, if we perform the above operations on N-1 rows then finally the minimum value in the last row will be our required answer.
- Now when we have iterate over all the N-1 rows then our final row will contain three possible sums as per the rules. So, we find the minimum of all three values present in the last row and that will be our required answer.
Algorithm:
- Create an array temp of size 6.
- Now iterate over all the N-1 rows and for each row perform the following operations:
- Find all the possible sums:
- temp[0] = ARR[i][1] + ARR[i+1][0]
- temp[0] = ARR[i][1] + ARR[i+1][0]
- temp[1] = ARR[i][2] + ARR[i+1][0]
- temp[2] = ARR[i][0] + ARR[i+1][1]
- temp[3] = ARR[i][2] + ARR[i+1][1]
- temp[4] = ARR[i][0] + ARR[i+1][2]
- temp[5] = ARR[i][1] + ARR[i+1][2]
- Now update the (i+1)th row:
- ARR[i+1][0] = min(temp[0], temp[1])
- ARR[i+1][1] = min(temp[2], temp[3])
- ARR[i+1][2] = min(temp[4], temp[5])
- Find all the possible sums:
- Now finally our answer will be minimum(ARR[N-1][0], ARR[N-1][1], ARR[N-1][2]).
Similar problems