Solve Leetcode Problems and Get Offers From Your Dream Companies|Max Area of Island
Tags: career, programming, algorithms, computerscience
Published: 2021-02-15 19:08:12

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.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/whjro63ir1mlvuozgpxn.jpg)
## Motivation to Learn Algorithms
{% gist https://gist.github.com/sksaikia/b3e44a32bab220f3773ca25ba9b9adf2.js %}

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](https://leetcode.com/discuss/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](https://leetcode.com/nilmadhab/)
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

{% youtube iO9Y8zDqwaQ %}

## 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)](https://www.javatpoint.com/breadth-first-search-algorithm)

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.
{% gist https://gist.github.com/sksaikia/65faf8ae06cbbf51edb543a0ee292b95.js %}
The Java code for this problem is given below.
{% gist https://gist.github.com/sksaikia/38842f720b77b2dc8e30758802427fa4.js %}
This problem can be solved with DFS too. All the code can be found in the following GitHub repo.
{% github webtutsplus/Leetcode %}
**Thank You for reading and Follow this publication for more Leetcode Solutions!😃**