SDE - 1

Step 1: Initialize an empty array or list to store the paths.

Step 2: Define a recursive function, let's call it "findPaths," that takes the current position of the rat (row and column), the size of the matrix (n), and the current path string as parameters.

Step 3: In the "findPaths" function, first, check if the rat has reached the destination (i.e. if the current position is (n-1, n-1)). If it has reached the destination, add the current path string to the array of paths and return.

Step 4: Next, check if the rat is within the boundaries of the matrix and if the cell it is currently on is not blocked (you may have some blocked cells that the rat cannot pass through). If these conditions are met, proceed with the recursive calls for all possible directions (up, down, left, and right).

Step 5: For each direction, update the current position of the rat accordingly, and append the corresponding direction character (U, D, L, or R) to the current path string.

Step 6: Make recursive calls to the "findPaths" function for each direction with the updated position and path string.

Step 7: After all recursive calls are completed, backtrack by removing the last direction character from the current path string. This step is essential for backtracking to explore all possible paths.

Step 8: Once the recursive function finishes execution, the array of paths will contain all possible paths from (0, 0) to (n-1, n-1) in the matrix.

Step 9: Return the array of paths as the final output.

Step 1: Create a Min Heap (Priority Queue) data structure. A Min Heap is a binary heap where the value of each node is greater than or equal to the values of its children. In Python, you can use the heapq module to implement a Priority Queue.

Step 2: Traverse through the array and add the first K elements to the Priority Queue.

Step 3: For the remaining elements in the array (i.e., from index K to N-1), compare the current element with the root of the Priority Queue (which is the smallest element in the heap).

Step 4: If the current element is smaller than the root, remove the root element from the Priority Queue, and insert the current element.

Step 5: After traversing through the entire array, the Kth smallest element will be the root of the Priority Queue.

Step 6: Return the root element of the Priority Queue as the Kth smallest element.