Number of Provinces
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
isConnected[i][j] = 1 means cities i and j are directly connected. A province is a group of cities connected directly or indirectly. Count the provinces.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which cells of the table give you the friendships?
- Hint 2Each successful merge reduces the number of circles by one.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Friend circles again, but given as a table: row i, column j holds 1 if students i and j are friends. Begin with each student in their own circle. For every pair of friends, join their circles if they are different. The number of circles left is the answer.
- The obvious way
DFS from each unvisited city: also O(n²).
- The key insight
provinces = n. For every pair of cities (city, other) with a 1, find the heads; if different, merge and subtract one. The table is symmetric, so looking at only the upper triangle is enough.
- The algorithm
- provinces = n; each city heads itself.
- For each pair with 1 in the table: find both heads.
- Different: merge and provinces - 1.
- Return provinces.
Watch it run
ExampleisConnected = [[1,1,0],[1,1,0],[0,0,1]]
Three cities, three provinces to start.
provinces = 3
Where people slip
- The input is an n x n matrix, not an edge list.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def find_circle_num(is_connected):
count = len(is_connected)
head = list(range(count))
def find(city):
while head[city] != city:
head[city] = head[head[city]]
city = head[city]
return city
provinces = count
for city in range(count):
for other in range(city + 1, count):
if is_connected[city][other] == 1:
city_head, other_head = find(city), find(other)
if city_head != other_head:
head[city_head] = other_head # two provinces become one
provinces -= 1
return provincesNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.