1
\$\begingroup\$

I am working on this HackerRank problem but running into time constraint issues.

Basically, given two arrays, we need to determine if the ith element of the second array is reachable by the ith element of the first array, where edges are determined by whether or not the gcd of the two node values is greater than some threshold. Below is my attempt but it times out for large inputs.

def computeGCD(x, y):   
   while(y): 
       x, y = y, x % y   
   return x 

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if start not in graph.keys():
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths


def connectedCities(n, g, originCities, destinationCities):
    res = []
    graph = {i+1:[] for i in range(n)}
    for i in originCities:
        for j in range(n):
            if i != j+1 and computeGCD(i, j+1) > g:
                graph[i].append(j+1)

    for i in range(len(originCities)):
        paths = find_all_paths(graph, originCities[i], destinationCities[i])
        if len(paths) > 0:
            res.append(1)
        else:
            res.append(0)

    return res

Can you help me determine if there is something I can be doing more efficiently here, or if solving this via a graph is even the most appropriate way?

\$\endgroup\$
1
\$\begingroup\$
def computeGCD(x, y):

Just call it gcd. It's part of a computer program: you don't need to say that it computes.


    graph = {i+1:[] for i in range(n)}
    for i in originCities:
        for j in range(n):
            if i != j+1 and computeGCD(i, j+1) > g:
                graph[i].append(j+1)

This is buggy: it doesn't build the whole graph. Consider test case connectedCities(16, 1, [14], [15]): there is a path 14 -- 6 -- 15 with GCDs respectively 2 and 3.

As a matter of style, I would find the code more readable if it iterated over range(1, n+1) and didn't have to continually increment the variable.


    for i in range(len(originCities)):
        paths = find_all_paths(graph, originCities[i], destinationCities[i])
        if len(paths) > 0:
            res.append(1)
        else:
            res.append(0)

Spot the big performance problem: to determine whether any foo exists, it suffices to find one foo. You don't need to find every foo in the universe and then count them.

But just fixing that still leaves a smaller performance problem: if there are a lot of queries (i.e. if originCities and destinationCities are long) then it's quicker to do an expensive preprocessing to get an object which answers queries fast than it is to evaluate each query separately. As a big hint, in graph-theoretic terms the queries are "Are these two vertices in the same connected component?".

