What is the time complexity of Number of Provinces?

The optimal solution has a time complexity of O(n^2).

What data structures are used to solve Number of Provinces?

This problem uses Depth-First Search, Breadth-First Search, Union Find, Graph. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Number of Provinces?

Insight 1: The problem can be modeled as finding the number of connected components in a graph. Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) are suitable algorithms to traverse the graph and identify connected components.

Which companies ask LeetCode 547. Number of Provinces in interviews?

This problem is frequently asked at DoorDash, Sprinklr, Two Sigma.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Number of Provinces - LeetCode 547 Solution

Number of Provinces - Complete Solution Guide

Number of Provinces is LeetCode problem 547, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b , and city b is connected directly with city c , then city a is connected indirectly with city c . A province is a group of directly or indirectly connected cities and no other cities outside of the group. You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the i th city and the j th city are directly connected, and isConnected[i][j] = 0 otherwise. Return the total

Detailed Explanation

The problem asks us to find the number of provinces in a given undirected graph represented by an adjacency matrix. Each city represents a node in the graph, and `isConnected[i][j] = 1` means there's an edge between city `i` and city `j`. A province is a group of connected cities (nodes) where any two cities in the province are reachable from each other, either directly or indirectly. The input is an `n x n` adjacency matrix representing the connections between `n` cities. The output should be the total number of distinct provinces.

Solution Approach

The provided solutions use Depth-First Search (DFS) to explore each connected component. The algorithm iterates through each city. If a city hasn't been visited yet, it means a new province has been found. DFS is then initiated from that city to mark all connected cities as visited. This process continues until all cities have been checked.

Step-by-Step Algorithm

Step 1: Initialize a `visited` array of size `n` (number of cities) to keep track of visited cities. Initially, all cities are marked as not visited (false).
Step 2: Initialize a `provinces` counter to 0. This counter will store the number of provinces found.
Step 3: Iterate through each city from 0 to `n-1`.
Step 4: For each city `i`, check if it has been visited. If `visited[i]` is false, it means a new province has been found.
Step 5: Increment the `provinces` counter by 1.
Step 6: Perform a DFS starting from city `i`. The DFS function marks the current city as visited and then explores all its adjacent cities (neighbors).
Step 7: In the DFS function, for each neighbor `v` of city `u`, if there's an edge between `u` and `v` (i.e., `isConnected[u][v] == 1`) and `v` hasn't been visited, recursively call DFS on `v`.
Step 8: After the DFS is complete for city `i`, all cities in the same province as `i` will be marked as visited.
Step 9: Continue iterating through the remaining cities. Repeat steps 4-8 until all cities have been processed.
Step 10: Return the `provinces` counter, which represents the total number of provinces.

Key Insights

Insight 1: The problem can be modeled as finding the number of connected components in a graph.
Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) are suitable algorithms to traverse the graph and identify connected components.
Insight 3: Union Find data structure provides an efficient solution for connected component problems.

Complexity Analysis

Time Complexity: O(n^2)

Space Complexity: O(n)

Topics

This problem involves: Depth-First Search, Breadth-First Search, Union Find, Graph.

Companies

Asked at: DoorDash, Sprinklr, Two Sigma.

Number of Provinces | LeetCode 547

Medium

Depth-First Search Breadth-First Search Union Find Graph

Time: O(n^2)Space: O(n)

Solution Code

