Problem Statement in English

You’re given a 2D array roads where roads[i] = [a, b] indicates that there is a road between city a and city b. The capital is city 0. Each road has a cost of 1. You have to report to the capital from all cities. Each car can carry at most seats people. You need to find the minimum number of cars needed to report to the capital.

Approach

The most important thing is to realize that this is a tree problem. The capital is the root of the tree, and we need to find the number of cars needed to report from all cities to the capital.

After that it’s just a matter of traversing the tree appropriately.

Solution in Python


class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        adjList = defaultdict(list)

        for src, dst in roads:
            adjList[src].append(dst)
            adjList[dst].append(src)

        total = 0

        def dfs(node, parent):
            nonlocal total
            people = 0

            for nei in adjList[node]:
                if nei != parent:
                    incoming = dfs(nei, node)
                    carsNeeded = (ceil(incoming/seats))
                    total += carsNeeded
                    people += incoming

            return people + 1

        dfs(0, 0)

        return total

Complexity

  • Time: O(n)O(n)
    Since we are traversing the tree once, the time complexity is linear with respect to the number of nodes.

  • Space: O(1)O(1)
    Since we are not using any extra space, the space complexity is constant.

Mistakes I Made

I had to look this one up :(

And we are done.