Minimum total power consumption by both the current “+” & “-“

Given a matrix of size rows x cols called “power,” which represents the power associated with each cell in the field. There are two types of current flow in the field: “+” current starts from the top left corner, while “-” current starts from the top right corner. Both types of current can move in three directions: from a cell (i, j) to either (i + 1, j – 1), (i + 1, j), or (i + 1, j + 1). The power consumption between two cells is calculated as the absolute difference between the power values of the two cells: abs(power[i + 1][j + 1] – power[i][j]). The task is to calculate the minimum total power consumption by both the current “+” & “-” to reach the last row.

Note:   At any given point (i, j), both types of current cannot occupy the same cell simultaneously, as it would cause an electric shock.

Examples: 

Input: power[][] = {{2, 4}, {3, 9}}
Output: combined minimum power : 6
Explanation: The “+” current chooses the path 2 -> 3, and the “-” current chooses the path 4 -> 9. The minimum total power consumption [abs(3 – 2) + abs(9 – 4)] = 1 + 5 = 6

Input: power[][] = {{2, 4, 6}, {8, 0, 10}, {6, 3, 9}}
Output: combined minimum power : 10
Explanation:  The “+” current chooses the path 2 -> 0-> 3, and the “-” current chooses the path 6->10-> 9. The minimum total power consumption [abs(0 – 2) + abs(3 – 0) + abs(10 – 6) + abs(9 – 10)] = 5 + 5= 10.

Approach: To solve the problem using Recursion follow the below idea:

• As mentioned in the question, both “+” and “-” currents can move in three directions: (i + 1, j – 1), (i + 1, j), or (i + 1, j + 1). Therefore, the total combined directions will be 3 * 3 = 9. For each “+” current, there will be three possible ways for the “-” current to move. We need to consider all the possible 9 directions.
• The base case occurs when both the “+” and “-” currents reach the last row, which will be the minimum valid position. Once they reach the last row, it becomes the base case.
• Now, for all possible paths, we calculate the minimum and return it as the result.

Mathematically the recursion will look like the following:

• value = abs(power[next_i][next_j1] – power[i][j1]) + abs(power[next_i][next_J2] – power[i][j2]);
• value += totalPower(next_i, next_j1, next_j2, power, rows, cols);
• mini = min(mini, value);
• // base case { once it reaches to last row. }
  • i == power.size()-1;

Steps to solve the problem:

• Build a recursive function and pass the starting row, col for both the current.
• For each (i, j) check if it’s valid or not, if it’s valid store the power consumption and call recursion for next.
• compare all the paths and take out the minimum power consumption.

Below is the implementation for the above approach:

Combined Minimum Power: 10

Complexity Analysis: 

• Time Complexity: O(3^{n +} 3ⁿ) The above solution may try all the possiable path in worst case. Therefore time complexity of the above solution is exponential.
• Auxiliary Space: O(n) where n is recursion stack space.

Using Memoization :

Each state of the solution can be uniquely identified using three variables – rows,col1 & col2 (for both “+” and “-“) . So create a 3D array to store the value of each state to avoid recalculation of the same state.

Below is the implementation of the above approach:

Combined Minimum Power: 10

Complexity Analysis: 

• Time Complexity: The time complexity of the given solution is O(N³), where N represents the number of columns in the power matrix. This is because, at each cell (i, j1, j2), we iterate over all possible combinations of j1 and j2.
• Auxiliary Space: The space complexity of the given solution is O(N³) as well. This is because we use a 3D array memo to store the calculated values for each state (i, j1, j2), resulting in a space requirement of O(N³).