Linked Areas Count


  • 0
    C

    Given a two-dimensional array which only contains 0 or 1 and width m, height n, Write a function to return the count of Linked areas in the array.

    Note:

    1. Linked area means when point(X,Y) = 1, if the left/right/up/down connected point =1(if we say Point(X-1,Y) = 1, then continue check the left/right/up/down of the point(Point(X-1,Y)) = 1, until you find all the "surrounding" points = 0, these points = 1 make up a linked area
    2. for point(X,Y) = 1, you just need to check 4 directions: left, right, up, down.

  • 0
    C
    static int GetLinkedAreaNum(int[,] map, int m, int n)
            {
                int num = 0;
                for (int i = 0; i < m; ++i)
                {
                    for (int j = 0; j < n; ++j)
                    {
                        if (map[i,j] == 1)
                        {
                            num++;
                            Clear(map, m, n, i, j);
                        }
                    }
                }
                return num;
            }
    
            static void Clear(int[,] map, int m, int n, int x, int y)
            {
                int xx, yy;
                map[x,y] = 0;
                
                //4-linked
                xx = x - 1;
                yy = y;
    
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && (map[xx, yy] == 1))
                    Clear(map, m, n, xx, yy);
    
                xx = x;
                yy = y - 1;
    
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && (map[xx, yy] == 1))
                    Clear(map, m, n, xx, yy);
    
                xx = x;
                yy = y + 1;
    
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && (map[xx, yy] == 1))
                    Clear(map, m, n, xx, yy);
    
                xx = x + 1;
                yy = y;
    
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && (map[xx, yy] == 1))
                    Clear(map, m, n, xx, yy);
            }

  • 2

    Is this the same question as "Number of Islands"?


  • 0
    S

    The approach is simple. Iterate over all array element one by one and see if they have a value of 1 and are visited or not. If they are visited then continue to the next element, else increase your count by one and traverse all the elements connected with this element and mark visited array with true. Hence the count would increase by one every time you find a 1 that has not been marked visited, which means it is unlinked with the other 1s.

    Time Complexity is O(n^2) because you will traverse all the cells just once.

    GitHub Code Link: https://github.com/shivam-maharshi/Algorithms/blob/master/src/microsoft/LinkedAreasCount.java

    Java code:

    /* Link: https://leetcode.com/discuss/48446/linked-areas-count

    • @author shivam.maharshi
      */
      public class LinkedAreasCount {

      private static int[] xa = new int[] { -1, 1, 0, 0 };
      private static int[] ya = new int[] { 0, 0, -1, 1 };

      // Time complexity O(n^2).
      public static int get(int[][] a) {
      int count = 0;
      boolean[][] visited = new boolean[a.length][a[0].length];
      for (int i = 0; i < a.length; i++) {
      for (int j = 0; j < a[0].length; j++) {
      if (a[i][j] == 1 && visited[i][j] == false) {
      count++;
      visit(i, j, a, visited);
      }
      }
      }
      return count;
      }

      private static void visit(int x, int y, int[][] a, boolean[][] visited) {
      visited[x][y] = true;
      for (int i = 0; i < 4; i++) {
      int nextX = x + xa[i];
      int nextY = y + ya[i];
      if (isValidMove(nextX, nextY, a) && a[nextX][nextY] == 1 && !visited[nextX][nextY])
      visit(nextX, nextY, a, visited);
      }
      }

      private static boolean isValidMove(int x, int y, int[][] a) {
      return (x >= 0 && y >= 0 && x < a.length && y < a[0].length);
      }

      public static void main(String[] args) {
      int[][] a = new int [][] {
      {1,0,1,0,1},
      {1,1,0,0,1},
      {1,0,1,0,1},
      {0,0,0,0,1},
      {1,1,1,1,1}
      };
      System.out.println(get(a));
      }

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.