Island Perimeter | 3 Approaches | Google | Leetcode 463 | codestorywithMIK
275Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 90th Video of our Playlist "Array 1D/2D : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good 2D Array problem : Island Perimeter | 3 Approaches | Google | Leetcode 463 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Island Perimeter | 3 Approaches | Google | Leetcode 463 | codestorywithMIK
Company Tags : GOOGLE
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Island%20Perimeter.cpp
Leetcode Link : https://leetcode.com/problems/island-perimeter/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Approach Summary :
Here's a short summary of each approach:
**Approach-1 (DFS):**
- Time Complexity: O(m*n)
- Space Complexity: O(1) Auxiliary Space
- Description: This approach utilizes Depth-First Search (DFS) to traverse the grid. It starts from a cell containing land (value 1) and explores its adjacent cells recursively, marking visited cells to avoid revisiting. It increments the perimeter count when encountering boundary cells or water cells. This approach uses minimal auxiliary space as it only modifies the input grid without any additional data structures.
**Approach-2 (BFS):**
- Time Complexity: O(m*n)
- Space Complexity: O(m*n)
- Description: This approach employs Breadth-First Search (BFS) to traverse the grid. It starts from a cell containing land (value 1) and explores its adjacent cells layer by layer, maintaining a queue of cells to visit. Similar to DFS, it marks visited cells and increments the perimeter count when encountering boundary cells or water cells. This approach uses additional space to store the queue for BFS traversal.
**Approach-3 (Iterative):**
- Time Complexity: O(m*n)
- Space Complexity: O(1)
- Description: This approach iterates through each cell of the grid. For each land cell (value 1), it checks its adjacent cells (up, down, left, right) to determine the perimeter. If an adjacent cell is out of bounds or contains water (value 0), it increments the perimeter count. This approach does not require additional data structures beyond the input grid and uses constant space.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
3:09 - Approach-1
17:27 - Coding Approach-1
21:57 - Approach-2
28:24 - Coding Approach-2
34:50 - Approach-3
42:41 - Coding Approach-3
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024