Monday, 2 October 2023

Number of distinct islands (code in JAVA)


import java.util.*;

import org.w3c.dom.Node;

public class graph {

    // Function to return Breadth First Traversal of given graph.
    public static ArrayList<Integer> bfsOfGraph(int numNodes, ArrayList<ArrayList<Integer>> adj) {
        ArrayList < Integer > bfs = new ArrayList < > (); // stores ans
        boolean vis[] = new boolean[numNodes + 1];
        Queue < Integer > q = new LinkedList < > ();
        // keep any node from where you want to start your bfs
        q.add(1); // keep value of node here, if your node has 0 then you should keep it
        vis[1] = true;
        while (!q.isEmpty()) {
            int levelSize = q.size(); // Number of nodes at the current level

            for (int i = 0; i < levelSize; i++) {
                Integer node = q.poll();
                bfs.add(node);
                for (Integer it : adj.get(node)) {
                    if (!vis[it]) {
                        vis[it] = true;
                        q.add(it);
                    }
                }
            }
            bfs.add(-1); // Add a marker (-1) to separate levels
        }
        return bfs;
    }

    // Function to return a list containing the DFS traversal of the graph.
    public static void dfs(int node, boolean vis[], ArrayList<ArrayList<Integer>> adj, 
    ArrayList<Integer> ls) {
        
        //marking current node as visited
        vis[node] = true;
        ls.add(node);
        
        //getting neighbour nodes
        for(Integer it: adj.get(node)) {
            if(vis[it] == false) {
                dfs(it, vis, adj, ls);
            }
        }
    }
    public static ArrayList<Integer> dfsOfGraph(int numNodes, ArrayList<ArrayList<Integer>> adj) {
        //boolean array to keep track of visited vertices
        boolean vis[] = new boolean[numNodes+1];
        vis[1] = true; 
        ArrayList<Integer> ls = new ArrayList<>();
        dfs(1, vis, adj, ls); 
        return ls; 
    }
 
    // Total number of provinces in given graph 
    public static void dfs(int node, 
       ArrayList<ArrayList<Integer>> adjLs , 
       int vis[]) {
        vis[node] = 1; 
        for(Integer it: adjLs.get(node)) {
            if(vis[it] == 0) {
                dfs(it, adjLs, vis); 
            }
        }
    }
    public static int numProvinces(ArrayList<ArrayList<Integer>> adj, int V) {
        int vis[] = new int[V + 1]; // +1
        int cnt = 0;
        for (int i = 1; i < V+1; i++) { // Start from vertex 1 (assuming 1-based indexing)
            if (vis[i] == 0) {
                cnt++;
                dfs(i, adj, vis);
            }
        }
        return cnt;
    }

        // Count number of islands
        public static class Pair {
            public int first;
            public int second;
        
            public Pair(int first, int second) {
                this.first = first;
                this.second = second;
            }
        }

        public static void bfs(int ro, int co, int[][] vis, char[][] grid) {
            vis[ro][co] = 1; 
            Queue<Pair> q = new LinkedList<Pair>();
            q.add(new Pair(ro, co)); 
            int n = grid.length; 
            int m = grid[0].length; 
            
            // until the queue becomes empty
            while(!q.isEmpty()) {
                int row = q.peek().first; 
                int col = q.peek().second; 
                q.remove(); 
                
                // traverse in the neighbours and mark them if its a land 
                for(int delrow = -1; delrow<=1;delrow++) {
                    for(int delcol = -1; delcol <= 1; delcol++) {
                        int nrow = row + delrow; 
                        int ncol = col + delcol; 
                // check if neighbour row and column is valid, and is an unvisited land
                        if(nrow >= 0 && nrow < n && ncol >= 0 && ncol < m 
                        && grid[nrow][ncol] == '1' && vis[nrow][ncol] == 0) {
                            vis[nrow][ncol] = 1; 
                            q.add(new Pair(nrow, ncol)); 
                        }
                    }
                }
            }
        }
      
          // Function to find the number of islands.
          public static int numIslands(char[][] grid) {
              int n = grid.length; 
              int m = grid[0].length; 
              int[][] vis = new int[n][m];
              int cnt = 0; 
              for(int row = 0; row < n ; row++) {
                  for(int col = 0; col < m ;col++) {
                      // if not visited and is a land
                      if(vis[row][col] == 0 && grid[row][col] == '1') {
                          cnt++; 
                          bfs(row, col, vis, grid); 
                      }
                  }
              }
              return cnt; 
          }
          
