Introduction

In this blog post, we will explore how to solve the LeetCode problem "2959" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

There is a company with n branches across the country, some of which are connected by roads. Initially, all branches are reachable from each other by traveling some roads. The company has realized that they are spending an excessive amount of time traveling between their branches. As a result, they have decided to close down some of these branches (possibly none). However, they want to ensure that the remaining branches have a distance of at most maxDistance from each other. The distance between two branches is the minimum total traveled length needed to reach one branch from another. You are given integers n, maxDistance, and a 0-indexed 2D array roads, where roads[i] = [ui, vi, wi] represents the undirected road between branches ui and vi with length wi. Return the number of possible sets of closing branches, so that any branch has a distance of at most maxDistance from any other. Note that, after closing a branch, the company will no longer have access to any roads connected to it. Note that, multiple roads are allowed. Example 1: Input: n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]] Output: 5 Explanation: The possible sets of closing branches are: - The set [2], after closing, active branches are [0,1] and they are reachable to each other within distance 2. - The set [0,1], after closing, the active branch is [2]. - The set [1,2], after closing, the active branch is [0]. - The set [0,2], after closing, the active branch is [1]. - The set [0,1,2], after closing, there are no active branches. It can be proven, that there are only 5 possible sets of closing branches. Example 2: Input: n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]] Output: 7 Explanation: The possible sets of closing branches are: - The set [], after closing, active branches are [0,1,2] and they are reachable to each other within distance 4. - The set [0], after closing, active branches are [1,2] and they are reachable to each other within distance 2. - The set [1], after closing, active branches are [0,2] and they are reachable to each other within distance 2. - The set [0,1], after closing, the active branch is [2]. - The set [1,2], after closing, the active branch is [0]. - The set [0,2], after closing, the active branch is [1]. - The set [0,1,2], after closing, there are no active branches. It can be proven, that there are only 7 possible sets of closing branches. Example 3: Input: n = 1, maxDistance = 10, roads = [] Output: 2 Explanation: The possible sets of closing branches are: - The set [], after closing, the active branch is [0]. - The set [0], after closing, there are no active branches. It can be proven, that there are only 2 possible sets of closing branches. Constraints: 1 <= n <= 10 1 <= maxDistance <= 105 0 <= roads.length <= 1000 roads[i].length == 3 0 <= ui, vi <= n - 1 ui != vi 1 <= wi <= 1000 All branches are reachable from each other by traveling some roads.

Explanation

Here's the solution to the problem:

• High-Level Approach:

  • Iterate through all possible subsets of branches to close using bit manipulation.
  • For each subset, construct the graph of remaining branches and calculate the shortest distances between all pairs of remaining branches using the Floyd-Warshall algorithm.
  • Check if the maximum distance between any two remaining branches is at most maxDistance. If so, increment the count.

• Complexity:

  • Runtime Complexity: O(2ⁿ * n³) where n is the number of branches.
  • Storage Complexity: O(n²)

Code

    def numberOfSets(n: int, maxDistance: int, roads: list[list[int]]) -> int:
    count = 0
    for i in range(2**n):
        # Determine active (remaining) branches
        active_branches = []
        for j in range(n):
            if (i >> j) & 1 == 0:
                active_branches.append(j)

        num_active = len(active_branches)

        # If no active branches, it's a valid configuration
        if num_active == 0:
            count += 1
            continue

        # Build the adjacency matrix for the remaining branches
        dist = [[float('inf')] * num_active for _ in range(num_active)]
        for k in range(num_active):
            dist[k][k] = 0

        for u, v, w in roads:
            if u in active_branches and v in active_branches:
                u_idx = active_branches.index(u)
                v_idx = active_branches.index(v)
                dist[u_idx][v_idx] = min(dist[u_idx][v_idx], w)
                dist[v_idx][u_idx] = min(dist[v_idx][u_idx], w)

        # Floyd-Warshall algorithm to find all-pairs shortest paths
        for k in range(num_active):
            for u in range(num_active):
                for v in range(num_active):
                    dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v])

        # Check if the maximum distance between any two active branches is <= maxDistance
        valid = True
        for u in range(num_active):
            for v in range(u + 1, num_active):
                if dist[u][v] > maxDistance:
                    valid = False
                    break
            if not valid:
                break

        if valid:
            count += 1

    return count