C++ interview problem: finding an Island in a 2D grid I was asked this question from an online coding interview and I have provided my solution that passes all of the test cases. I wanted to see if someone can review my code.

You can find my solution below using BFS. Here's also the link to the question that was asked at Pramp.


  Island Count
  
  Given a 2D array binaryMatrix of 0s and 1s, implement a function getNumberOfIslands that returns the number of islands of 1s in binaryMatrix.
  
  An island is defined as a group of adjacent values that are all 1s. A cell in binaryMatrix is considered adjacent to another cell if they are next to each either on the same row or column. Note that two values of 1 are not part of the same island if they’re sharing only a mutual “corner” (i.e. they are diagonally neighbors).
  
  Explain and code the most efficient solution possible and analyze its time and space complexities.

input:  binaryMatrix = [ [0,    1,    0,    1,    0],
                         [0,    0,    1,    1,    1],
                         [1,    0,    0,    1,    0],
                         [0,    1,    1,    0,    0],
                         [1,    0,    1,    0,    1] ]

output: 6 # since this is the number of islands in binaryMatrix.
          # See all 6 islands color-coded below.



#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;queue&gt;
#include &lt;unordered_set&gt;

#define AND &amp;&amp;
using namespace std;

int getNumberOfIslands( const vector&lt;vector&lt;int&gt;&gt;&amp; binaryMatrix ) 
{
  int ans=0;
  int n = binaryMatrix.size();
  if (!n) return 0;
  int m = binaryMatrix[0].size();
  unordered_set&lt;int&gt; *used = new unordered_set&lt;int&gt;[n];
  for (int i=0; i&lt;n; i++) used[i].clear();
 //Implementation through Breadth First Search
 // starting origin for my x and y coordinates 
  int dx[] = {-1, 1, 0, 0};
  int dy[] = {0, 0, -1, 1};
  queue&lt; pair&lt;int, int&gt; &gt; q;



  for (int i=0; i&lt;n; i++)
    for (int j=0; j&lt;m; j++){

      if (!used[i].count(j) AND binaryMatrix[i][j]==1){

        ans++;

        q.push(make_pair(i, j));
        used[i].insert(j);
        while (!q.empty()){
          pair&lt;int, int&gt; pos = q.front();
          q.pop();

          for (int k=0; k&lt;4; k++){
            int nx = pos.first+dx[k];
            int ny = pos.second+dy[k];
            if (nx&lt;0 || nx&gt;=n) continue;
            if (ny&lt;0 || ny&gt;=m) continue;
            if (used[nx].count(ny)) continue;
            if (binaryMatrix[nx][ny]!=1) continue;

            used[nx].insert(ny);
            q.push(make_pair(nx, ny));


          }



        }

      }

    }

  return ans;

}  



int main() {
  return 0;
}


My code passes all of the test cases:



Test Case #1
Input: [[0]],Expected: 0,Actual: 0
Test Case #2
Input: [[1]],Expected: 1,Actual: 1
Test Case #3
Input: [[1,0,1,0]],Expected: 2,Actual: 2
Test Case #4
Input: [[1,0,1,0],[0,1,1,1],[0,0,1,0]],Expected: 2,Actual: 2
Test Case #5
Input: [[1,0,1,0],[0,1,1,1],[0,0,1,0],[1,1,0,0],[0,1,0,1]],Expected: 4,Actual: 4
Test Case #6
Input: [[0,1,0,1,0],[0,0,1,1,1],[1,0,0,1,0],[0,1,1,0,0],[1,0,1,0,1]],Expected: 6,Actual: 6
Test Case #7
Input: [[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]],Expected: 1,Actual: 1
Don't use using namespace std

It's considered bad practice.

Don't define AND

There is already and as an alternative to &amp;&amp;.

Use std::vector instead of new[]

You have a memory leak at the moment, since you forgot to delete[] the allocated memory. std::vector prevents this kind of error.

Use appropriate data structures

You use an array of unordered_set&lt;int&gt;s where a std::unordered_set&lt; std::pair&lt;int,int&gt; &gt; would be sufficient. Also, clear() isn't necessary. Unless your std::unordered_set implementation is broken, a std::unordered_set starts out empty.

Consider const for variables that shouldn't change

dx, dy, n and m should never change. const makes sure that you don't change them by accident.

Always use braces around blocks

No braces after control structures have led to several bugs that were hard to catch. Always use them. That way you cannot accidentally forget to place them when necessary.