Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Mohammed Dh Abbas
the official solution is buggy please see why with my solution

Mohammed Dh Abbas

Jul 7, 2024

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 else: remain = fmod(new_index, len(arr)) if remain < 0: index = len(arr) + remain # negative index. we need to get the positive index else: index = remain # zero case else: index += val return (int(index), direction) # initial slow pointer move slow = move(0, arr) # initial fast pointer move + record the direction fast = move(0, arr) prev_fast_dir = fast[1] prev_fast_node = fast[0] fast = move(fast[0], arr) while slow and fast: # pointers are not moving if fast[1] == 'n': return False # pointers meet in one direction and we have more that one node involved elif slow[0] == fast[0] and prev_fast_dir == fast[1] and prev_fast_node != fast[0]: return True # pointers meet in one direction and we have only one node elif slow[0] == fast[0] and prev_fast_dir == fast[1] and prev_fast_node == fast[0]: return False # pointers meet in different directions elif slow[0] == fast[0] and prev_fast_dir != fast[1]: return False else: # move pointers store the last direction slow = move(slow[0], arr) fast = move(fast[0], arr) prev_fast_dir = fast[1] fast = move(fast[0], arr) return False

0

0

Comments
Comments
R
Ricardo Estradaa year ago

3rd constraint of the problem description specifies that no element in the array can be 0

  • nums[i] != 0

On this page