What is the time complexity of Reachable Nodes With Restrictions?

The optimal solution has a time complexity of O(n + E).

What is the space complexity of Reachable Nodes With Restrictions?

The space complexity is O(n + E).

What data structures are used to solve Reachable Nodes With Restrictions?

This problem uses Array, Hash Table, Tree, 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 Reachable Nodes With Restrictions?

Insight 1: Represent the graph using an adjacency list for efficient neighbor lookups. Insight 2: Use Breadth-First Search (BFS) to explore the graph level by level, starting from node 0.

Which companies ask LeetCode 2368. Reachable Nodes With Restrictions in interviews?

This problem is frequently asked at MakeMyTrip.

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

Reachable Nodes With Restrictions - LeetCode 2368 Solution

Reachable Nodes With Restrictions - Complete Solution Guide

Reachable Nodes With Restrictions is LeetCode problem 2368, 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 is an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given a 2D integer array edges of length n - 1 where edges[i] = [a i , b i ] indicates that there is an edge between nodes a i and b i in the tree. You are also given an integer array restricted which represents restricted nodes. Return the maximum number of nodes you can reach from node 0 without visiting a restricted node. Note that node 0 will not be a restricted node. Example 1: Input: n = 7, edges = [[

Detailed Explanation

The problem presents an undirected tree represented by a list of edges. We are given a set of 'restricted' nodes that cannot be visited. The goal is to find the number of nodes reachable from node 0 without traversing any restricted nodes. Node 0 is guaranteed not to be restricted. The input consists of the number of nodes 'n', a list of edges 'edges', and a list of restricted nodes 'restricted'. The output is the count of reachable nodes from 0, excluding the restricted ones.

Solution Approach

The solution uses a BFS algorithm to traverse the tree starting from node 0. An adjacency list is used to represent the graph. A set of restricted nodes is created for fast lookups. A queue is used to implement BFS, and a set 'visited' tracks visited nodes to avoid cycles. The algorithm explores the graph level by level, only adding unvisited and non-restricted neighbors to the queue. The count of visited nodes represents the number of reachable nodes from node 0.

Step-by-Step Algorithm

Step 1: Create an adjacency list from the given 'edges' list. Each node in the graph will be a key in the dictionary, and the value will be a list of its adjacent nodes.
Step 2: Create a set 'restricted_set' from the given 'restricted' list for efficient membership checking (O(1) lookup).
Step 3: Initialize a queue 'q' with node 0 (if 0 is not in restricted_set).
Step 4: Initialize a set 'visited' with node 0 to keep track of visited nodes and prevent cycles.
Step 5: Initialize a 'count' variable to 0. This will store the number of reachable nodes.
Step 6: While the queue 'q' is not empty:
Step 7: Dequeue a node 'node' from the queue and increment 'count'.
Step 8: Iterate through the neighbors of the 'node' from the adjacency list.
Step 9: For each neighbor, check if it is not in the 'visited' set and not in the 'restricted_set'.
Step 10: If the neighbor satisfies both conditions, add it to the 'visited' set and enqueue it to the queue.
Step 11: After the queue is empty, return the 'count'.

Key Insights

Insight 1: Represent the graph using an adjacency list for efficient neighbor lookups.
Insight 2: Use Breadth-First Search (BFS) to explore the graph level by level, starting from node 0.
Insight 3: Maintain a 'visited' set to prevent cycles and a 'restricted' set for quick lookups to avoid restricted nodes.

Complexity Analysis

Time Complexity: O(n + E)

Space Complexity: O(n + E)

Topics

This problem involves: Array, Hash Table, Tree, Depth-First Search, Breadth-First Search, Union Find, Graph.

Companies

Asked at: MakeMyTrip.

Reachable Nodes With Restrictions | LeetCode 2368

Medium

Array Hash Table Tree Depth-First Search Breadth-First Search Union Find Graph

Time: O(n + E)Space: O(n + E)

Solution Code

Available in:

import java.util.*;

class Solution {
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
        }

        Set<Integer> restrictedSet = new HashSet<>();
        for (int r : restricted) {
            restrictedSet.add(r);
        }

        Queue<Integer> q = new LinkedList<>();
        // Node 0 is guaranteed not to be restricted.
        if (!restrictedSet.contains(0)) {
            q.offer(0);
        }

        Set<Integer> visited = new HashSet<>();
        visited.add(0);
        int count = 0;

        while (!q.isEmpty()) {
            int node = q.poll();
            count++;

            if (adj.containsKey(node)) {
                for (int neighbor : adj.get(node)) {
                    if (!visited.contains(neighbor) && !restrictedSet.contains(neighbor)) {
                        visited.add(neighbor);
                        q.offer(neighbor);
                    }
                }
            }
        }

        return count;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2368: Reachable Nodes With Restrictions - Detailed explanation and solution approaches.

Topics

Array Hash Table Tree Depth-First Search Breadth-First Search Union Find Graph

Companies

MakeMyTrip

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:2368

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

11 steps

1
Step 1: Create an adjacency list from the given 'edges' list. Each node in the graph will be a key in the dictionary, and the value will be a list of its adjacent nodes.
2
Step 2: Create a set 'restricted_set' from the given 'restricted' list for efficient membership checking (O(1) lookup).
3
Step 3: Initialize a queue 'q' with node 0 (if 0 is not in restricted_set).
4
Step 4: Initialize a set 'visited' with node 0 to keep track of visited nodes and prevent cycles.
5
Step 5: Initialize a 'count' variable to 0. This will store the number of reachable nodes.
6
Step 6: While the queue 'q' is not empty:
7
Step 7: Dequeue a node 'node' from the queue and increment 'count'.
8
Step 8: Iterate through the neighbors of the 'node' from the adjacency list.
9
Step 9: For each neighbor, check if it is not in the 'visited' set and not in the 'restricted_set'.
10
Step 10: If the neighbor satisfies both conditions, add it to the 'visited' set and enqueue it to the queue.
11
Step 11: After the queue is empty, return the 'count'.

💡

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 + E)

💾

Space Complexity

O(n + E)

📝

Why?

The time complexity is determined by the BFS traversal. The space complexity comes from storing the adjacency list, visited nodes, restricted nodes, and the queue used for BFS.

📖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

Depth-First Search (DFS)

Instead of BFS, we can use DFS to traverse the graph. The logic remains the same: avoid restricted nodes and keep track of visited nodes.

Time: O(n + E)Space: O(n + E) in the worst case (skewed tree), and O(n) on average (balanced tree) due to recursion stack.

Trade-offs: BFS is generally preferred because it finds the shortest path (in terms of number of edges) from the starting node. DFS can lead to stack overflow errors for very deep trees. However, if the problem requires finding a path and not necessarily the shortest one, DFS can be a simpler implementation in some cases.

Union Find

We could use Union Find to find the connected component containing node 0, but exclude restricted nodes during the union process. This is less intuitive than BFS/DFS for this specific problem.

Time: O(E * α(n)), where α(n) is the inverse Ackermann function, which is almost constant for practical values of n.Space: O(n)

Trade-offs: Union Find is more complex to implement for this specific problem. While its time complexity is technically better (almost linear), the constant factors are higher compared to BFS/DFS making it less efficient in practice for this specific task.

✨

Key Insights

1Insight 1: Represent the graph using an adjacency list for efficient neighbor lookups.
2Insight 2: Use Breadth-First Search (BFS) to explore the graph level by level, starting from node 0.
3Insight 3: Maintain a 'visited' set to prevent cycles and a 'restricted' set for quick lookups to avoid restricted nodes.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Tree

Hierarchical structure with nodes. Like a family tree!

Graph

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

Edge Cases

Edge case 1: Empty graph (n = 0 or edges is empty). The code should still work correctly, returning 0 because there are no nodes reachable.
Edge case 2: Node 0 is isolated (no edges connected to it). The algorithm correctly returns 1 (only node 0 is reachable).
Edge case 3: All nodes are restricted except 0. The algorithm correctly returns 1 (only node 0 is reachable).
Edge case 4: All nodes are reachable. The algorithm correctly returns n minus the number of restricted nodes.
Edge case 5: The graph is disconnected. The algorithm only counts nodes reachable from 0, as required.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to check for cycles. Without the 'visited' set, the algorithm could loop infinitely.

✗Common mistake 2: Not handling the case where the graph is disconnected. The algorithm should only count nodes reachable from node 0.

✗Common mistake 3: Incorrectly building the adjacency list or restricted set, leading to incorrect neighbors or misidentified restricted nodes.

✗Common mistake 4: Failing to exclude restricted nodes during traversal, resulting in an inflated count of reachable nodes.

✅

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: Network routing where certain nodes (routers) are unavailable due to maintenance or failure. Find all reachable devices from a specific source device.

🏦Real-world scenario 2: Social network analysis where certain users are blocked or restricted. Find all reachable users from a given user within the network.

🎮Real-world scenario 3: Mapping reachable locations on a map where certain roads are closed or inaccessible. Determine all reachable locations from a starting point.

💡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

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

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 29, 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

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

@CodeNinjaJul 13

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

@TechLeadJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Reachable Nodes With Restrictions"?

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

🤖 Need help with this problem?