Distance Of Nearest Cell
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.graphs;
/ * ============================================================================================ * PROBLEM: Distance of Nearest Cell * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given an N x M matrix A containing 0s and 1s. * For every cell (i, j), calculate the distance to the nearest cell containing a '1'. * * Distance Metric: Manhattan Distance * Formula: dist = |x1 - x2| + |y1 - y2| * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * This is a classic Shortest Path problem in an unweighted grid. While we could run * BFS from every '0' to find a '1', that would be O((NM)^2). * * Optimized Approach: Multi-Source BFS * Instead of starting from '0's, we start from all '1's simultaneously. * * 1. Initialization: * - Create a result matrix B of size N x M, initialized with -1 (or Infinity). * - Initialize a Queue for BFS. * - For every cell (i, j) where A[i][j] == 1: * - Set B[i][j] = 0 (Distance to self is 0). * - Add (i, j) to the Queue. * * 2. BFS Traversal: * - While the Queue is not empty: * - Pop the current cell (r, c). * - Explore its 4-directional neighbors (Up, Down, Left, Right). * - For each neighbor (nr, nc): * - If (nr, nc) is within bounds AND B[nr][nc] == -1: * - Set B[nr][nc] = B[r][c] + 1. * - Enqueue (nr, nc). * * 3. Termination: * - Once the queue is empty, all cells have been assigned their minimum distance. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= N, M <= 1000 * * Time Complexity: * O(N * M) - Every cell is enqueued and dequeued exactly once. * * Space Complexity: * O(N * M) - To store the result matrix B and the BFS queue. * * ============================================================================================ / public class DistanceOfNearestCell { public int[][] solve(int[][] A) { // TODO: Implement solution return new int[0][0]; } }