Back to course home
0% completed
Vote For New Content
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