Single Cycle Check

tags:Graph Medium

Problem

You're given an array of integers where each integer represents a jump of its value in the array. For instance, the integer 2 represents a jump of two indices forward in the array; the integer -3 represents a jump of three indices backward in the array.

If a jump spills past the array's bounds, it wraps over to the other side. For instance, a jump of -1 at index 0 brings us to the last index in the array. Similarly, a jump of 1 at the last index in the array brings us to index 0.

Write a function that returns a boolean representing whether the jumps in the array form a single cycle. A single cycle occurs if, starting at any index in the array and following the jumps, every element in the array is visited exactly once before landing back on the starting index.

Sample Input

array = [2, 3, 1, -4, -4, 2]

Sample Output

true

Optimal Space & Time Complexity

O(n) time | O(1) space - where n is the length of the input array

Hint 1

In order to check if the input array has a single cycle, you have to jump through all of the elements in the array. Could you keep a counter, jump through elements in the array, and stop once you've jumped through as many elements as are contained in the array?

Hint 2

Assume the input array has length n. If you start at index 0 and jump through n elements, what are the simplest conditions that you can check to see if the array doesn't have a single cycle?

Hint 3

Given Hint #2, there are 2 conditions that need to be met for the input array to have a single cycle. First, the starting element (in this case, the element at index 0) cannot be jumped through more than once, at the very beginning, so long as you haven't jumped through all of the other elements in the array. Second, the (n + 1)th element you jump through, where n is the length of the array, must be the first element you visited: the element at index 0 in this case.

---

Solutions

Official

// O(n) time | O(1) space - where n is the length of the input array

function hasSingleCycle(array) {
  let numElementsVisited = 0;
  let currentIdx = 0;

  while (numElementsVisited < array.length) {
    if (numElementsVisited > 0 && currentIdx === 0) return false;

    numElementsVisited++;
    currentIdx = getNextIdx(currentIdx, array);
  }

  return currentIdx === 0;
}

function getNextIdx(currentIdx, array) {
  const jump = array[currentIdx];
  const nextIdx = (currentIdx + jump) % array.length;

  return nextIdx >= 0 ? nextIdx : nextIdx + array.length;
}

---

Everyone's

Sol

東

Hao

/**
 * Time complexity: O(n) where n is array.length;
 * Space complexity: O(n) where n is array.length;
 */

function hasSingleCycle(array) {
  function sanitize(idx) {
    const remainder = idx % array.length;

    return remainder < 0 ? remainder + array.length : remainder;
  }

  const visited = new Array(array.length).fill(false);

  const startIdx = 0;
  let runningIdx = startIdx;

  for (let i = 0; i < array.length; i += 1) {
    if (visited[runningIdx]) return false;

    visited[runningIdx] = true;
    runningIdx = sanitize(runningIdx + array[runningIdx]);
  }

  return runningIdx === startIdx && visited.every((each) => each === true);
}

YC

/* 
  time: O(n) - where n is the length of the array
  space: O(n) - where n is the length of the array
*/
function hasSingleCycle(array) {
  let counter = 0;
  const visited = new Array(array.length).fill(false);
  let index = 0;
  while(counter < array.length){
    if(visited[index]) return false;
    visited[index] = true;
    counter++;
    index = (index + array[index] % array.length + array.length) % array.length;
  }
  return index === 0
}

---

Supplement / Discussion

Solution 1

We could maybe keep track of how many times we've visited every number in an auxiliary array. So we could have like, a list of the same length here. And maybe we initialize this list to zero everywhere like [0, 0, 0, 0, 0, 0].

And after n jumps, n means the array length. We expect to get something like [1, 1, 1, 1, 1, 1] , which means we have visited every elements exactly once. But when we run through the array, if we find there is value greater than 1 , like [1, 0, 2, 0, 0, 0] it means we have visited more than once, then we return false.

So this seems like a sort of relatively straightforward solution, that would work.

The only problem with that is that we have to use this extra array here to keep track of the times we visited the element.

Solution 2

And there's actually a simpler way of doing this or perhaps not simpler, but a more optimal way of doing it without using an extra array.

So it's actually very similar in term of mindset. What if we don’t keep track of the times we have visited every elements. Because if you think about it, we have n elements, in this case n is equal to six. We expect to visit these six elements exactly once and get back to the element we start with. It means we should jump exactly six times to get back to the starting element.

If we visit some element more than once, we would jump more than six times to get back to the starting element. Similarly, if we reach the starting element with less than six times, it means we have not visited some of the elements.

In a word, only after exact n jumps, we check if the current element is the starting one.