Making The Largest Island

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
20 upvotes
Asked in companies
AmazonMicrosoftHike

Problem statement

You are given an 'n' x 'n' binary matrix 'grid'.


You are allowed to change at most one '0' to be '1'. Your task is to find the size of the largest island in the grid after applying this operation.


Note: 
An island is a 4-directionally (North, South, East, West) connected group of 1s.


Example: 
Input: 'grid' = [[1,0],
                 [0,1]]
Output: 3

Explanation:
We can change the 0 at (0,1) to 1 and get an island of size 3.


Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of each test case contains an integer 'n', representing the number of rows and columns in 'grid'.

Each of the next 'n' lines contain 'n' elements each denoting the values of the grid.


Output format: 
Return the largest size of the island in the grid after applying the given operation at most once.


Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1:
2
0 1
1 0


Expected Answer:
 3


Output on console:
 3


Explanation for Sample Input 1:
For this test case,
If we change the 0 at (1,1) to 1, then we get an island with size 3.


Sample Input 2:
4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Expected Answer:
 1


Output on console:
 1


Expected Time Complexity:
Try to do this in O(n^2).


Constraints:
1 <= n <= 500
0 <= grid[i][j] <= 1


Time Limit: 1 sec
Hint

Can you solve this problem using  Depth-first search?

Approaches (2)
Brute Force Approach

Approach:

  • This is a brute force approach where for every 0 we encounter, we temporarily change it to 1 and find the maximum size of the resulting island that is formed. After finding the size of the island, we will change the 1 back to 0. In the end, we will return the maximum size of the island that we were able to find in all our iterations. We will be using Depth First Search (DFS) to find the islands and their size.

Algorithm:

  • We will create the variable ‘maxSize’ intialised to 0 to store our answer, and the variable ‘hasZero’ intialised to the boolean value False to check whether there is at least one zero in the binary matrix.
  • We will iterate over the matrix, and for every zero, we temporarily make it one and call the depth-first search at this point.
  • Find the maximum size of the island of 1’s and update the ‘maxSize’.
  • Again we change the value at that index back to 0.
  • Finally, if ‘hasZero’ is true, we will return ‘maxSize’; otherwise, we will return the number N*N  as the grid will have all 1’s belonging to the same island.
Time Complexity

O(N^4), where ‘N’ is the number of rows in the binary matrix. 

 

Since we are traversing over each element of the matrix, and we are calling DFS for every 0 encountered which takes O(N^2) time for each call. Hence, the overall Time Complexity is O(N^4).

Space Complexity

O(N^2), where ‘N’ is the number of rows in the binary matrix.

 

In the worst case, O(N) space is used by the recursion stack formed during DFS traversal, and also, the visited array used for DFS takes O(N^2) space. Hence, the overall Space Complexity is O(N^2).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Making The Largest Island
Full screen
Console