JUN3 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Hemanth Kumar
Tester: Hrushikesh Koyadala
Editorialist: Hemanth Kumar

DIFFICULTY:

HARD

PREREQUISITES:

Breadth First Search, Depth First Search

PROBLEM:

Given a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell. Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

QUICK EXPLANATION:

This problem is a variation of the classic BFS problem. We also have to keep track of the number of obstacles that can still be removed while traversing. Therefore, while traversing, we have to keep track of current position, number of obstacles removable, number of steps taken.

EXPLANATION:

In the BFS problem, we take a node and find all its neighbors and append the ones we haven’t visited yet to a queue. Then we pop the front of the queue and repeat the process till the target node is reached.

In this problem, we have an additional parameter k. Therefore, we traverse the graph like we do in BFS, but at each point, we track the value of k as well. If we want to move onto a position with an obstacle on it, we decrement the value of k and move to it. This process repeats until we reach the target destination, or we have no more moves available with the given k, at which point, we return -1.

SOLUTIONS:

Setter's Solution
def solution(grid, k):
    visited = set()
    queue = []
    
    #If grid is of size 1x1
    if len(grid)==1 and len(grid[0])==1:
        return 0
    
    #Helper function to return the neighbours of the given position
    def neighbours(x, y):
        n = []
        if x > 0:
            n.append((x-1, y))
        if y > 0:
            n.append((x, y-1))
        if x < len(grid)-1:
            n.append((x+1, y))
        if y < len(grid[0])-1:
            n.append((x, y+1))
        return n
    
    #We append values of the form (x, y, k_remaining, steps_taken)
    queue.append((0, 0, k, 0))

    #We monitor values of the form (x, y, k_remaining) to ensure we don't return to a position with same k
    visited.add((0, 0, k))
    while len(queue) > 0:
        (curr_x, curr_y, curr_k, curr_steps) = queue.pop()
        for x, y in neighbours(curr_x, curr_y):
            if (x, y, curr_k) not in visited:
                visited.add((x, y, curr_k))
                if x == len(grid)-1 and y == len(grid[0])-1:
                    return curr_steps + 1
                if grid[x][y] == 1 and curr_k > 0:
                    queue.append((x, y, curr_k-1, curr_steps+1))
                if grid[x][y] == 0:
                    queue.append((x, y, curr_k, curr_steps+1))
    return -1

TIME COMPLEXITY

In the worst case, every node (position) in the above graph is visited atmost k times (one for each value of [0,k]). Therefore, for m*n nodes each visited k times, the time complexity is O(m*n*k).