Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 3: Cycle in a Circular Array

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!
beruss sama

beruss sama

· 5 months ago

def circularArrayLoop(self, nums: List[int]) -> bool:
        n = len(nums)
        def get_next(idx):
            return (idx + nums[idx]) % n
        
        def is_invalid(idx, direction):
            return (nums[idx] > 0) != direction
        
        for i in range(n):
            direction = nums[i] > 0
            slow, fast = i, i
            while True:
                slow = get_next(slow)
                if is_invalid(slow, direction): break
                fast = get_next(fast)
                if is_invalid(fast, direction): break
                fast = get_next(fast)
                if is_invalid(fast, direction): break

                if slow == fast:
                    if slow == get_next(slow):
                        break
                    return True
Alexei Tilikin

Alexei Tilikin

· 7 months ago

It's enough to use one (slow) pointer and "visited" set. Visited requires O(n) space but also detects any loops. We just need to clear the set every time the direction changes.

It's enough to walk at most (N + 1) steps because one of the following will happen:

  • detected a cycle with the same direction (i.e. returned "true")
  • entered a cycle with direction change. This is the only logical option after N + 1 steps if the above didn't hold, since we have to step at the same node at least once.
K

kfaham

· a year ago

class Solution:
  def loopExists(self, arr): # T O(N) | S O(1)
    p1 = self.getNext(arr, 0)
    p2 = self.getNext(arr, self.getNext(arr, 0))

    # step 1) find an element within the cycle
    while p1 != p2:
      p1 = self.getNext(arr, p1)
      p2 = self.getNext(arr, self.getNext(arr, p2))
    
    # step 2) make sure its a cycle that contains atleast 1 other element
    p2 = self.getNext(arr, p1)
    if p1 == p2:
      return False
    
    # step 3) make sure all the directions of the cycle are the same
    while p1 != p2:
      if (arr[p2] < 0 and arr[p1] > 0) or (arr[p2] > 0 and arr[p1] < 0):
        return False
      p2 = self.getNext(arr, p2)
    
    return True


  def getNext(self, arr, index): # T O(1) | S O(1)
    if index is None or len(arr) - 1 < index:
Show 1 reply
Denys Stopkin

Denys Stopkin

· a year ago

Either I don't understand the task or it's incorrect (incomplete). Example array: {3,2,-2,5,6}. The last value gives a circle itself since it goes through the whole array's available index range twice. [0, 1, 2, 3, 4 ] + 6 = 10 10 - arr.size() = 5, which is greater than allowed index is 5 - arr.size() = 0. And here we have circled through the array twice already. Does it mean that this particular example should return true?

In the same case if we start form 2 the sequence would prove the circle exists before the loop would be found

Ashutosh Kumar

Ashutosh Kumar

· a year ago

Cycle in a Circular Array, An Alternate Approach :O(N) fails for [2, 2, -3, -1]

Ankit Joshi

Ankit Joshi

· a year ago

Floyd's algorithm will eventually find any cycle that exists, even if we start from index 0

class Solution {

  public boolean loopExists(int[] arr) {
    int slow = 0;
    int fast = 0;
    do{
      slow = getNext(arr, slow);
      fast = getNext(arr, getNext(arr, fast));
    }while(slow!=fast);

    int length =  getCycleLength(arr,slow) ;
    return length>1;
  }

  int getNext(int a[], int index){
    int val = a[index]+a.length+index;
    return val%a.length;
  }

  int getCycleLength(int a[], int slow){
    int index = slow;
    boolean isNegative = false;
    boolean isPositive = false;
    int count = 0;
    if(a[slow]>0){
      isPositive = true;
    }else{
      isNegative = true;
    }
    do{
      index = getNext(a, index);
      if(a[index]>0){
        isPos
Show 1 reply
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
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
        }
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};
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

Reading Progress

0%