    // Flood-Fill Algorithm
    public static void dfs_floodfill(int row, int col, 
    int[][] ans,
    int[][] image, 
    int newColor, int delRow[], int delCol[],
    int iniColor) {
       // color with new color
       ans[row][col] = newColor; 
       int n = image.length;
       int m = image[0].length; 
       // there are exactly 4 neighbours
       for(int i = 0;i<4;i++) {
           int nrow = row + delRow[i]; 
           int ncol = col + delCol[i]; 
           // check for valid coordinate 
           // then check for same initial color and unvisited pixel
           if(nrow>=0 && nrow<n && ncol>=0 && ncol < m && 
           image[nrow][ncol] == iniColor && ans[nrow][ncol] != newColor) {
               dfs_floodfill(nrow, ncol, ans, image, newColor, delRow, delCol, iniColor); 
           }
       }
   }
   public static int[][] floodFill(int[][] image, int sr, int sc, int newColor)
   {
       // get initial color
       int iniColor = image[sr][sc]; 
       int[][] ans = image; 
       // delta row and delta column for neighbours
       int delRow[] = {-1, 0, +1, 0};
       int delCol[] = {0, +1, 0, -1}; 
       dfs_floodfill(sr, sc, ans, image, newColor, delRow, delCol, iniColor); 
       return ans;  
   }

   // Rotten oranges
   public static class Pair_rottenOranges {
    int row;
    int col;
    int tm;
    Pair_rottenOranges(int _row, int _col, int _tm) {
      this.row = _row;
      this.col = _col;
      this.tm = _tm;
    }
  }

