Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
using System;
class Solution
{
public static int GetNumberOfIslands(int[,] binaryMatrix)
{
// your code goes here
}
static void Main(string[] args)
{
}
}
/*
keywords: 2D array, 0 and 1,
same row, same column , at most 4 neighbors, not 8 ones
010020
010300
ask: return number of islands
[0, A, 0, B, 0],
[0, 0, -1, -1, -1],
[E, 0, 0, -1, 0],
[0, C, -1, 0, 0],
[D, 0, -1, 0, E]
BFS - value 1, mark visited -1
it is in the range of matrix and also it is 1, and then add to queue
your appear.in is laggy. maybe turn off the video to conserve bandwidth?
time: O(rows*columns)
queue: at most 16 -> O(m*n) - you are correct
rows * columns -> 1 ->
Follow-up 1:
Let's say the dataset is very large.
The input data is now a list of coordinates for any piece of land.
No guarantee on order of coordinates given to you. (random order)
size k -> preprocessing size k -> order by sort by row, second col
put all cordination into dictionary to loop up O(1) <-
key = row + ';' + col -> 1 -> value 1's dictionary -> O(1)
visited one -> look up hashset O(1)
(1000, 23)
(0, 1)
(0, 3)
(3948, 1837)
1st loop: insert all into land_dictionary
2nd loop: lookup neighbors in land_dcitionary and mark in visisted dictionary
returning number of island at the very end
Follow-up 2:
We have the same conditions as above.
0123
0 0bec
1 000d
2 a000
Stream:
a: (2, 0)
b: (0, 1)
c: (0, 3)
d: (1, 3)
e: (0, 2)
0bec
000d
a000
Return:
a, b, c, d, e
1, 2, 3, 3, 2
Result:
[1, 2, 2, 3]
1. find island, assign id,using global id startin from 1 , increment one at time
2. still want to go over the steam one by one, mark element, create -> save steamid, id -> dictionary
3. go over stream, look up dictionary, try to find island
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.