Minimum Obstacle Removal to Reach Corner

Leetcode Problem:

• Minimum Obstacle Removal to Reach Corner

Summary

• This solution solves the Minimum Obstacles to Remove problem where we need to find the minimum number of obstacles to remove from a 2D grid so we can move from the upper left corner to the lower right corner.

Approach

• This solution uses a priority queue to keep track of the cells to visit
• It uses a heap data structure to efficiently select the cell with the minimum number of obstacles to remove
• It also uses a visited matrix to keep track of the cells that have been visited to avoid revisiting them.

Complexity

• O(m * n * log(m * n))

Explanation

• The solution first initializes a visited matrix and a priority queue
• It then starts by pushing the starting cell into the priority queue
• The priority queue is implemented as a binary heap
• The solution then enters a loop where it pops the cell with the minimum number of obstacles to remove from the priority queue and checks its neighbors
• If a neighbor is an obstacle, it pushes the neighbor into the priority queue with an increased number of obstacles to remove
• If a neighbor is not an obstacle, it pushes the neighbor into the priority queue with the same number of obstacles to remove
• The solution continues this process until it reaches the destination cell or until all reachable cells have been visited
• The time complexity of this solution is O(m * n * log(m * n)) because the priority queue operations (push and pop) take O(log(m * n)) time and we perform these operations m * n times.

Solution Code:

struct _node{
    int r;
    int c;
    int moveCnt;
    int removeCnt;
};
struct _heap{
    int size;
    _node arr[1000001];
    _heap(){
        size = 1;
    }
    bool _cmp(_node a, _node b){
        if(a.removeCnt != b.removeCnt){
            return a.removeCnt < b.removeCnt;
        }
        return a.moveCnt < b.moveCnt;

    }
    void push(_node a){
        arr[size++] = a;
        int idx = size -1;
        while(idx > 1 && _cmp(arr[idx], arr[idx/2])){
            _node tmp = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = tmp;
            idx /= 2;
        }
    }
    _node pop(){
        _node ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if (j >= size){
                break;
            }
            if((j + 1) < size && _cmp(arr[j+1], arr[j])){
                j++;
            }
            if(_cmp(arr[j], arr[i])){
                _node t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else {
                break;
            }
        }

        return ret;

    }
    bool empty(){
        return size == 1;
    }
};
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};

class Solution {
public:
    _heap que;
    int minimumObstacles(vector>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int **visited = new int*[m];
        for(int i = 0 ; i < m; i++){
            visited[i] = new int[n];
            for(int j = 0 ; j < n ;j++){
                visited[i][j] = 1234567890;
            }
        }
        visited[0][0]= 0;
        que.push({0, 0, 0, 0});
        while(!que.empty()){
            _node nod = que.pop();
            if(nod.r == m - 1 && nod.c == n - 1){
                return nod.removeCnt;
            }
            for(int i = 0 ; i< 4; i++){
                int nr = nod.r + dy[i];
                int nc = nod.c + dx[i];
                if(nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc] <= nod.moveCnt+1){
                    continue;
                }
                visited[nr][nc] = nod.moveCnt+1;
                if(grid[nr][nc] == 0){
                    que.push({nr, nc, nod.moveCnt+1, nod.removeCnt});
                } else {
                    que.push({nr, nc, nod.moveCnt+1, nod.removeCnt + 1});
                }
            }
        }

        return -1;
    }
};