From Treasure Maps to Tech: Understanding Multi-Source Pathfinding | Islands and Treasures | Grid Algorithms

Let's first understand why is this question and it's solution significant to us:

The Why??

1. Algorithmic Pattern Recognition
2. It's a gateway to understanding Dijkstra's algorithm and other pathfinding algorithms
3. Introduces the concept of distance matrices which is crucial for problems like:
4. Finding nearest exit in a maze
5. Calculating minimum service area coverage
6. Optimising warehouse placement
7. Finding escape routes in emergency scenarios
8. Architectural Design: The problem teaches important system design patterns:
9. How to handle multiple sources of truth (multiple treasures)
10. Propagating information across a network (distance values)
11. Dealing with barriers and constraints (-1 cells)
12. Optimizing for shortest paths vs any valid path
13. Practical Applications
14. Amazon's warehouse robot navigation systems use similar algorithms
15. Google Maps uses related concepts for showing multiple nearby restaurants/services
16. City planning tools use similar algorithms for:
17. Emergency service coverage
18. Public transport accessibility
19. Retail location optimisation
20. Technical Growth : Forces you to think about:
21. Why BFS guarantees shortest path while DFS doesn't
22. How to optimize memory usage with queue/stack
23. When to use iterative vs recursive approaches
24. How to handle state updates without corrupting data
25. Understanding time-space tradeoffs
26. Problem-Solving Framework: Teaches a systematic approach:
27. Breaking down complex requirements
28. Identifying base cases
29. Managing multiple starting conditions
30. Handling edge cases
31. Optimizing initial solutions

The Neetcode problem:

 You are given a m×n

m×n 2D grid initialised with these three possible values:

-1  : A water cell that can not be traversed.
 0  : A treasure chest.
INF : A land cell that can be traversed. 

We use the integer 2^31 - 1 = 2147483647 to represent INF.

Fill each land cell with the distance to its nearest treasure chest. If a land cell cannot reach a treasure chest than the value should remain INF.

Assume the grid can only be traversed up, down, left, or right.

Modify the grid in-place.

Example 1:

Input: [
  [2147483647,-1,0,2147483647],
  [2147483647,2147483647,2147483647,-1],
  [2147483647,-1,2147483647,-1],
  [0,-1,2147483647,2147483647]
]

Output: [
  [3,-1,0,1],
  [2,2,1,-1],
  [1,-1,2,-1],
  [0,-1,3,4]
]

Example 2:

Input: [
  [0,-1],
  [2147483647,2147483647]
]

Output: [
  [0,-1],
  [1,2]
]

Here we need to find how much distant it is from the current location to the nearset treasure chest. If a land cell cannot reach a treasure chest than the value should remain INF as originally supplied in the grid.

This is our input grid, where we are supplied 2D array with

-1  : A water cell that can not be traversed.
 0  : A treasure chest.
INF : A land cell that can be traversed. 

Visualising

Let's start brainstorming & how we would approach it:

1. We start from [0, 0] i.e top left position, we start some sort of traversal looking for the gold chest
2. Or we first discover where the gold chest lies, then we start our explaration filling up the 2D array, every time we expand in outward direction, we increase the distance by 1.

[
 [INF, -1, 0, INF],
 [INF, INF, INF, -1],
 [INF, -1, INF, -1],
 [0,  -1, INF, INF]
]

TO me the 2nd approach sounds clean and better.

[
 [INF,   -1,    0,     *],    
 [INF,   INF,  INF,   -1],
 [*,     -1,   INF,   -1],   
 [0,     -1,   INF,   INF]
]

Initial State , Starting from both treasure chests (0):

[
 [INF,   -1,    0,     *],   
 [INF,   INF,  INF,   -1],
 [*,     -1,   INF,   -1],   
 [0,     -1,   INF,   INF]
]

• Step 1 (Fill in distance 1):

[
 [INF,   -1,    0,     1],    # Right from top 0
 [*,     INF,   *,    -1],    # * marks cells we're checking
 [1,     -1,   INF,   -1],    # Up from bottom 0
 [0,     -1,   INF,   INF]
]

• Step 2 (Fill in distance 2):

Copy
[
 [INF,   -1,    0,     1],
 [2,     INF,   1,    -1],    # Cells filled with distance 2
 [1,     -1,    *,    -1],    # * marks cells we're checking
 [0,     -1,   INF,   INF]
]

