36. Graphs-2 (traversal problems)

1. No. of provinces

Count total components in a graph, using any traversal technique
-----------------------------------------------------------------------------------------------------------------------------

2. Rotten oranges⭐

  Multi source BFS

time: O(n*m)   space: O(n*m)
--------------
- count all fresh at start and then count if these many will rot in the process or not

- here we do not need a visited matrix since we can modify given
- we update time each time there rots atleast one orange in a BFS cycle

---------------------------------------------------------------------------------------------------------------------------

3. No. of Islands

Count no. of islands (land surrounded by water in 4 directions)
----------------------------------------------------

time: O(n^2) space: O(n^2)

No. of islands = no. of graph components

-----------------------------------------------------------------------------------------------------------------------------

4. Flood Fill

BFS-
-----------------------------------------------------------------------------------------------------------------------------

5. No. of Enclaves

count no. of islands(group of 1s) where no land is on boundary

- set all 1s connected to boundary as 0, using multi source traversal
- count remaining 1s (lands) in entire matrix
------------------------------
1. using BFS:
-----------------------------------
2. using DFS:
-----------------------------------------------------------------------------------------------------------------------------

6. No. of distinct islands



we need to store shape of islands in a set and then return st.count() 
In every dfs on an island, subtract base island coordinates from all neighbouring islands

-----------------------------------------------------------------------------------------------------------------------------

7. Surrounded regions

time: O(nm)        space: O(nm)

- simply do a multi source BFS, on boundary 0s and preserve these by replacing with #s
- now replace all inner 0s with Xs
- now replace #s again with 0s
-----------------------------------------------------------------------------------------------------------------------------

8. Dist of nearest cell having 0

we want to find distance of nearest 0s
so instead of doing BFS on every 1, 
we will use BFS on all 0s (multi source bfs)
jo koi bhi 0 kisi 1 ko pehle encounter krega toh us 1 ke liye vo wala 0 hi closest hoyega

---------------------------------------------------------------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

30.) DP on subsequences

Image
Subset sum = target✅⭐ Partition equal subset sum✅ Partition array into 2 subsets with min abs [sum(v1)-sum(v2) ]✅ Count subsets with sum k✅⭐ Count partitions with given diff✅ target sum✅ 0/1 knapsack✅⭐ min coins✅---->count min coins to be taken coin change-2--->count n(ways) of taking coins⭐✅ unbounded knapsack✅ rod cutting problem✅ ----------------------------------------------------------------------------------------------------------------------------- 2 ways to generate all subsequences- Power Set, or Recursion subset means subsequence in dsa ----------------------------------------------------------------------------------------------------------------------------- 1. Target Sum- QUES- return true if there exists a subset with sum equal to the target in the array... Soln assuming all array elements are positive  here f(n-1,target) will tell if there's a subsequence till n-1 index with sum = target 1.) RECURSIVE SOLN-        ( time: 2^n    ...
Read more

35. Graphs-1 (basics)

Image
# Note -  1. it has nodes/vertices (N) connected by edges (E) 2. d egree(N)  = n(edges) connected to a node 3. in-degree(N) = no. of in-going edges  4. out-degree(N) = no. of out-going edges  5.  Total degree of undirected graph = (2*E) 6.  DAG - directed acyclic graph 7.  Path -  a sequence of nodes where all  adj nodes have a direct edge b/w them -------------------------------------------------------------------------------------------------------------------------- 1. Representation- 1. Adjacency Matrix:  space: O(n^2) store info about presence of edges between 2 nodes -------------------------------------------------------- 2. Adjacency list:   space: O(n) - store info about adjacent neighbours of a node - for unweighted graph instead of a pair we will store them as integer array ----------------------------------------------------------------------------------------------------------------------------- 2. BFS- time: O(N+...
Read more