K Turns Allowed — Asked in Amazon Interview

Problem Statement :

Ninja has been given the dimensions of a matrix, count the number of paths to reach the bottom right from top left with maximum k turns allowed.

Each test case contains three space-separated integers ’N’, ’M’, and ‘K’ denoting the number of rows, columns, and maximum turn around respectively.

A valid turn :

There are two possible scenarios when a turn can occur at point (i, j):

Turns Right: (i — 1, j) -> (i, j) -> (i, j + 1)

Turns Down: (i, j-1) -> (i, j) -> (i+1, j)

Input:

3 3 2

Output:

4

Explanation of test case:

We can reach the right bottom point through the following ways:

0 turns -> 0 ways

1 turn -> 2 ways

2 turns -> 2 ways

Hence our answer shall be 4

Approach :

Dynamic Programming Approach

In our brute force approach, we can add memorizations and improve the time complexity. We can declare a global matrix having 4 dimensions as the 4 parameters of our recursive function. Now, in this approach, when we reach a certain cell, we will check whether the output for that cell is present in the DP table or not. If the output is present for that cell, we will return that without computing for that cell again, otherwise we will compute for the cell and store the result in the DP table for further use.

• Here, DP(‘i’,’j’,’k’,1) represents we are currently on the node ( ‘i’, ’j’) with ‘k’ turns remaining and the direction is downward movement. Similarly, for DP( ‘i’, ’j’, ’k’, 0), it represents we are currently on the node ( ‘i’, ’j’) with ‘k’ turns remaining and the direction is rightward movement.

Our transitions are as follows:

• During a right turn, from (‘ i’ — 1, ‘j’) -> ( ‘i’, ‘j’) -> ( ‘i’, ‘j’ + 1), our DP table change from DP( ‘i’ — 1, ’j’, ’k’, 1) to DP( ‘i’, ’j’, ’k’, 1) to DP( ‘i’, ’j’ + 1, ’k’ — 1, 0) indicating a right turn.
• During a left turn, from ( ‘i’, ‘j’ — 1) -> ( ‘i’, ‘j’) -> ( ‘i’ + 1, ‘j’), our DP table change from DP( ‘i’, ’j’ — 1, ’k’, 0) to DP( ‘i’, ’j’, ’k’, 1) to DP( ‘i’ + 1, ’j’, ’k’ — 1, 1) indicating a right turn.

Algorithm:

• Declare a global matrix having 4 dimensions representing a number of rows and column, ‘k-th’ turn possible from the current index and current direction of movement.
• From the main function, call the recursive function ‘countPath’ for the adjacent cells as countPath( ’N’ — 2, ‘M’ — 1, ‘K’, 1) and countPath( ’N’ — 1, ‘M’ — 2, ‘K’, 0), sum them up and return to the main function.
• In our recursive function, we have 4 parameters that are the same as the dimension of the matrix.
• If our current row index and column index becomes invalid, we can return 0 as a failure.
• If we reach the final bottom right point, we will return 1 as success.
• If ‘K’ is equal to zero indicating no further turns:
• If we are in the last row and our current direction is 0, then we can return 1 as a success
• If we are in the last column and our current direction is 1, then we can return 1 as a success
• Otherwise, we can return zero as a failure.
• If the current location is already computed, we shall pick up the value from the DP table and return it.
• If our current direction is 0,
• Update the DP table with the summation of ‘countPath( ‘i’, ‘j’ — 1, ‘k’, ‘d’)’ + ‘countPath( ‘i’ — 1, ‘j’, ‘k’ — 1, ‘d’ ^ 1)’ and return to the parent function.
• Otherwise, our current direction is 1,
• Update the DP table with the summation of ‘countPath( ‘i’ — 1, ‘j’, ‘k’, ‘d’)’ + ‘countPath( ‘i’, ‘j’ — 1, ‘k’ — 1, ‘d’ ^ 1)’ and return to the parent function.

Time Complexity: O(N * M * K)
Space Complexity: O(N * M * K)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.