• Step 3 (Fill in distance 3):

[
 [3,     -1,    0,     1],    # Distance 3 filled
 [2,     2,     1,    -1],    # Distance 2 filled from step 2
 [1,     -1,    2,    -1],    # Distance 2 filled from step 2
 [0,     -1,    *,     *]     # * marks cells we're checking
]

Final State (Fill in distance 4):

[
 [3,     -1,    0,     1],
 [2,     2,     1,    -1],
 [1,     -1,    2,    -1],
 [0,     -1,    3,     4]     # Last cells filled
]

Each step:

1. We expand from current cells
2. Update reachable neighbour's with current_distance + 1
3. Can't go through water (-1)
4. Numbers represent shortest path to any treasure (0)

class Solution {
    /**
     * @param {number[][]} grid
     */
    constructor() {
        this.distances = [
            [-1, 0],
            [0, 1],
            [1, 0],
            [0, -1]
        ]
    }

islandsAndTreasure(grid) {
 for (let i = 0; i < grid.length; i++) {
  for (let j = 0; j < grid[0].length; j++) {
     if (grid[i][j] === 0) {
        this.dfs(grid, i, j, 0)
      }
   }
  }
 return grid
}

inBound(value, max) {
 return -1 < value && value < max
}

dfs(grid, row, col, currentDistance) {

  if (!this.inBound(row, grid.length)
  || !this.inBound(col, grid[0].length)
  || grid[row][col] === -1) {
   return 0
  }

  if (grid[row][col] < currentDistance  ) {
     return null
   }
   grid[row][col] = currentDistance
   for (let [dirRow, dirCol] of this.distances) {
     const newRow = dirRow + row
     const newCol = dirCol + col
     this.dfs(grid, newRow, newCol, currentDistance + 1)
     }
  }
}

problem of finding the shorter distance

Can be further OPTIMISED USING BFS

BFS is Better Than DFS for This Problem

1. Problem Requirements: Shortest Path

Th problem requires finding the shortest distance from each cell to the nearest treasure (0).

1. BF is inherently designed for finding the shortest path in unweighted graphs (or grids) because it explores all nodes level by level.
2. DFS, on the other hand, explores one path deeply before backtracking. It does not guarantee the shortest path unless you add additional logic (pruning).

2. Redundant Updates in DFS

InDFS, you might revisit the same cell multiple times through different paths. Each time you revisit a cell, you might update its distance, even if a shorter distance has already been found.

Thi leads to redundant updates and inefficiency.

In BFS, each cell is visited only once, and its distance is updated with the shortest possible value immediately.

3. Performance

1. BF has a time complexity of O(M * N), where M is the number of rows and N is the number of columns. This is optimal for this problem.
2. DF can have a much higher time complexity because it may revisit cells multiple times and explore unnecessary paths.

4. Stack Overflow in DFS

DF uses recursion, which relies on the call stack. For large grids, the recursion depth can become very large, leading to a stack overflow.

BF uses a queue, which is not limited by stack size and is more suitable for large grids.

islandsAndTreasure(grid) {
 const rows = grid.length;
 if (rows === 0) return grid;
 const cols = grid[0].length;

 // Initialize the queue with all treasure positions (0s)
 const queue = [];
 for (let i = 0; i < rows; i++) {
   for (let j = 0; j < cols; j++) {
     if (grid[i][j] === 0) {
       queue.push([i, j]);
      }
    }
  }

// Perform BFS
this.bfs(grid, queue);
return grid;
}

bfs(grid,  queue) {

 while (0 < queue.length) {
   const [row, col] = queue.shift()
   let currentDistance = grid[row][col];

   for (let [dirRow, dirCol] of this.distances) {
    const newRow = row + dirRow
    const newCol = col + dirCol

    if (this.inBound(newRow, grid.length)
        && this.inBound(newCol, grid[0].length)
        && grid[newRow][newCol] === 2147483647) {

          grid[newRow][newCol] = currentDistance + 1;
          queue.push([newRow, newCol])
     }
    }
  }
}

point to be noted: when we run sequencial traversing we already have all the position where we can find gold.

#DataStructures #leetcode #Graph #Traversal