   //Function to find minimum time required to rot all oranges. 
   public static int orangesRotting(int[][] grid) {
    // figure out the grid size
    int n = grid.length;
    int m = grid[0].length;
    // n x m 
    Queue < Pair_rottenOranges > q = new LinkedList < > ();
    // n x m 
    int[][] vis = new int[n][m];
    int cntFresh = 0;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        // if cell contains rotten orange
        if (grid[i][j] == 2) {
          q.add(new Pair_rottenOranges(i, j, 0));
          // mark as visited (rotten) in visited array
          vis[i][j] = 2;
        }
        // if not rotten
        else {
          vis[i][j] = 0;
        }

        // count fresh oranges
        if (grid[i][j] == 1) cntFresh++;
      }
    }

    int tm = 0;
    // delta row and delta column
    int drow[] = {-1, 0, +1, 0};
    int dcol[] = {0, 1, 0, -1}; 
    int cnt = 0;

    // until the queue becomes empty
    while (!q.isEmpty()) {
      int r = q.peek().row;
      int c = q.peek().col;
      int t = q.peek().tm;
      tm = Math.max(tm, t);
      q.remove();
      // exactly 4 neighbours
      for (int i = 0; i < 4; i++) {
        int nrow = r + drow[i];
        int ncol = c + dcol[i];
        // check for valid coordinates and 
        // then for unvisited fresh orange
        if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m &&
          vis[nrow][ncol] == 0 && grid[nrow][ncol] == 1) {
          // push in queue with timer increased
          q.add(new Pair_rottenOranges(nrow, ncol, t + 1));
          // mark as rotten
          vis[nrow][ncol] = 2;
          cnt++;
        }
      }
    }

    // if all oranges are not rotten
    if (cnt != cntFresh) return -1;
    return tm;
  }

  // To detect cycle in graph using bfs
  public static class Node {
    int first;
    int second;
    public Node(int first, int second) {
        this.first = first;
        this.second = second; 
    }
}
  public static boolean checkForCycle(ArrayList<ArrayList<Integer>> adj, int s,
            boolean vis[], int parent[])
    {
       Queue<Node> q =  new LinkedList<>(); //BFS
       q.add(new Node(s, -1));
       vis[s] =true;
       
       // until the queue is empty
       while(!q.isEmpty())
       {
           // source node and its parent node
           int node = q.peek().first;
           int par = q.peek().second;
           q.remove(); 
           
           // go to all the adjacent nodes
           for(Integer it: adj.get(node))
           {
               if(vis[it]==false)  
               {
                   q.add(new Node(it, node));
                   vis[it] = true; 
               }
        
                // if adjacent node is visited and is not its own parent node
               else if(par != it) return true;
           }
       }
       
       return false;
    }
    
    // function to detect cycle in an undirected graph
    public static boolean isCycle(int numNodes, ArrayList<ArrayList<Integer>> adj)
    {
        boolean vis[] = new boolean[numNodes+1];
        Arrays.fill(vis,false);
        int parent[] = new int[numNodes+1];
        Arrays.fill(parent,-1);  
        
        for(int i=1;i<numNodes+1;i++)
            if(vis[i]==false) 
                if(checkForCycle(adj, i,vis, parent)) 
                    return true;
    
        return false;
    }

    // detect cycle in graph via dfs
    public static  boolean dfs_cycle(int node, int parent, int vis[], ArrayList<ArrayList<Integer>> 
    adj) {
        vis[node] = 1; 
        // go to all adjacent nodes
        for(int adjacentNode: adj.get(node)) {
            if(vis[adjacentNode]==0) {
                if(dfs_cycle(adjacentNode, node, vis, adj) == true) 
                    return true; 
            }
            // if adjacent node is visited and is not its own parent node
            else if(adjacentNode != parent) return true; 
        }
        return false; 
    }
    // Function to detect cycle in an undirected graph.
    public static boolean isCycle_dfs(int numNode, ArrayList<ArrayList<Integer>> adj) {
       int vis[] = new int[numNode+1]; 
       for(int i = 1;i<numNode+1;i++) {
           if(vis[i] == 0) {
               if(dfs_cycle(i, -1, vis, adj) == true) return true; 
           }
       }
       return false; 
    }

    // Distance of nearest cell having 1 | 0/1 Matrix
    //Function to find distance of nearest 1 in the grid for each cell.
    public static class Node_dist {
        int first;
        int second;
        int third; 
        Node_dist(int _first, int _second, int _third) {
            this.first = _first; 
            this.second = _second; 
            this.third = _third; 
        }
    }
     public static int[][] nearest(int[][] grid)
     {
         int n = grid.length; 
         int m = grid[0].length; 
         // visited and distance matrix
         int vis[][] = new int[n][m]; 
         int dist[][] = new int[n][m]; 
         // <coordinates, steps>
         Queue<Node_dist> q = new LinkedList<Node_dist>();
         // traverse the matrix
         for(int i = 0;i<n;i++) {
             for(int j = 0;j<m;j++) {
             // start BFS if cell contains 1
                 if(grid[i][j] == 1) {
                     q.add(new Node_dist(i, j, 0)); 
                     vis[i][j] = 1; 
                 }
                 else {
                     // mark unvisted 
                     vis[i][j] = 0; 
                 }
             }
         }
         
         
         
         int delrow[] = {-1, 0, +1, 0}; 
         int delcol[] = {0, +1, 0, -1}; 
         
         
         // n x m x 4 
         // traverse till queue becomes empty
         while(!q.isEmpty()) {
             int row = q.peek().first; 
             int col = q.peek().second; 
             int steps = q.peek().third; 
             q.remove(); 
             dist[row][col] = steps; 
             // for all 4 neighbours
             for(int i = 0;i<4;i++) {
                 int nrow = row + delrow[i]; 
                 int ncol = col + delcol[i]; 
                 // check for valid unvisited cell
                 if(nrow >= 0 && nrow < n && ncol >= 0 && ncol < m
                 && vis[nrow][ncol] == 0)  {
                         vis[nrow][ncol] = 1; 
                     q.add(new Node_dist(nrow, ncol, steps+1));  
                 } 
                 }
             }
         
         // return distance matrix
         return dist; 
     }

     // Surrounded regions replace '0s' with 'X'
     static void dfs(int row, int col,int vis[][], 
    char mat[][], int delrow[], int delcol[]) {
        vis[row][col] = 1; 
        int n = mat.length;
        int m = mat[0].length;
        
        // check for top, right, bottom, left 
        for(int i = 0;i<4;i++) {
            int nrow = row + delrow[i];
            int ncol = col + delcol[i]; 
            // check for valid coordinates and unvisited Os
            if(nrow >=0 && nrow <n && ncol >= 0 && ncol < m 
            && vis[nrow][ncol] == 0 && mat[nrow][ncol] == 'O') {
                dfs(nrow, ncol, vis, mat, delrow, delcol); 
            }
        }
    }

    static char[][] fill(int n, int m, char mat[][])
    {
        int delrow[] = {-1, 0, +1, 0};
        int delcol[] = {0, 1, 0, -1}; 
        int vis[][] = new int[n][m]; 
        // traverse first row and last row 
        for(int j = 0 ; j<m;j++) {
            // check for unvisited Os in the boundary rws
            // first row 
            if(vis[0][j] == 0 && mat[0][j] == 'O') {
                dfs(0, j, vis, mat, delrow, delcol); 
            }
            
            // last row 
            if(vis[n-1][j] == 0 && mat[n-1][j] == 'O') {
                dfs(n-1,j,vis,mat, delrow, delcol); 
            }
        }
        
        for(int i = 0;i<n;i++) {
            // check for unvisited Os in the boundary columns
            // first column 
            if(vis[i][0] == 0 && mat[i][0] == 'O') {
                dfs(i, 0, vis, mat, delrow, delcol); 
            }
            
            // last column
            if(vis[i][m-1] == 0 && mat[i][m-1] == 'O') {
                dfs(i, m-1, vis, mat, delrow, delcol); 
            }
        }
        
        // if unvisited O then convert to X
        for(int i = 0;i<n;i++) {
            for(int j= 0 ;j<m;j++) {
                if(vis[i][j] == 0 && mat[i][j] == 'O') 
                    mat[i][j] = 'X'; 
            }
        }
        
        return mat;
    }

    // Number of Enclaves
    public static int numberOfEnclaves(int[][] grid) {
        Queue<Pair> q = new LinkedList<Pair>();
        int n = grid.length; 
        int m = grid[0].length; 
        int vis[][] = new int[n][m];
        // traverse boundary elements
        for(int i = 0;i<n;i++) {
            for(int j = 0;j<m;j++) {
                // first row, first col, last row, last col 
                if(i == 0 || j == 0 || i == n-1 || j == m-1) {
                    // if it is a land then store it in queue
                    if(grid[i][j] == 1) {
                        q.add(new Pair(i, j)); 
                        vis[i][j] = 1; 
                    }
                }
            }
        }
        
        int delrow[] = {-1, 0, +1, 0};
        int delcol[] = {0, +1, +0, -1}; 
        
        while(!q.isEmpty()) {
            int row = q.peek().first; 
            int col = q.peek().second; 
            q.remove(); 
            
            // traverses all 4 directions
            for(int i = 0;i<4;i++) {
                int nrow = row + delrow[i];
                int ncol = col + delcol[i]; 
                // check for valid coordinates and for land cell
                if(nrow >=0 && nrow <n && ncol >=0 && ncol < m 
                && vis[nrow][ncol] == 0 && grid[nrow][ncol] == 1) {
                    q.add(new Pair(nrow, ncol));
                    vis[nrow][ncol] = 1; 
                }
            }
            
        }
        int cnt = 0;
        for(int i = 0;i<n;i++) {
            for(int j = 0;j<m;j++) {
                // check for unvisited land cell
                if(grid[i][j] == 1 & vis[i][j] == 0) 
                    cnt++; 
            }
        }
        return cnt;
    }

    // Number of distinct islands
    public static void dfs_islands(int row, int col, int[][] vis,
    int[][] grid, ArrayList < String > vec, int row0, int col0) {
    // mark the cell as visited
    vis[row][col] = 1;

    // coordinates - base coordinates
    vec.add(toString(row - row0, col - col0));
    int n = grid.length;
    int m = grid[0].length;

    // delta row and delta column
     int delrow[] = {-1, 0, +1, 0}; 
     int delcol[] = {0, -1, 0, +1}; 

    // traverse all 4 neighbours
    for (int i = 0; i < 4; i++) {
      int nrow = row + delrow[i];
      int ncol = col + delcol[i];
      // check for valid unvisited land neighbour coordinates
      if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m &&
        vis[nrow][ncol] == 0 && grid[nrow][ncol] == 1) {
        dfs_islands(nrow, ncol, vis, grid, vec, row0, col0);
      }
    }
  }
  public static String toString(int r, int c) {
    return Integer.toString(r) + " " + Integer.toString(c);
  }

  public static int countDistinctIslands(int[][] grid) {
    int n = grid.length;
    int m = grid[0].length;
    int vis[][] = new int[n][m];
    HashSet < ArrayList < String >> st = new HashSet < > ();

    // traverse the grid
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        // if not visited and is a land cell
        if (vis[i][j] == 0 && grid[i][j] == 1) {
          ArrayList < String > vec = new ArrayList < > ();
          dfs_islands(i, j, vis, grid, vec, i, j);
          // store it in HashSet
          st.add(vec);
        }
      }
    }
    return st.size();
  }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Input the number of nodes.
        System.out.print("Enter the number of nodes: ");
        int numNodes = scanner.nextInt();

        // Create an adjacency list.
        ArrayList<ArrayList<Integer>> adjList = new ArrayList<>(numNodes);

        for (int i = 0; i < numNodes + 1; i++) { // numNodes + 2 only if remove empty zero index 
            adjList.add(new ArrayList<>());
        }

        // Input the number of edges.
        System.out.print("Enter the number of edges: ");
        int numEdges = scanner.nextInt();

        // Input the edges (connections between nodes).
        System.out.println("Enter the edges (startNode endNode):");
        for (int i = 0; i < numEdges; i++) {
            int startNode = scanner.nextInt();
            int endNode = scanner.nextInt();

            // Add an edge from startNode to endNode (for directed graph).
            adjList.get(startNode).add(endNode);

            // For undirected graph, add the reverse edge as well.
             adjList.get(endNode).add(startNode); // Uncomment this line for an undirected graph.
        }

        // Print the adjacency list.
        System.out.println("Adjacency List:");
        for (int i = 1; i < numNodes + 1; i++) { // if start from zero then empty list will also be seen
            System.out.print(i + " -> ");
            for (int neighbor : adjList.get(i)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
        // BFS of graph
        System.out.println("The bfs of the given graph is:");
        ArrayList<Integer> bfsResult = bfsOfGraph(numNodes, adjList);
        for (Integer node : bfsResult) {
            if (node == -1) {
                System.out.println(); // Print a newline for each level
            } else {
                System.out.print(node + " ");
            }
        }
        // DFS of graph
        System.out.println("The dfs of the given graph is:");
        System.out.println(dfsOfGraph(numNodes, adjList));
        // number of provinces
        System.out.println("The total number of provinces in your graph is: "+numProvinces(adjList, numNodes));
        // count number of islands from the given graph(grid)--> 2D Matrix
        char[][] grid =  {
            {'0', '1', '1', '1', '0', '0', '0'},
            {'0', '0', '1', '1', '0', '1', '0'}
        };
        System.out.println("The total number of island in the grid is: "+numIslands(grid));       
        // Flood Fill algorithm
        System.out.println("The matix after flood fill is below:");
        int[][] image =  {
        {1,1,1},
        {1,1,0},
        {1,0,1}
    };
        // sr = 1, sc = 1, newColor = 2       
        int[][] ans = floodFill(image, 1, 1, 2);
        for(int i = 0; i < ans.length; i++){
            for(int j = 0; j < ans[i].length; j++)
                System.out.print(ans[i][j] + " ");
            System.out.println();
        }
        // Rotten Oranges
        int[][] grid_rottenOranges =  {{0,1,2},{0,1,1},{2,1,1}};
        System.out.println("The minimum time required to rot all the oranges are: "+orangesRotting(grid_rottenOranges));
        // Cycle in graph via BFS
        System.out.println("Is the graph contain cycle(via BFS)? "+isCycle(numNodes,adjList));
         // Cycle in graph via DFS
        System.out.println("Is the graph contain cycle(via DFS)? "+isCycle_dfs(numNodes,adjList));
        // Distance of nearest cell having 1
        int[][] grid_dist = {
            {0,1,1,0},
            {1,1,0,0},
            {0,0,1,1}
        };
        int ans_dist[][] = nearest(grid_dist);
        System.out.println("The nearest distance matrix is as below:");
        for(int i = 0; i < ans_dist.length; i++){
            for(int j = 0; j < ans_dist[i].length; j++){
                System.out.print(ans_dist[i][j] + " "); 
            }
            System.out.println();
        }
        // Surrounded region replace O with X
        System.out.println("Surrounded region matrix after is as below:");
        char mat[][] = {
            {'X', 'X', 'X', 'X'}, 
            {'X', 'O', 'X', 'X'}, 
            {'X', 'O', 'O', 'X'}, 
            {'X', 'O', 'X', 'X'}, 
            {'X', 'X', 'O', 'O'}};
    
            // n = 5, m = 4
            char[][] ans_surround = fill(5, 4, mat);
            for(int i = 0;i < 5;i++) {
                for(int j = 0;j < 4;j++) {
                    System.out.print(ans_surround[i][j] + " ");
                }
                System.out.println();
            }
        // Number of Enclaves
        int grid_enclaves[][] = {
            {0, 0, 0, 0},
            {1, 0, 1, 0},
            {0, 1, 1, 0},
            {0, 0, 0, 0}};
            int ans_enclaves = numberOfEnclaves(grid_enclaves);
            System.out.println("The total number of enclaves are: "+ans_enclaves);
        // Number of distinct islands
        int grid_islands[][] = {
            {1, 1, 0, 1, 1},
            {1, 0, 0, 0, 0},
            {0, 0, 0, 0, 1},
            {1, 1, 0, 1, 1}};
        int ans_islands = countDistinctIslands(grid_islands);
        System.out.println("The total number of distinct islands are: "+ans_islands);
        scanner.close();
    }
}

No comments:

Post a Comment

Good thoughtful question on Binary search on answers

Problem link:  https://leetcode.com/problems/maximize-score-of-numbers-in-ranges/description/ Solution: //import java.util.Arrays; class So...