#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/meta-interview-prep-v2/coding-patterns-ii-trees-graphs-advanced/lc-463-island-perimeter-example-and-complexity-analysis

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/meta-interview-prep-v2/coding-patterns-ii-trees-graphs-advanced/lc-463-island-perimeter-example-and-complexity-analysis

Repovive

LeetCode 463 Island Perimeter - Example and Complexity Analysis - Coding Patterns II: Trees, Graphs & Advanced | Meta Interview Prep | Repovive

Repovive.

Meta Interview Prep6 sections · 147 units8h total

Open in Course

LeetCode 463 Island Perimeter - Example and Complexity Analysis

Worked example

Let's trace a small grid:

1 1
1 0

Cell (0,0): $4$ edges. Right neighbor is land ( $-1$ ). Bottom neighbor is land ( $-1$ ). Contribution: $2$ .

Cell (0,1): $4$ edges. Left neighbor is land ( $-1$ ). Contribution: $3$ .

Cell (1,0): $4$ edges. Top neighbor is land ( $-1$ ). Contribution: $3$ .

Total perimeter: $2 + 3 + 3 = 8$ .

You check each cell and up to $4$ neighbors per cell. That's $O(m \times n)$ time, $O(1)$ space.