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
| Year | Company name | Designation | Status | Base Salary | Joining Bonus | Extras | Total CTC(INR) | Total CTC(USD) | |
|---|---|---|---|---|---|---|---|---|---|
| 2016 | Flipkart | SDE 1 | Did not join | 18 lakhs | 2 lakhs | - | 20 lakhs | 27,420 | |
| 2016 | Samsung Noida | SDE 1 | Joined | 14 lakhs | 5 lakh | - | 19 lakhs | 26,050 | |
| 2017 | Oyorooms | SDE 1 | Joined | 17 lakhs | - | - | 17 lakhs | 23,300 | |
| 2019 | Sharechat | SDE 1 | Joined | 26 lakhs | 2.6 lakhs | Stock options | 28.6 lakhs | 39,200 | |
| 2019 | Grab | SDE 1 | Did not join | 21 lakhs | 3 lakhs | - | 24 lakhs | 32,900 | |
| 2019 | Rivigo | SDE 1 | Did not join | 27 lakhs | - | 3 lakhs bonus | 30 lakhs | 41,100 | |
| 2020 | Amazon | SDE 2 | Did not join | 26.5 lakhs | 18.5 lakhs | - | 43 lakhs | 58,950 | |
| 2020 | Uber | SDE 2 | Did not join | 33 lakhs | 5 lakhs | 15 lakhs stocks | 55 lakhs | 75,400 | |
| 2020 | Booking.com | Developer | Currently working | Can't disclose | Can't disclose | Can't disclose | Can't disclose | Can't disclose |
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.
| class Solution(object): | |
| def maxAreaOfIsland(self, grid): | |
| #These are the possible directions where we can go,i.e. vertically and horizontally | |
| DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)] | |
| ROW = len(grid) | |
| # This if condition checks whether the Row is zero or not. If it is 0 then return 0. | |
| if ROW == 0: | |
| return 0 | |
| COLUMN = len(grid[0]) | |
| #This if condition checks whether the Column is zero or not. If it is 0 then return 0. | |
| if COLUMN == 0: | |
| return 0 | |
| #We create a visited matrix of size equal to the grid to keep track of visited grid locations. | |
| visited = [[False for i in range(COLUMN) ] for j in range(ROW)] | |
| #This utility method helps to find valid neighbours for a given point(x,y) i.e. finds all the possible points which can be visited from a given point(x,y) | |
| def find_valid_neighbour(x, y): | |
| valid_neighbours = [] | |
| for d in DIRECTIONS: | |
| r, c = x+ d[0], y + d[1] | |
| if r >= 0 and r < ROW and c >= 0 and c < COLUMN: | |
| valid_neighbours.append((r, c)) | |
| return valid_neighbours | |
| #This is the bfs method. When we visited a point (x,y) , it marks it as visited and adds it to the queue. Also assign the current area value to 1. | |
| #we now pop the queue and for valid neighbours , we mark them as visited and increament the area value . Also we add those elements to the queue. | |
| #We do this process until the queue is empty. | |
| def bfs(x, y, visited): | |
| queue = [(x, y)] | |
| visited[x][y] = True | |
| area = 1 | |
| while len(queue): | |
| pop = queue.pop(0) | |
| for neighbours in find_valid_neighbour(pop[0], pop[1]): | |
| r, c = neighbours | |
| if grid[r][c] == 1 and not visited[r][c]: | |
| visited[r][c] = True | |
| area += 1 | |
| queue.append((r, c)) | |
| return area | |
| #max_area value is our answer . So when we find a point with a value of 1, we do bfs for that point . The returned area is compared with | |
| #the max_area variable. After the nested for loop, we will return max_area. | |
| max_area = 0 | |
| for x in range(ROW): | |
| for y in range(COLUMN): | |
| if grid[x][y] == 1 and not visited[x][y]: | |
| area = bfs(x, y, visited) | |
| max_area = max(max_area, area) | |
| return max_area |
The Java code for this problem is given below.
| public class LC695BFS { | |
| //These are the possible directions where we can go,i.e. vertically and horizontally | |
| int[] xDir = {1,0,-1,0}; | |
| int[] yDir = {0,-1,0,1}; | |
| // maxArea variable is our answer and current is the area value the points where we are doing the BFS | |
| static int maxArea; | |
| static int current; | |
| public int maxAreaOfIsland(int[][] grid) { | |
| maxArea = 0; | |
| int row = grid.length; | |
| //This if condition checks whether the Row is zero or not. If it is 0 then return 0. | |
| if(row==0) | |
| return 0; | |
| int col = grid[0].length; | |
| //This if condition checks whether the Column is zero or not. If it is 0 then return 0. | |
| if (col==0) | |
| return 0; | |
| //We create a visited matrix of size equal to the grid to keep track of visited grid locations. | |
| boolean[][] visited = new boolean[row][col]; | |
| //Here we do a search in every possible point in the matrix. | |
| for (int i=0;i<row;i++){ | |
| for (int j=0;j<col;j++){ | |
| if (visited[i][j] == false && grid[i][j]==1){ | |
| //Here the current value is set to 1. As we have a point which is a land , so size is 1. | |
| //We do the bfs on this point and mark all the points which are connected with it . | |
| current = 1; | |
| bfs(grid,visited,i,j,row,col); | |
| //We compare it to the maxArea value . | |
| maxArea = Math.max(maxArea,current); | |
| } | |
| } | |
| } | |
| return maxArea; | |
| } | |
| //This is the main logic of the problem . We add a given point x and y to the queue. | |
| //We do bfs until the queue is empty. | |
| private void bfs(int[][] grid, boolean[][] visited, int x, int y, int row, int col) { | |
| Queue<Node> queue = new LinkedList<>(); | |
| queue.add(new Node(x,y)); | |
| visited[x][y] = true; | |
| //We have added the point into the queue and also marked that point as visited so that we don't fall into a infinite loop. | |
| while (!queue.isEmpty()){ | |
| //We keep running this loop until the queue is empty. | |
| Node curr = queue.poll(); | |
| int posX = curr.getX(); | |
| int posY = curr.getY(); | |
| //This loop checks for all the possible paths where the island can extend. | |
| for (int i=0;i<4;i++){ | |
| int currX = posX + xDir[i]; | |
| int currY = posY + yDir[i]; | |
| //We will check whether we can go to the currX and currY point. And if that point is not visited | |
| //we will add that point into the queue and also mark it as visited. Also the current variable keeps | |
| //track of the current island size. After we get out of this loop, we return the current value | |
| if (isSafe(currX,currY,row,col) && grid[currX][currY]==1 && !visited[currX][currY]){ | |
| queue.add(new Node(currX,currY)); | |
| visited[currX][currY] = true; | |
| current++; | |
| } | |
| } | |
| } | |
| } | |
| //This utility method helps to check whether a point (i,j) is outOfBounds or not. | |
| private boolean isSafe(int i,int j,int m,int n){ | |
| return (i>=0 && i<m) && (j>=0 && j<n); | |
| } | |
| //This is a container class which has two fields, x and y. This class is used to keep the | |
| //points in the queue as a pair | |
| static class Node { | |
| private int x; | |
| private int y; | |
| public Node(int x, int y) { | |
| this.x = x; | |
| this.y = y; | |
| } | |
| public int getX() { | |
| return x; | |
| } | |
| public int getY() { | |
| return y; | |
| } | |
| } | |
| } |
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)