LeetCode Entry

463. Island Perimeter

18.04.2024 easy 2024 kotlin rust

Perimeter of 1's islands in 01-matrix

463. Island Perimeter easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/575

Problem TLDR

Perimeter of 1’s islands in 01-matrix #easy

Intuition

Let’s observe the problem example: As we see, the perimeter increases on the 0-1 transitions, we can just count them. Another neat approach I steal from someone: every 1 increases by 4 and then decreases by 1-1 borders.

Approach

Let’s try to save some keystrokes

• did you know compareTo(false) will convert Boolean to Int? (same is as i32 in Rust)

Complexity

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

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

Code

    fun islandPerimeter(grid: Array<IntArray>) =
        (0..<grid.size * grid[0].size).sumBy { xy ->
            val x = xy % grid[0].size; val y = xy / grid[0].size
            if (grid[y][x] < 1) 0 else
            (x < 1 || grid[y][x - 1] < 1).compareTo(false) +
            (y < 1 || grid[y - 1][x] < 1).compareTo(false) +
            (x == grid[0].lastIndex || grid[y][x + 1] < 1).compareTo(false) +
            (y == grid.lastIndex || grid[y + 1][x] < 1).compareTo(false)
        }

    pub fn island_perimeter(grid: Vec<Vec<i32>>) -> i32 {
        let mut p = 0;
        for y in 0..grid.len() { for x in 0..grid[0].len() {
            if grid[y][x] < 1 { continue }
            if y > 0 && grid[y - 1][x] > 0 { p -= 2 }
            if x > 0 && grid[y][x - 1] > 0 { p -= 2 }
            p += 4
        } }; p
    }