Codility 'ShortestAdjSeq' Solution

Martin Kysel · August 21, 2020

Short Problem Definition:

A non-empty zero-indexed array A consisting of N integers is given. Two integers P and Q are called adjacent in array A if there exists an index 0 ≤ K < N−1 such that:

  • P = A[K] and Q = A[K+1], or
  • Q = A[K] and P = A[K+1].

A non-empty zero-indexed sequence B consisting of M integers is called adjacent in array A if the following conditions hold:

  • B[0] = A[0];
  • B[M−1] = A[N−1];
  • B[K] and B[K+1] are adjacent in A for 0 ≤ K < M−1.



time complexity is O(NlogN)

space complexity is O(N)


This is a graph problem, the shortest adjacent sequence is basically a shortest path in a bidirectional graph.

To calculate the shortest path I am using Breath-first-search or Dijkstra’s algorithm.

I don’t agree with the problem specification of one of the extreme cases such as [1,2,1]. I believe that the shortest path is 3, since the beginning and end are not adjacent. But it seems that Codility expects 1.

from collections import defaultdict

def bfs_shortest_path(paths, start, end):
    q = [(start, 1)]

    visited_paths = set()

    while q:
        key, distance = q.pop(0)
        new_distance = distance + 1
        for path in paths[key]:
            if path == end:
                return new_distance
            elif path not in visited_paths:
                q.append((path, new_distance))

def solution(A):
    if len(A) <= 2:
        return len(A)

    # I dont agree with this edge case based on the problem statement
    if A[0] == A[-1]:
        return 1

    paths = defaultdict(set)


    for i in range(1, len(A)-1):

    return bfs_shortest_path(paths, A[0], A[-1])

Twitter, Facebook