0% completed
I think I might have a solution with O(N) time complexity and O(1) space time complexity
PARUNIDAN V K
Apr 9, 2025
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 twice for fast in each iteration. Since it is given that a cycle exists, slow and fast pointers are bound to meet. Once they meet, we will have an index that belongs to the cycle. Starting from this index, move the indices once each iteration and count the length of the cycle until the same index is reached. In the process also track the direction of the cycle. If the length of the cycle is 1 or if the cycle is not uni-directional return False, else return True.
What I am not sure about is, if this solution misses any corner cases not provided in the test cases for this problem.
0
0
Comments
Ankit Joshi6 months ago
It will fail for this test case [1,-1,2,2,2,2,2,4]
On this page