Q9 Number of Enclaves - LeetCode 1085

PHOTO

Sat Apr 22 2023 17:12:52 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07

class Solution {
    public int numEnclaves(int[][] grid) {
        /* Q2 of graph playlist , we fire GCC from boundary elements and make all 1's in those
        components as 0 , then we count left no. of 1's in the grid as those are the land cell
        which will not lead to boundary
        */
        
        //firing DFS to find components from boundary elements and making them 0
        int m = grid.length , n = grid[0].length;

        for(int i = 0 ;i < m ; i++){
            for(int j = 0 ; j< n ; j++){
                if(i == 0 || i == m-1 || j == 0 || j == n-1){
                    if(grid[i][j] == 1)
                    dfs(grid , i , j , m , n);
                }
            }
        }

        // count no. of land cells and return them
        int count = 0;
        for(int i = 0 ;i < m ; i++){
            for(int j = 0 ; j< n ; j++){
                    if(grid[i][j] == 1)
                    count++;
            }
        }
        return count;
    }

    int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
    public void dfs (int[][] grid , int row , int col , int m , int n){
        //base case
        if(row < 0 || col < 0 || row >= m || col >= n || grid[row][col] == 0)
        return;
        
        //making component's 1 to 0
        grid[row][col] = 0;
        
        for(int i =0 ;i < 4 ; i++)
        dfs(grid , row + dir[i][0] , col + dir[i][1] , m ,n);
    }
}

https://leetcode.com/problems/number-of-enclaves/

Save snippets that work from anywhere online with our extensions

Available in the Chrome Web Store

Get Firefox Add-on

Get VS Code extension

Comments

More like this

Graphs Level 2

@Ayush_dabas07

Minimum Score of a Path Between Two Cities - 2492 Number of Operations to Make Network Connected - 1319 Q42 Mother Vertex | Interviewbit (kosraju) Q41 Count Strongly Connected Components (Kosaraju’s Algorithm) Q40 Leetcode 734. Sentence Similarity Q39 Satisfiability of Equality Equations - LeetCode 990 Q38 Redundant Connection II - LeetCode 685 Q37 Redundant Connection - LeetCode 684 Q36 Minimize Malware Spread II - LeetCode 928 Q35 Minimize Malware Spread - LeetCode 924 Q34 Accounts Merge - LeetCode 721 Q33 Minimize Hamming Distance After Swap Operations - LeetCode 1722 Q32 Rank Transform of a Matrix - LeetCode 1632 Q32 Reconstruct Itinerary - leetcode 332 (eularian path && Eularian cycle) Q31 Regions Cut By Slashes - LeetCode 959 Q30 Minimum Spanning Tree | Practice | GeeksforGeeks (kruskal algo) Q29 Number of Islands II - Coding Ninjas (DSU) Q28 Remove Max Number of Edges to Keep Graph Fully Traversable - LeetCode 1579 Q27 Checking Existence of Edge Length Limited Paths - LeetCode 1675 Q26 Network Delay Time - LeetCode 743 Q25 Cheapest Flights Within K Stops - LeetCode 787 Q24 Distance from the Source (Bellman-Ford Algorithm) | Practice | GeeksforGeeks Q23 Connecting Cities With Minimum Cost - Coding Ninjas Q22 Swim in Rising Water - LeetCode 778 Q21 Water Supply In A Village - Coding Ninjas Q20 Minimum Spanning Tree | Practice | GeeksforGeeks(prims algo) Q19 Alien Dictionary | Practice | GeeksforGeeks Q18 Course Schedule - LeetCode 207 (kahn's algorithm) Q17 Minimum edges(0-1 BFS) | Practice | GeeksforGeeks Q17 Minimum edges(0-1 BFS) | Practice | GeeksforGeeks ( using djikstra) Q16 Sliding Puzzle - LeetCode 773 Q15 Bus Routes - LeetCode 815 Q14 Shortest Bridge - LeetCode 934 (without pair class) Q14 Shortest Bridge - LeetCode 934 ( with pair class) Q 13 As Far from Land as Possible - LeetCode 1120 Q12 Rotting Oranges - LeetCode 994 Q11 01 Matrix - LeetCode 542 Q10 Number of Distinct Islands | Practice | GeeksforGeeks Q9 Number of Enclaves - LeetCode 1085 Q8 Coloring A Border - LeetCode 1034 Q7 Unique Paths II - 63 Q6 Unique Paths III - LeetCode 980 Q5 Number of Provinces - LeetCode 547 Q4 Number of Islands - LeetCode 200 Q3 Number of Operations to Make Network Connected - LeetCode 1319 Q2 All Paths From Source to Target - LeetCode 797 Q1 Find if Path Exists in Graph - LeetCode 1971 Q43 is Cycle present in DAG ? GFG ( Topological Sort) Q43 is cycle present in DAG ? GFG (using kahns algo) Q44 Bellman ford | GFG ( Smaller code) Q45 Minimum Cost to Make at Least One Valid Path in a Grid - LeetCode 1368

Browse more snippets >>