In this series, I am going to solve Leetcode medium problems live with my friend, which you can see on our youtube channel, Today we will do Problem 695. Max Area of Island.
A little bit about me, I have offers from Uber India and Amazon India in the past, and I am currently working for Booking.com in Amsterdam.
Motivation to Learn Algorithms
I have worked in India as a software developer for 4 years. I started learning algorithms and data structure from my 3rd year in college as I was from an Electronics background. Here is my salary progression over the years, (all in INR, Lakh per year)
2016: placement in Flipkart from college, IIT KGP(18 lakh base + 2 lakh bonus = 20 lakh). But the offer was delayed by 6 months, as Flipkart was going through some trouble, so I joined Samsung.
2016: Samsung Noida(off campus ) (14 lakh base + 5 lakh joining bonus = 19 lakh). They pay to IITians 19 lakh but other colleges 9-14 lakh for the same work, which is bogus.
2017: Oyorooms (17 lakh fixed, no bonus, no stocks). I took a pay cut as I was not learning anything in Samsung, so joined Oyo.
2019: Sharechat (26 lakh fixed + 2.6lakh bonus + stock options) I joined Sharechat in Bangalore, as SDE1
2020: Offer from Amazon ( 26.5 lakh base + 18.5 lakh joining bonus= 43 lakh) in SDE2 role. They offer stocks but it is vested only 5 percent in the first year, so I ignored it.
Offer from Uber (33 lakh base + 15 lakh stock options per year (96000 USD over 4 years)+ 5 lakh joining bonus = 55 lakh per year) in SDE2 role. I think that is the top salary, you can get 3.5–4 years experience in India, but I might be wrong.
A lot of startups and established companies in India pay over 35 lakh per year for the top talent in programming, for just over 4 years of experience, like Dunzo, Dream11, Rubric, etc, check
Compensation
I rejected both offers and ended up joining Booking.com as I wanted to explore Europe. I can’t disclose my current salary.
I got so many offers because I practiced a lot of data structure and algorithms. I solved over 410 questions in Leetcode.
Nil Madhab-Leetcode Profile
Let's first talk about the Max Area of Island problem (LC 695).
Problem Statement
Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
Youtube Discussion
Solution
For solving this problem, we have to visualize the 2D matrix as a Graph. We can apply DFS or ``BFS with this problem. In this tutorial, we are going to use the BFS algorithm.
Breadth-first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes. The algorithm follows the same process for each of the nearest nodes until it finds the goal. (Source)
The lands should be connected vertically and horizontally. (not diagonally) which reduces possible paths for us to 4; UP(0,1) , DOWN (0,-1), LEFT(1,0),RIGHT(0,-1). So when we find a point which is a land, we will do a BFS on that point and we will accumulate the total points which are land and are connected to that particular point.
We will keep a visited matrix of size equal to the given grid so that we can keep track of all the visited points (so we are not stuck in an infinite loop).
We will keep another variable named max_area, which finds the answer. max_area is compared with the area for a possible island and hence maximum area is found.
The following is the well-documented python code for the problem.
The Java code for this problem is given below.
This problem can be solved with DFS too. All the code can be found in the following GitHub repo.
Thank You for reading and Follow this publication for more Leetcode Solutions!😃
Top comments (0)