Available in:

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;

        // DFS function
        function dfs(isConnected, u, visited, n) {
            visited[u] = true;
            for (int v = 0; v < n; v++) {
                if (isConnected[u][v] == 1 && !visited[v]) {
                    dfs(isConnected, v, visited, n);
                }
            }
        }
        

        // Iterate to visit each node
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                provinces++;
                dfs(isConnected, i, visited, n);
            }
        }
        
        return provinces;
    }

    private void dfs(int[][] isConnected, int u, boolean[] visited, int n) {
        visited[u] = true;
        for (int v = 0; v < n; v++) {
            if (isConnected[u][v] == 1 && !visited[v]) {
                dfs(isConnected, v, visited, n);
            }
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 547: Number of Provinces - Detailed explanation and solution approaches.

Topics

Depth-First Search Breadth-First Search Union Find Graph

Companies

DoorDashSprinklrTwo Sigma

Stats

Difficulty:Medium

Languages:4

Companies:3

Problem #:547

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Initialize a `visited` array of size `n` (number of cities) to keep track of visited cities. Initially, all cities are marked as not visited (false).
2
Step 2: Initialize a `provinces` counter to 0. This counter will store the number of provinces found.
3
Step 3: Iterate through each city from 0 to `n-1`.
4
Step 4: For each city `i`, check if it has been visited. If `visited[i]` is false, it means a new province has been found.
5
Step 5: Increment the `provinces` counter by 1.
6
Step 6: Perform a DFS starting from city `i`. The DFS function marks the current city as visited and then explores all its adjacent cities (neighbors).
7
Step 7: In the DFS function, for each neighbor `v` of city `u`, if there's an edge between `u` and `v` (i.e., `isConnected[u][v] == 1`) and `v` hasn't been visited, recursively call DFS on `v`.
8
Step 8: After the DFS is complete for city `i`, all cities in the same province as `i` will be marked as visited.
9
Step 9: Continue iterating through the remaining cities. Repeat steps 4-8 until all cities have been processed.
10
Step 10: Return the `provinces` counter, which represents the total number of provinces.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n^2)

🐢 Quadratic - Gets slow with large inputs. Consider optimization!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is O(n^2) because the algorithm iterates through each city `n` times, and in the DFS function, it iterates through all possible neighbors for each city, which is also `n` in the worst case. The space complexity is O(n) due to the `visited` array of size `n`. In the worst-case scenario where the graph is sparse, the DFS recursion stack can also grow to a depth of n, but the `visited` array dominates.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Breadth-First Search (BFS)

Instead of DFS, BFS can be used to explore the graph and identify connected components. The core idea remains the same: iterate through the cities, and if a city hasn't been visited, start a BFS from that city to mark all connected cities as visited.

Time: O(n^2)Space: O(n)

Trade-offs: BFS generally uses more memory than DFS due to maintaining a queue, but in this problem, the space complexity is still O(n) because the adjacency matrix determines the upper bound of connections. There is not much practical difference in using DFS versus BFS for this problem.

Union Find (Disjoint Set)

The Union Find data structure can efficiently solve connected component problems. Initialize each city as a separate component. Then, iterate through the adjacency matrix. If `isConnected[i][j] == 1`, perform a 'union' operation to merge the components containing cities `i` and `j`. Finally, the number of distinct roots represents the number of provinces.

Time: O(n^2 * α(n)), where α(n) is the inverse Ackermann function, which grows very slowly and can be considered almost constant for practical values of n.Space: O(n)

Trade-offs: Union Find is often more efficient than DFS/BFS, especially when the number of union operations is large. For this specific problem, the difference might not be significant due to the adjacency matrix representation. However, Union Find provides a more elegant and scalable solution for general connected component problems. It's especially useful when edges are given in a different format than an adjacency matrix.

✨

Key Insights

1Insight 1: The problem can be modeled as finding the number of connected components in a graph.
2Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) are suitable algorithms to traverse the graph and identify connected components.
3Insight 3: Union Find data structure provides an efficient solution for connected component problems.

📚

Key Terms Explained

For Students

Graph

Nodes connected by edges. Like a social network or city map!

Edge Cases

Edge case 1: A single city with no connections to other cities. The solution correctly identifies this as a province.
Edge case 2: A fully connected graph where all cities are connected to each other. The solution correctly identifies this as a single province.
Edge case 3: An empty graph (n=0). Although the constraints specify 1 <= n <= 200, it's good practice to consider empty input. In this case, some implementations might return 0 without error, while others would fail if not handled specifically. The given code does not handle n=0, but the problem statement does not allow for it.
Edge case 4: Disconnected graphs where each city is an isolated province. This would result in `n` provinces, and the solution would accurately count them.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not marking nodes as visited, leading to infinite loops in the DFS/BFS.

✗Common mistake 2: Incorrectly handling the adjacency matrix indices, potentially accessing out-of-bounds memory.

✗Common mistake 3: Forgetting to free dynamically allocated memory (especially in C), leading to memory leaks.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Social network analysis: Identifying communities or groups of users who are connected to each other. Each user is a node, and connections (friendships, follows) are edges. Finding provinces helps determine distinct social circles.

🏦Real-world scenario 2: Network connectivity: Determining the number of independent networks within a larger network infrastructure. Each device is a node, and connections are physical or logical links. Finding provinces helps identify isolated network segments.

🎮Real-world scenario 3: Image segmentation: Grouping pixels with similar characteristics (color, texture) into distinct regions. Each pixel is a node, and similarity is represented by edges. Finding provinces helps delineate different objects in the image.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 8, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Number of Provinces"?

For this medium-level Depth-First Search problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether breadth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?