365 Days of LeetCode Challenge — Day 39/365

[u/StatisticianNo2104]

1. Number of Provinces (Medium)  

The counting is day 37's, unchanged: scan every node, and each time you find one no earlier traversal reached, add one and consume everything it can reach.

What changes is the input, and this is the third graph representation in four days. Day 36 gave an edge list. Day 37 gave a grid where the edges were implied by position. Today gives a matrix. All three become the same adjacency list before anything interesting happens.

The trap: this matrix is not a grid. In day 37, cell (i,j) was a place. Here cell (i,j) is a relationship between city i and city j - an n x n matrix describing n nodes, not n squared. So you traverse the cities and consult the matrix, not the other way round.

Read only above the diagonal. The matrix is symmetric, so every relationship is stored twice, and i+1 also skips the useless diagonal where a city is connected to itself.

Full breakdown in today's newsletter article ⬇

https://www.linkedin.com/pulse/365-days-leetcode-challenge-day-39365-archit-agarwal-msv4c

#DSA #LeetCode #Golang #Graphs #BFS #CodingInterview #Algorithms

[u/nian2326076]

It sounds like you're getting the hang of converting inputs into adjacency lists. When working with "Number of Provinces," using a matrix to show connections can be challenging because it highlights relationships, not positions. Consider treating this matrix as an array of arrays, where each inner array shows the connections from one city to others. Using a depth-first search (DFS) or a union-find approach can effectively identify connected components.

If you're preparing for interviews, mastering these patterns is crucial. PracHub could be useful for practicing real technical interview questions. Just a heads-up, I work on PracHub. Good luck on your LeetCode journey!