We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Possible Sets of Closing Branches

Number: 3217

Difficulty: Hard

Paid? No

Companies: Atlassian, Meesho, TA Digital

Problem Description

Given n branches (nodes) and an array of roads (edges with weights) that initially connect all branches, determine the number of possible sets of branches that can be closed such that the remaining open branches have a pairwise distance of at most maxDistance. Note that if a branch is closed, all its connecting roads are removed. The remaining set may be empty or consist of a single branch (both are valid). There may be multiple roads between the same two nodes.

Key Insights

  • n is small (n ≤ 10), meaning that iterating over all 2^n potential "closed branch" subsets is feasible.
  • For each subset, the remaining open branches must abide by the condition that every pair is reachable with distance ≤ maxDistance.
  • For each configuration, build a graph using only the open branches and use a shortest-path algorithm (e.g., Floyd–Warshall) to compute pairwise distances.
  • Special cases: An active set with 0 or 1 node always trivially satisfies the condition.
  • Efficiently filtering valid subsets involves iterating through each subset and verifying the property for each pair of active branches.

Space and Time Complexity

Time Complexity: O(2^n * (n^3 + m))
• There are 2^n subsets.
• For each, we potentially process m roads to build the graph and then run Floyd–Warshall in O(n^3), where n ≤ 10.

Space Complexity: O(n^2) per subset for the distance matrix, along with O(m) for storing the roads.

Solution

The solution iterates over every subset of closed branches (using bitmasks). For each subset, the open branches are extracted. If the count of open branches is 0 or 1, the set is valid by definition. Otherwise, a distance matrix is built for the open branches (initializing distances to infinity except for 0 on the diagonal). For every road, if both endpoints are open, update the distance matrix with the road weight (taking the minimum in case of multiple roads). Then, Floyd–Warshall is run on these nodes to compute all-pairs shortest paths. Finally, for every two distinct open branches, if any distance exceeds maxDistance, the subset is invalid. Otherwise, count it as a valid configuration.

Key data structures and techniques:

  • Bitmask/Enumeration for subsets of branches.
  • A 2D matrix and Floyd–Warshall algorithm for computing shortest paths.

Code Solutions

# Python solution with detailed comments
def numberOfClosingSets(n, maxDistance, roads):
    INF = float('inf')
    total_valid = 0
    
    # Loop over all subsets of nodes (each subset represents closed nodes)
    for mask in range(1 << n):
        # Determine open branches (those not closed)
        open_nodes = [i for i in range(n) if not (mask & (1 << i))]
        
        # 0 or 1 active branch is always valid by definition
        if len(open_nodes) <= 1:
            total_valid += 1
            continue
        
        # Initialize the distance matrix for open nodes
        dist = [[INF] * n for _ in range(n)]
        for i in range(n):
            dist[i][i] = 0
        
        # Set the direct road lengths if both endpoints are open
        for u, v, w in roads:
            if u in open_nodes and v in open_nodes:
                # Consider multiple roads: pick the minimum weight
                dist[u][v] = min(dist[u][v], w)
                dist[v][u] = min(dist[v][u], w)
        
        # Run Floyd-Warshall only on the open nodes
        for k in range(n):
            if k not in open_nodes:
                continue
            for i in range(n):
                if i not in open_nodes:
                    continue
                for j in range(n):
                    if j not in open_nodes:
                        continue
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        
        # Check if all pairs of open nodes satisfy the maxDistance condition
        valid = True
        for i in open_nodes:
            for j in open_nodes:
                if i != j and dist[i][j] > maxDistance:
                    valid = False
                    break
            if not valid:
                break
        
        if valid:
            total_valid += 1

    return total_valid

# Example usage:
print(numberOfClosingSets(3, 5, [[0,1,2],[1,2,10],[0,2,10]]))  # Output: 5
← Back to All Questions