LeetCode Entry

1765. Map of Highest Peak

22.01.2025 medium 2025 kotlin rust

Make growing landscape

1765. Map of Highest Peak medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/872

Problem TLDR

Make growing landscape #medium #bfs

Intuition

Do BFS from initial points

Approach

• next height is always curr + 1
• mark vacant places with -1 to solve 0 edge case
• fill the place when its added to the queue

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun highestPeak(isWater: Array<IntArray>) = isWater.apply {
        val q = ArrayDeque<Pair<Int, Int>>(); var d = listOf(-1, 0, 1, 0, -1)
        for ((y, r) in withIndex()) for (x in r.indices)
            if (r[x] > 0) { r[x] = 0; q += y to x } else r[x] = -1
        while (q.size > 0) {
            val (y, x) = q.removeFirst()
            for (i in 0..3) {
                val (y1, x1) = y + d[i] to x + d[i + 1]
                if (getOrNull(y1)?.getOrNull(x1) ?: 0 < 0) {
                    this[y1][x1] = 1 + this[y][x]
                    q += y1 to x1
                }
            }
        }
    }

    pub fn highest_peak(mut is_water: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut q = VecDeque::new();
        for y in 0..is_water.len() { for x in 0..is_water[0].len() {
            if is_water[y][x] > 0 { is_water[y][x] = 0; q.push_back((y, x)) }
            else { is_water[y][x] = -1 }
        }}
        while let Some((y, x)) = q.pop_front() {
            for (y1, x1) in [(y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)] {
                if (y1.min(x1) >= 0 && y1 < is_water.len() && x1 < is_water[0].len()) {
                    if is_water[y1][x1] >= 0 { continue }
                    is_water[y1][x1] = 1 + is_water[y][x];
                    q.push_back((y1, x1))
                }
            }
        }; is_water
    }

    vector<vector<int>> highestPeak(vector<vector<int>>& w) {
        queue<pair<int, int>> q;
        int d[] = {1, 0, -1, 0, 1}, m = size(w), n = size(w[0]);
        for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j)
            if (w[i][j]) w[i][j] = 0, q.push({i, j}); else w[i][j] = -1;
        while (size(q)) {
            auto [y, x] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i)
                if (int y1 = y + d[i], x1 = x + d[i + 1];
                    min(y1, x1) >= 0 && y1 < m && x1 < n && w[y1][x1] < 0)
                    w[y1][x1] = 1 + w[y][x], q.push({y1, x1});
        } return w;
    }