Optimizing Grid Paths With Minimal Obstacle Removal
BFS solution for minimum obstacles: TC:O(n*mlog(n*m)), SC:O(n*m). Dijkstra's algorithm used with priority queue to find shortest path.
TC:O(n*mlog(n*m))
SC :O(n*m)
Problem
//BFS : dijkstra's
class Solution {
public int minimumObstacles(int[][] grid) {
int minObstacleRemoved = Integer.MAX_VALUE;
Queue<Cell> q = new PriorityQueue<>((a,b)-> Integer.compare(a.c,b.c));
int visited[][] = new int[grid.length][grid[0].length];
q.add(new Cell(0,0,0));
while(!q.isEmpty()){
Cell cell = q.remove();
int I = cell.i;
int J = cell.j;
if(visited[I][J] ==1) continue;
visited[I][J] = 1;
if(I == grid.length-1 && J == grid[0].len...