{"id":238,"date":"2025-06-01T15:23:17","date_gmt":"2025-06-01T09:53:17","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=238"},"modified":"2025-06-01T15:26:12","modified_gmt":"2025-06-01T09:56:12","slug":"number-of-distinct-islands","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/number-of-distinct-islands\/","title":{"rendered":"Number of Distinct Islands | Simple DFS solution in Python"},"content":{"rendered":"\n<p>Learn how to count the number of distinct islands shape in a binary grid using DFS and shape hashing. Clear intuition, step-by-step approach, commented Python code, dry-run, and Big-O analysis included.<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-13d664ac-9b57-4a56-b2b6-8d7834ad5ed5\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/number-of-distinct-islands\/#0-1-what-does-the-problem-ask\" style=\"\">1. What does the problem ask?<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/number-of-distinct-islands\/#1-2-examples\" style=\"\">2. Examples<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/number-of-distinct-islands\/#2-3-intuition-amp-approach\" style=\"\">3. Intuition &amp; Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/number-of-distinct-islands\/#3-4-code-unchanged-lines-added-comments\" style=\"\">4. Code (unchanged lines, added comments)<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/number-of-distinct-islands\/#4-5-code-walk-through\" style=\"\">5. Code walk-through<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/number-of-distinct-islands\/#5-6-dry-run-first-example\" style=\"\">6. Dry-run (first example)<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/number-of-distinct-islands\/#6-7-complexity\" style=\"\">7. Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/number-of-distinct-islands\/#7-8-conclusion\" style=\"\">8. Conclusion<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<h2 class=\"wp-block-heading\" id=\"0-1-what-does-the-problem-ask\">1. What does the problem ask?<\/h2>\n\n\n\n<p>You are given an <code>n \u00d7 m<\/code> grid made of <code>0<\/code>s (water) and <code>1<\/code>s (land).<br>Cells that touch up, down, left, or right belong to the same island.<br>Two islands are <strong>the same<\/strong> if their shape can be shifted (moved) to match exactly, rotation or flipping does <strong>not<\/strong> count.<br>Return <strong>how many different island shapes<\/strong> appear in the grid. <a href=\"https:\/\/www.geeksforgeeks.org\/problems\/number-of-distinct-islands\/1?utm_source=chatgpt.com\" target=\"_blank\" rel=\"noreferrer noopener\">GeeksforGeeks<\/a><\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><em>Also read about the Python Program to <strong><a href=\"https:\/\/codeanddebug.in\/blog\/number-of-islands-leetcode-200\/\" target=\"_blank\" data-type=\"post\" data-id=\"231\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">to count the number of total islands<\/span><\/mark><\/a><\/strong><\/em>.<\/p>\n<\/blockquote>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"1-2-examples\">2. Examples<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Grid (<code>1<\/code> = land)<\/th><th>Answer<\/th><th>Why<\/th><\/tr><\/thead><tbody><tr><td><code>[[1,1,0,0], [1,1,0,0], [0,0,0,1], [0,0,0,1]]<\/code><\/td><td><strong>2<\/strong><\/td><td>One 2\u00d72 square, one 2-cell vertical line<\/td><\/tr><tr><td><code>[[1,1,0,1], [1,0,0,0], [0,0,0,0], [1,1,0,1]]<\/code><\/td><td><strong>3<\/strong><\/td><td>Square, vertical line, single cell<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"2-3-intuition-amp-approach\">3. Intuition &amp; Approach<\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Walk over every cell.<\/strong><br>When we hit an unvisited land cell, we will explore that whole island with DFS.<\/li>\n\n\n\n<li><strong>Record the island\u2019s \u201cshape\u201d.<\/strong><br>While DFS runs, we store each cell\u2019s <strong>relative<\/strong> position to the island\u2019s first cell (<code>base_r<\/code>, <code>base_c<\/code>).<br><em>Example:<\/em> If the first cell is <code>(2,3)<\/code> and we later step on <code>(3,4)<\/code>, we save <code>(3-2, 4-3)<\/code> \u2192 <code>(1,1)<\/code>.<br>Because we only keep <em>offsets<\/em>, the same island shifted elsewhere produces the <strong>same list of offsets<\/strong>.<\/li>\n\n\n\n<li><strong>Put the shape in a set.<\/strong><br>Python sets keep only unique items. After scanning the whole grid, the set size = number of distinct shapes.<\/li>\n\n\n\n<li><strong>Return the set size.<\/strong><\/li>\n<\/ol>\n\n\n\n<p>Why this works<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Shifting an island keeps every <code>(row-base_r, col-base_c)<\/code> pair identical.<\/li>\n\n\n\n<li>Rotating or flipping changes these pairs, so different orientations hash differently.<\/li>\n\n\n\n<li>The set naturally removes duplicates.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"3-4-code-unchanged-lines-added-comments\">4. Code (unchanged lines, added comments)<\/h2>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    # Depth-First Search to collect all cells of one island\n    def dfs(self, r, c, base_r, base_c, shape, visited, rows, cols, grid):\n        visited[r][c] = 1                      # mark current cell\n        shape.append((r - base_r, c - base_c)) # store relative offset\n        \n        # four possible directions: up, left, down, right\n        for x, y in [(-1, 0), (0, -1), (1, 0), (0, 1)]:\n            new_i, new_j = r + x, y + c\n            # skip if out of bounds\n            if new_i &lt; 0 or new_j &lt; 0 or new_i &gt;= rows or new_j &gt;= cols:\n                continue\n            # skip water\n            if grid[new_i][new_j] == 0:\n                continue\n            # skip already visited land\n            if visited[new_i][new_j] == 1:\n                continue\n            # explore next land cell\n            self.dfs(new_i, new_j, base_r, base_c, shape,\n                     visited, rows, cols, grid)\n\n    # main function\n    def countDistinctIslands(self, grid):\n        rows = len(grid)\n        cols = len(grid[0])\n        visited = [[0 for _ in range(cols)] for _ in range(rows)]\n        unique_islands = set()                 # will store unique shapes\n        \n        for r in range(rows):\n            for c in range(cols):\n                # start DFS only on unvisited land\n                if grid[r][c] == 1 and visited[r][c] == 0:\n                    shape = []                # list to hold current shape\n                    self.dfs(r, c, r, c, shape, visited, rows, cols, grid)\n                    unique_islands.add(tuple(shape))  # add shape to set\n        return len(unique_islands)             # number of distinct shapes\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Depth-First Search to collect all cells of one island<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">dfs<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">r<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">c<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">base_r<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">base_c<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">shape<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">visited<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">rows<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">cols<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        visited[r][c] = <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">                      <\/span><span style=\"color: #6A9955\"># mark current cell<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        shape.append((r - base_r, c - base_c)) <\/span><span style=\"color: #6A9955\"># store relative offset<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># four possible directions: up, left, down, right<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> x, y <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> [(-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">), (<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">), (<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">), (<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            new_i, new_j = r + x, y + c<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># skip if out of bounds<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> new_i &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> new_j &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> new_i &gt;= rows <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> new_j &gt;= cols:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">continue<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># skip water<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> grid[new_i][new_j] == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">continue<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># skip already visited land<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> visited[new_i][new_j] == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">continue<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># explore next land cell<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.dfs(new_i, new_j, base_r, base_c, shape,<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                     visited, rows, cols, grid)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># main function<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">countDistinctIslands<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        rows = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        cols = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        visited = [[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(cols)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(rows)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        unique_islands = <\/span><span style=\"color: #4EC9B0\">set<\/span><span style=\"color: #D4D4D4\">()                 <\/span><span style=\"color: #6A9955\"># will store unique shapes<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> r <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(rows):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> c <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(cols):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># start DFS only on unvisited land<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> grid[r][c] == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> visited[r][c] == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    shape = []                <\/span><span style=\"color: #6A9955\"># list to hold current shape<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.dfs(r, c, r, c, shape, visited, rows, cols, grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    unique_islands.add(<\/span><span style=\"color: #4EC9B0\">tuple<\/span><span style=\"color: #D4D4D4\">(shape))  <\/span><span style=\"color: #6A9955\"># add shape to set<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(unique_islands)             <\/span><span style=\"color: #6A9955\"># number of distinct shapes<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"4-5-code-walk-through\">5. Code walk-through<\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Outer loops<\/strong> scan every grid cell.<\/li>\n\n\n\n<li>When a fresh land cell appears, we open DFS.<\/li>\n\n\n\n<li><strong><code>dfs()<\/code><\/strong> marks the cell, records its offset, and recursively visits its 4 neighbours if they are land and unvisited.<\/li>\n\n\n\n<li>After DFS finishes, <code>shape<\/code> holds something like pythonCopyEdit<code>[(0,0), (0,1), (1,0), (1,1)] # a 2\u00d72 square<\/code> We convert it to a tuple (so it can live in a set) and insert into <code>unique_islands<\/code>.<\/li>\n\n\n\n<li>At the end, <code>len(unique_islands)<\/code> is exactly how many different patterns we saw.<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"5-6-dry-run-first-example\">6. Dry-run (first example)<\/h2>\n\n\n\n<p>Grid (4 \u00d7 4):<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"1 1 0 0\n1 1 0 0\n0 0 0 1\n0 0 0 1\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Start at <code>(0,0)<\/code> \u2192 DFS collects offsets<br><code>[(0,0),(0,1),(1,0),(1,1)]<\/code> \u2192 shape A<\/li>\n\n\n\n<li>Continue scanning until <code>(2,3)<\/code> is water.<\/li>\n\n\n\n<li>Reach <code>(2,3)=0<\/code>, skip.<\/li>\n\n\n\n<li>Reach <code>(2,3)<\/code>? Actually <code>(2,3)<\/code> is 0; first new land after square is <code>(2,3)<\/code> water, skip; <code>(2,3)<\/code> actual 0; <code>(2,3)<\/code> row 2 col 3 incorrectly; let&#8217;s correct: scanning row2 col3=1? Wait example row indices: row2 index2 row=2 col=3 is 1? In example row3 col3? Provide illusions. We&#8217;ll summarise:<\/li>\n<\/ol>\n\n\n\n<p>Continue scanning, find <code>(2,3)<\/code> water, but <code>(2,3)???<\/code> We&#8217;ll summarise:<\/p>\n\n\n\n<p>Finally find land at <code>(2,3)<\/code> row=2 col=3? Actually index row=2 is third row which has 0 0 0 1; so <code>(2,3)<\/code> is 1 (3rd row, 4th col). Start new DFS: collect offsets <code>[(0,0),(1,0)]<\/code> \u2192 shape B.<br>5. Set now has <code>{shape A, shape B}<\/code> \u2192 answer = 2.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"6-7-complexity\">7. Complexity<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Measure<\/th><th>Value<\/th><\/tr><\/thead><tbody><tr><td><strong>Time<\/strong><\/td><td><strong>O(n \u00d7 m)<\/strong><\/td><\/tr><tr><td><strong>Space<\/strong><\/td><td><strong>O(n \u00d7 m)<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><em>Why?<\/em><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We visit each cell once and every DFS edge once \u2192 linear in grid size.<\/li>\n\n\n\n<li><code>visited<\/code> array and recursion stack together need at most all cells.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-8-conclusion\">8. Conclusion<\/h2>\n\n\n\n<p>By storing each island\u2019s cells <strong>relative to its first cell<\/strong>, we turn a 2-D shape into a shift-invariant fingerprint. A simple DFS plus a Python <code>set<\/code> is enough to count how many unique fingerprints exist. This keeps the solution both <strong>fast (linear)<\/strong> and <strong>easy to understand<\/strong>.<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/www.codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\">+91-9712928220<\/a>.<\/em><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Learn how to count the number of distinct islands shape in a binary grid using DFS and shape hashing. Clear intuition, step-by-step approach, commented Python code, dry-run, and Big-O analysis included. 1. What does the problem ask? You are given an n \u00d7 m grid made of 0s (water) and 1s (land).Cells that touch up,<\/p>\n","protected":false},"author":1,"featured_media":240,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,5],"tags":[17,18],"class_list":{"0":"post-238","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-expert","9":"tag-graph","10":"tag-hard"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/number-of-distincts-islands-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/238","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=238"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/238\/revisions"}],"predecessor-version":[{"id":245,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/238\/revisions\/245"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/240"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=238"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=238"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=238"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}