Map of Highest Peak
Problem Statement
Aapko ek integer matrix
isWater
diya gaya hai jiska sizem x n
hai, jo land aur water cells ka map represent karta hai.Agar
isWater[i][j] == 0
, to cell (i, j) ek land cell hai.Agar
isWater[i][j] == 1
, to cell (i, j) ek water cell hai.
Objective:
Har cell ko aise height assign karni hai ki:
Har cell ki height non-negative ho (0 ya usse zyada).
Agar cell water cell hai, to uski height 0 honi chahiye.
Do adjacent cells ki height difference at most 1 honi chahiye (absolute difference). Adjacent cells wo hote hain jo north, east, south, ya west mein directly touch karte hain.
Aapko heights aise assign karni hain ki matrix mein maximum height maximize ho.
Output:
Ek integer matrix
height
return karo jiska sizem x n
ho, jahanheight[i][j]
cell (i, j) ki height ho. Agar multiple solutions hain, to koi bhi valid solution return kiya ja sakta hai.Example 1:
Input:
isWater = [[0, 1], [0, 0]]
Output:[[1, 0], [2, 1]]
Explanation: Assigned heights image mein dikhay gaye hain:
Blue cell water cell hai aur green cells land cells hain.
Har cell ka height rules ko follow karta hai aur maximum height maximize hoti hai.
Example 2:
Input:
isWater = [[0, 0, 1], [1, 0, 0], [0, 0, 0]]
Output:[[1, 1, 0], [0, 1, 1], [1, 2, 2]]
Explanation: Is solution mein maximum height 2 possible hai jo ki rules ko follow karta hai. Koi bhi height assignment jisme maximum height 2 ho aur rules ko follow karta ho, wo valid hai.
Constraints:
m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j] 0 ya 1 hota hai
Map of Highest Peak
Hume cells ko grid mein heights assign karna hai jahan water cells ka height 0 hota hai aur land cells ka positive heights hota hai.
Har land cell ki height uski nearest water cell se minimum distance honi chahiye.
Key Idea: Yeh problem Breadth-First Search (BFS) approach ko use karne ka suggestion deti hai, jahaan hum saare water cells se ek saath start karte hain.Intuition
Matrix Initialization:
Pehle, ek new matrix initialize karte hain jo input matrix isWater jaise same dimensions ka hota hai.
Saare water cells ko 0 set karte hain aur land cells ko -1 (unvisited) set karte hain.
Queue Creation:
Ek queue banate hain aur saare water cell coordinates ko us queue mein add karte hain. Matlab, saare water cells ko BFS traversal ke liye ready karte hain.
Perform BFS:
Queue se cells nikalke unka processing start karte hain:
Har cell ke adjacent 4 cells (north, east, south, west) ko check karte hain.
Agar adjacent cell within bounds hai aur ab tak visited nahi hai (height -1 hai):
Uska height current cell ke height +1 set karte hain.
Un newly visited cells ko queue mein add karte hain.
Continue Until Queue is Empty:
Yeh process tab tak continue karte hain jab tak queue empty nahi ho jata.
Queue empty hone ka matlab hai sab cells ko height assign ho chuki hai.Approach
Time Complexity: O(m * n)
Is problem mein, hum matrix ke har cell ko (water aur land cells) ek baar process karte hain.
Breadth-First Search (BFS) traversal mein har cell ko queue mein add karte hain aur phir adjacent cells ko check karte hain.
Yeh process jab tak chalu rehti hain jab tak queue empty nahi ho jati, jo har case mein matrix ke m × n cells ke liye hota hai.
Isliye, overall time complexity O(m * n) hoti hai kyunki hum m rows aur n columns ke sabhi cells ko process kar rahe hain.
Space Complexity: O(m * n)
Space complexity mein bhi har cell ke liye storage chahiye hota hai.
BFS mein queue ke liye space lagti hai jahan hum water cells aur phir land cells ko process karte hain.
Additionally, hum ek auxiliary matrix use karte hain jo input matrix ke dimensions ka hi hota hai jahan har cell ki height store hoti hai.
Isliye, overall space complexity bhi O(m * n) hoti hai kyunki hum maximum m × n cells ke liye space use kar rahe hain.
Solution
function highestPeak(isWater) {
const m = isWater.length;
const n = isWater[0].length;
// Initialize result matrix with same dimensions as input
const matrix = Array.from({ length: m }, () => Array(n).fill(-1));
// Queue to perform BFS
const queue = [];
// Initialize matrix and queue
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (isWater[i][j] === 1) {
// Water cells have height 0 and are added to queue
matrix[i][j] = 0;
queue.push([i, j]);
}
}
}
// Possible directions: right, left, down, up
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
// BFS Traverse
while (queue.length > 0) {
const [r, c] = queue.shift();
// Check all adjacent cells
for (const [dx, dy] of directions) {
const nr = r + dx;
const nc = c + dy;
// If adjacent cell is within boundary and unvisited
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] === -1) {
// Set height to 1 more than current cell
matrix[nr][nc] = matrix[r][c] + 1;
// Add to queue for further exploration
queue.push([nr, nc]);
}
}
}
return matrix;
}
Matrix Initialization:
Pehle hum ek nayi matrix banate hain jo input matrix
isWater
jaisi hi dimensions ki hoti hai. Yahan, jitne bhi cells hain sabko initially-1
(unvisited) set karte hain.
Queue Initialization:
Ek queue banate hain aur saare water cell coordinates ko is queue mein add karte hain. Water cells ka height 0 hota hai aur ye initial state mein queue mein hoti hain jisse BFS traversal start hota hai.
BFS Traversal ka Process:
Queue se har cell ko nikaalte hain aur unka processing karte hain:
Har cell ke 4 adjacent (north, east, south, west) cells ko check karte hain.
Agar adjacent cell boundary ke andar hai aur uska height ab tak
-1
(unvisited) hai:Uska height current cell ke height +1 set karte hain.
Un newly visited cells ko queue mein add karte hain for further exploration.
Continue Until Queue is Empty:
Yeh process tab tak chalta rehta hai jab tak queue khatam nahi ho jaata, iska matlab hai ki sab cells ko heights assign ho chuki hai.
Solution
#include
#include
using namespace std;
class Solution {
public:
vector> highestPeak(vector>& isWater) {
int m = isWater.size();
int n = isWater[0].size();
// Initialize result matrix with same dimensions as input
vector> matrix(m, vector(n, -1));
// Queue to perform BFS
queue> que;
// Initialize matrix and queue
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (isWater[i][j] == 1) {
// Water cells have height 0 and are added to queue
matrix[i][j] = 0;
que.push({i, j});
}
}
}
// Possible directions: right, left, down, up
vector> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// BFS Traverse
while (!que.empty()) {
auto [r, c] = que.front();
que.pop();
// Check all adjacent cells
for (auto [dx, dy] : directions) {
int nr = r + dx;
int nc = c + dy;
// If adjacent cell is within boundary and unvisited
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] == -1) {
// Set height to 1 more than current cell
matrix[nr][nc] = matrix[r][c] + 1;
// Add to queue for further exploration
que.push({nr, nc});
}
}
}
return matrix;
}
};
Matrix Initialization:
Pehle hum ek new matrix banate hain jo input
isWater
matrix ke dimensions jitni hoti hai. Jitne bhi cells hain sabko initially-1
(unvisited) set karte hain.
Queue Initialization:
Ek queue banate hain aur saare water cell coordinates ko is queue mein add karte hain. Water cells ka height 0 hota hai aur queue mein add kiya jata hai taaki trunculent BFS traversal start kiya ja sake.
BFS Traversal ka Process:
Queue se har cell ko nikalte hain aur unka adjacent cells ko check karte hain:
Jaise hi adjacent cells ko visit karte hain, agar wo boundary ke andar hain aur unvisited hain (height ab tak
-1
hai):Un cells ko current cell ke height +1 set karte hain,
Aur un visited cells ko queue mein add kar dete hain for further processing.
Continue Until Queue is Empty:
Yeh process tab tak chalta rehta hai jab tak queue empty nahi ho jata, iska matlab hai ki sab cells ko heights assign ho chuki hain.