Find Efficient way

Hi, Folks! Today I solved three problems on LeetCode : Unique Paths, Spiral matrix, and N-Queens. Let’s walk through these problems.

Unique paths problem

We are given two numbers, representing number of rows and number of columns. Our task is to find the total number of unique paths to reach the position (m-1,n-1) from (0,0). To solve this problem, we can follow recursive approach. We can start from (0,0) recursively find steps to travel right and bottom until we reach the required position. To find total unique paths, we would add the right steps to bottom steps and return it. However, there is a small issue with this approach: the solutions may repeat number of times. To overcome this, the alternative approach is to use DP matrix. We create a DP matrix with same number of rows and columns as input and we initialize all positions of DP matrix with 1. Finally, we return the value in the lats cell of DP matrix as total number off unique paths.

Spiral Matrix

We are given with a matrix and we have to return a list containing the elements of matrix in spiral order. To solve this problem, we can use indexing limits as conditions to run a loop. We traverse from left to right of matrix we can use one for loop. Then, we move from the top-right corner to the bottom-right corner with another loop. We traverse from the bottom-right corner to the bottom-left corner using a third loop. Finally, we move from the bottom-left corner to the top-left corner with a fourth loop. In this way, we use four different loops to traverse in all four directions, controlling them with indexing limits.

N-Queens

We are given with a input number n, we have to find the number of ways to place n queens in nxn matrix such that no two queens will attack each other. This means no two queens should be in same row, column, or diagonal. To solve this problem, we can use recursion and backtracking concepts. We can first perform recursion to repeat the process multiple times. because, we need to find all the possible ways to place queens. Backtracking is performed when we did not find the correct position to place queen then we can replace ‘Q’ with ‘.’ and repeat the process for the next position.

We can optimize the above solution by using three lists. One lists is to keep track of number of rows. lets say we have n rows we will place n zeros in the list and replace the respective zero by one if that specific row is having queen. This will avoid unnecessary backtracking. Similarly, the second list is for lower diagonal, and third list is for upper diagonal. Both diagonal lists have 2n-1 elements all initially set to zeros. As we traverse through the matrix to place queens, we update the respective row or diagonal list by replacing 0 with 1 when queen is placed. This indicates that no more queens can be placed in that respective diagonal or row. In this way, this approach works efficiently.

I hope my experience will be helpful.

The above is the detailed content of Find Efficient way. For more information, please follow other related articles on the PHP Chinese website!