Minimum Sum in matrix

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
15 upvotes
Asked in companies
OlaAmazonWolters Kluwer

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 
1 2 3
4 5 6
1
3 5 6
Sample Output 1:
6
3
Explanation for Sample Input 1:
For the first test case, 
There are only six possible sums as per rules:
(i) 1 -> 5 with sum equal to 6.
(ii) 1 -> 6 with sum equal to 7.
(iii) 2 -> 4 with sum equal to 6.
(iv) 2 -> 8 with sum equal to 8.
(v) 3 -> 4 with sum equal to 7.
(vi) 3 -> 5 with sum equal to 8.
So the minimum among all of these is 6. So the output is 6.


For the second test case, 
Since the given matrix has a single row so the possible sum can be {3, 5, 6} and the minimum among all of them is 3. So the output is 3.
Sample Input 2:
2
2
4 5 6
7 8 9
2
4 8 9
6 10 12
Sample Output 2:
12
14
Explanation for Sample Input 2:
For the first test case, 
There are only six possible sums as per rules:
(i) 4 -> 8 with sum equal to 12 .
(ii) 4 -> 9 with sum equal to 13.
(iii) 5 -> 7 with sum equal to 12.
(iv) 5 -> 9 with sum equal to 14.
(v) 6 -> 7 with sum equal to 13.
(vi) 6 -> 8 with sum equal to 14.
So the minimum among all of these is 12. So the output is 12.


For the second test case, 
There are only six possible sums as per rules:
(i) 4 -> 10 with sum equal to 14.
(ii) 4 -> 12 with sum equal to 16.
(iii) 8 -> 6 with sum equal to 14.
(iv) 8 -> 12 with sum equal to 20.
(v) 9 -> 6 with sum equal to 15.
(vi) 9 -> 10 with sum equal to 19.
So the minimum among all of these is 14. So the output is 14.
Hint

Recursively find all the combinations.

Approaches (3)
Brute Force - Recursion

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.
Time Complexity

O(2^N), where ‘N’ is the number of rows.

 

We are using the recursion for forming all possible combinations. As in each function call, we have 2 options available. Hence, the time complexity will be O(2^N). So the overall time complexity will be O(2^N).   

Space Complexity

O(1).

 

Since we are using a recursive function and in the worst case, there can be O(Z) states where Z = 3 in the recursion stack which does not have much effect on the overall space complexity. Therefore, constant space is being used. So, the overall space complexity will be O(1). 

Code Solution
(100% EXP penalty)
Minimum Sum in matrix
Full screen
Console