Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
A DFS Solution

c.avina05

Dec 30, 2024

It's silly to hop into Union-Find at this level if you haven't been exposed to it.

Here is a simple DFS solution.

class Solution: def findProvinces(self, isConnected): def dfs(node): visited[node] = True for neighbor in range(n): if isConnected[node][neighbor] == 1 and not visited[neighbor]: dfs(neighbor) provinces = 0 n = len(isConnected) visited = [False]*n for i in range(n): if not visited[i]: dfs(i) provinces += 1 return provinces

5

0

Comments
Comments
Design Gurus
Design Gurus10 months ago

The DFS solution is presented as an alternate solution at the end of the lesson.

R
Russell Rogers6 months ago

This is the simplest solution and should have been presented first over the union find solution. The UF solution seems way too complicated for this.