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 = A;
- 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() visited_paths.add(start) 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: visited_paths.add(path) 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 == A[-1]: return 1 paths = defaultdict(set) paths[A].add(A) paths[A[-1]].add(A[-2]) for i in range(1, len(A)-1): paths[A[i]].add(A[i-1]) paths[A[i]].add(A[i+1]) return bfs_shortest_path(paths, A, A[-1])
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.