36. Graphs-2 (grid/traversal problems)

 PROBLEMS ON BFS/ DFS:-

  • no. of provinces          ✅components
  • rotten oranges            ⭐✅multi source BFS
  • no. of islands              ✅BFS/ DFS
  • flood fill                     ✅BFS/ DFS
  • no. of enclaves           ⭐✅multi source BFS/DFS
  • no. of distinct islands ⭐✅shape storing BFS/ DFS
  • surrounded regions    ✅multi source BFS/DFS
  • 0/1 Matrix                  ⭐⭐✅multi source BFS
  • word ladder-1 , 2
----------------------------------------------------------------------------------------------------------------------------

1. No. of provinces

count total components of a graph
time- O(N + V+2E)            space: O(N)
-----------------------------------------------------------------------------------------------------------------------------

2. Rotten oranges

                                                            MULTI    SOURCE    BFS
time: (n*m)               space: (n*m)

it can be seen that oranges are being rottened in a BFS fashion, with each time current level of oranges rottening neighbor oranges at same time...since we need minimum time so BFS is preferred here
------------
No. of starting points = no. of rotten oranges at start
-----------
Here we will create a visited 2d-matrix
-----------
1. initialize a queue & a visited matrix with all rotten oranges at start, along with time 0
2. pick q.front element and update time from this element
3. see its fresh & non visited neighbors , and put them in queue with incrementing time by 1 & mark them as visited
4. repeat till queue is non empty
--------------

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

3. No. of islands

time- n^2        space- n^2

a grid of size NxM consists of '0's (Water) and ‘1's(Land). Find the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically or diagonally i.e., in all 8 directions.

------------------------------------
example- below grid has 1 island

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

No. of islands = no. of graph components



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

4. flood fill

BFS

DFS-
time: 4nm    space: nm
-----------------------------------------------------------------------------------------------------------------------

5. no. of enclaves⭐

count no. of islands such that in a group of islands there should not be any island on boundary

Method-1: flood fill wale mein hi adjustments krdo using if else (ki boundary wale ni lunga)
----------------------------------------------------------------
Method-2:  Multi source DFS
Flood-fill all 1s connected to the boundary (make them 0). Then, count remaining 1s (they are no. of required enclaves).
----------------------------------
using multi source BFS-
-----------------------------------------------------------------------------------------------------------------------------
NOTE-

For any grid-based traversal problem, you can usually solve it by either:

  • Single-source DFS/BFS → starting from each valid unvisited cell (found by if conditions u put)

  • Multi-source DFS/BFS → starting from all valid sources at once (smartly reject invalid nodes using multi source traversal and then traverse for valid nodes)

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

6. no. of  distinct islands



we need to store shape of islands in a set and then return st.count() 
for this for each island, we will subtract base island coordinates from all neighbor islands of it


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

7. Surrounding regions

instead of putting filter in dfs function before setting vis as true, you can instead put a filter in main function before calling dfs for boundary loops

TIME:-   O(nm)        space: O(nm)
-----------------------------------------------------------------------------------------------------------------------------

8. Dist of nearest cell having 0⭐⭐

binary matrix
dist calculated as (i1-i2)+(j1-j2)

if a[i][j]=0 so dist is 0 since element itself is 0

we prefer BFS here, since in BFS we move layer by layer
we will use BFS on 0s and see all 1s at dist of 1 , then at dist of 2 and so on....

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

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more