Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 3: Cycle in a Circular Array (hard)

Problem Statement

We are given an array containing positive and negative numbers. Suppose the array contains a number ‘M’ at a particular index. Now, if ‘M’ is positive we will move forward ‘M’ indices and if ‘M’ is negative move backwards ‘M’ indices. You should assume that the array is circular which means two things:

  1. If, while moving forward, we reach the end of the array, we will jump to the first element to continue the movement.
  2. If, while moving backward, we reach the beginning of the array, we will jump to the last element to continue the movement.

.....

.....

.....

Like the course? Get enrolled and start learning!
N

Naresh Ch

· 4 years ago

It would be really helpful if code for Alternate Approach that improves algorithm to O(N) was also posted here..

S

subscriptions.michel

· a year ago

Counter example. The following should return true (Cycle -3 -> -2 -> -1 -> -3), but the official solution returns false.

std::vector<int> arr1 = {1,2,-3,-1,1-2};
K

kfaham

· 3 years ago

For the input: [0,1,2,3,4]

It should result in false, since although its a cycle, there's only 1 element. But instead the "correct" answer says its supposed to be "True"

My answer for reference:

class Solution:
  def loopExists(self, arr):
    next_index = self.traverse(0, arr[0], arr)
    slow = next_index
    fast = self.traverse(0, arr[0], arr)
    fast = self.traverse(fast, arr[fast], arr)
    while slow != fast:
      slow = self.traverse(slow, arr[slow], arr)
      fast = self.traverse(fast, arr[fast], arr)
      fast = self.traverse(fast, arr[fast], arr)

    #We have now entered the main cycle. 
    #From here, we want to see if we meet again without hitting any other direction
    fast = self.traverse(fast, arr[fast], arr)
    if slow == fast: 
      return
Show 1 reply
John Snow

John Snow

· 3 years ago

In example 3 with input [2, 1, -1, -2] we already have a circle 1 -> 2 -> 1 isn't it?

Show 1 reply
B

Ben

· 4 years ago

The test Java code runs, but when I do a walk through of the second array the first do loop and second run of findIndex() on fast results in direction != isForward and should result in false. findNextIndex() should exit with -1 whenever this occurs, but it doesn't here. What am I missing - arr[2] == -1 and arr[0] == 2?

Y

Yuqi

· 3 years ago

use a hash

A

Aniket Joshi

· 3 years ago

as the title suggest, when I am at index i, i already have the information if the num at i is < 0 or > 0. why do we need to check again when we calculate the next index?

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

case [0, 1, 2, 3, 4] / there is no cycle from index 0 we cant move to any direction

here is my solution

from math import fmod

class Solution:
  def loopExists(self, arr):
    # this method calculates the new index/direction after + or - shift
    # the new index will be in the range of array length
    def move(index, arr):
      val = arr[index]

      new_index = index + val

      # figure out the direction of the move
      direction = 'n' # no direction
      if new_index > index:
        direction = 'r' # right
      elif new_index < index:
        direction = 'l' # left

      # if index exceeds the boundary of the array
      if new_index < 0 or new_index >= len(arr):
        if new_index > 0:
          index = fmod(new_index, len(arr)) # positive or zero
Show 1 reply
K

Kai

· a year ago

The alternative solution should be corrected like the first solution.

It should cast the arr.size() to int to mod with negative value.

Without casting, mod result will be affected by overflow because of signed status difference between int & size_t

        int nextIndex = (currentIndex + arr[currentIndex]) % (int)arr.size();
        if (nextIndex < 0) {
            nextIndex += arr.size(); // wrap around for negative numbers
        }
PARUNIDAN V K

PARUNIDAN V K

· a year ago

class Solution:
  def loopExists(self, arr):
    def moveIndices(i, n):
      return (i + arr[i]) % n

    n = len(arr)
    slow, fast = 0, 0
    while True:
      slow = moveIndices(slow, n)
      fast = moveIndices(moveIndices(fast, n), n)

      if slow == fast:
        break
    
    forward = (arr[slow] >= 0)

    length = 0
    while True:
      slow = moveIndices(slow, n)
      length += 1
      if (forward and arr[slow] < 0) or (not forward and arr[slow] > 0):
        return False

      if slow == fast:
        if length == 1:
          return False
        else:
          return True

The above solution passes all the given test cases and runs in O(N).

Explanation:

Initialize 2 variables slow and fast to the 0th index and move the indices once for slow and twic

Show 1 reply