Note that if you really want to squeeze the asymptotic complexity (and it's not too bad for practical performance either), \$O(n \lg \lg n + q)\$ is achievable1 where \$q\$ is the number of queries.

1 Technically there's also a factor of \$\alpha(n)\$ where \$\alpha\$ is the inverse Ackermann function, but for practical purposes it's constant.

\$\endgroup\$
  • \$\begingroup\$ Incidentally, it's a fun exercise to consider what nasty test cases you can come up with to punish different implementation approaches. E.g. connectedCities(1000000, 0, [12345], [67890]) can be solved instantaneously; now generalise that trick... This question has great potential for a long-form interview discussion. \$\endgroup\$ – Peter Taylor Mar 7 at 11:52
0
\$\begingroup\$

Solving this via a graph algorithm is probably the way to go. However your find_all_paths algorithm is not the right tool.

Instead, what you need to find are the connected components of this graph. Then, if two vertices are not in the same component, there is no way between them and you can return zero.

With this you can solve the actual connected part in linear time (on top of this you will still have the building of the graph, which will be quadratic in time because of the finding of the edges).

First, though, let's have a look at your graph building. It needs to process all combinations of i and j, not just the ones starting from an origin city, because otherwise cities that are connected via two or more hops will not be marked as connected.

Also, the math module, included in the standard library, also has a gcd function. After testing, that one seems to be about a factor two faster than your implementation.

from collections import defaultdict
from math import gcd
from itertools import count

def build_graph(n, g):
    graph = defaultdict(set)  # don't care if we add a connection more than once
    for i in range(1, n + 1):
        if i not in graph:    # ensure even stand-alone nodes are in the graph
            graph[i] = set()
        for j in range(1, n + 1):
            if i != j and gcd(i, j) > g:
                graph[i].add(j)
                graph[j].add(i)  # make connections bi-directional
    return graph

Now we need to implement a way to find all nodes, starting from one start node, for example depth-first search:

def dfs(graph, start, visited):
    yield start
    visited.add(start)
    for node in graph[start]:
        if node in visited:
            continue
        yield from dfs(graph, node, visited)

With this implementation we could just directly solve the problem like this:

def connectedCities(n, g, originCities, destinationCities):
    graph = build_graph(n, g)
    connected_cities = {i: set(dfs(graph, i, set())) for i in originCities}
    return [dest in connected_cities
            for orig, dest in zip(originCities, destinationCities)]

However, it still has hidden quadratic behaviour, since the depth-first search is performed starting from every origin city, resetting the visited set each time. Instead keep it around and give all nodes that you get from one starting node the same component label:

def get_components(graph):
    assignments, visited = {}, set()
    for label, node in enumerate(graph):
        if node in visited:
            continue
        assignments.update(dict.fromkeys(dfs(graph, node, visited), label))
    return assignments

Example:

graph = {1:[2,3], 2:[1], 3:[1], 4:[5], 5:[4]}
get_components(graph)
# {1: 0, 2: 0, 3: 0, 4: 3, 5: 3}

With some extra work the labels cold be made contiguous, but here it is enough that they are unique. Now, two cities have a connection, iff they are in the same component, i.e. if their assigned component label is the same:

def connectedCities(n, g, originCities, destinationCities):
    graph = build_graph(n, g)
    component = get_components(graph)
    return [int(component[orig] == component[dest])
            for orig, dest in zip(originCities, destinationCities)]

This passes the three sample inputs given in the problem description. I don't have a HackerRank account so I can't test if it is fast enough, though.

In the end it is \$\mathcal{O}(n^2)\$ for the building of the graph, \$\mathcal{O}(n)\$ for finding the connected components and afterwards \$\mathcal{O}(q)\$, with \$q\$ being the length of originCities and destinationCities for the querying.


Here are two possible optimizations on this:

  1. Note that when we added an edge between i and j, we also added an edge between j and i, so j does not need to run over all values anymore, only those larger than i (since all other combinations have already been explored):

    def build_graph(n, g):
        graph = defaultdict(set)  # don't care if we add a connection more than once
        for i in range(1, n + 1):
            if i not in graph:    # ensure even stand-alone nodes are in the graph
                graph[i] = set()
            for j in range(i + 1, n + 1):
                if gcd(i, j) > g:
                    graph[i].add(j)
                    graph[j].add(i)  # make connections bi-directional
        return graph
    
  2. To avoid the recursion limit, implement the depth-first search using a stack of yet-to-be-visited nodes:

    def dfs(graph, start, visited):
        out = {start}
        visited.add(start)
        to_visit = graph[start]
        while to_visit:
            node = to_visit.pop()    # this actually modifies `graph`, careful...
            if node in visited:
                continue
            out.add(node)
            visited.add(node)
            to_visit |= graph[node] - visited
        return out
    
\$\endgroup\$
  • 1
    \$\begingroup\$ Really appreciate the thoughts and help. I tried running your code and unfortunately it does still time out on two of the test cases (before it timed out on 7 so it is an improvement) and it gave the wrong answer for five test cases. I'll take what you have provided me and see if I can dig deeper to see what is going on with these 5 that are wrong and the two that still time out... \$\endgroup\$ – user9592573 Mar 7 at 16:05
  • \$\begingroup\$ @user9592573: Let me know if you figure out a failing testcase. Maybe it's something simple as empty graphs... \$\endgroup\$ – Graipher Mar 7 at 17:04
  • 1
    \$\begingroup\$ I can give you a slow one: print(connectedCities(10000, 1, [10, 4, 3, 6], [3, 6, 2, 9])). There are various heuristics one can implement to reduce the need to precompute connected components, and this is one example of how that can make a big difference. \$\endgroup\$ – Peter Taylor Mar 7 at 17:13
  • \$\begingroup\$ @PeterTaylor: That does take quite some time. And then it hits the recursion limit :) There are a lot of optimizations left in how you build the graph, I guess. And since that part is quadratic it is also where the most benefits are to be gained. \$\endgroup\$ – Graipher Mar 7 at 17:16
  • \$\begingroup\$ I take that back: it's not slow, it dies with RecursionError: maximum recursion depth exceeded in comparison. So maybe large n is where the automated tester is failing the code. \$\endgroup\$ – Peter Taylor Mar 7 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.