Skip to content

Instantly share code, notes, and snippets.

@Morriz
Created February 11, 2019 15:43
Show Gist options
  • Save Morriz/56a75d7b7cd6c1c7e44e56294411f48f to your computer and use it in GitHub Desktop.
Save Morriz/56a75d7b7cd6c1c7e44e56294411f48f to your computer and use it in GitHub Desktop.
My codility solution to find the longest chain in an array where A[i] -> A[A[i]]:
const solution = A => {
let longest = 0
let next = 0
let count = 1
while (count < A.length) {
let len = 0
while (A[next] !== -1) {
len++
const prev = next
next = A[next]
A[prev] = -1
}
if (len > A.length / 2) return len // early exit since we already have longest
if (len > longest) longest = len
next++
count++
}
return longest
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment