There are solutions (a. O(n^2) time, O(1) space; b. O(n) time, O(n) space). This works by dividing the range of possible numbers that the duplicate could occur in into half every iteration. For n there will be logn iterations, so O(nlogn) time and O(1) space.

a: 1 2 5 4 5 4 l h m ec ac 1 5 3 3 2 4 5 4 1 2 4 4 a: 1 2 3 4 5 4 l h m ec ac 1 5 3 3 3 4 5 4 1 2 4 4 a: 1 2 3 5 5 4 l h m ec ac 1 5 3 3 3 4 5 4 1 1 5 5

//O(nlogn) time, O(1) space (a): n = a.length()-1 low = 1 high = n while low < high: mid = low + (high-low)/2 expected = mid-low+1 count = 0 for i = 0, i < a.length(), i++: if low <= a[i] <= mid: count++ if count <= expected: low = mid +1 else: high = mid //not mid-1 return low // or high

beast mode

This approach treats the array as a graph where value at index i points to index a[i]-1 (so value 1 points to index 0). There is at least 1 repeating number, so the graph will be cyclic. There are n+1 elements and the max is n, so the last node a[n+1] will never be a part of a cycle but will enter a cycle. This is important as this last node is the start node for traversal. Note that if a node which is part of a cycle is used as start node with slow (1x) and fast (2x) pointers then they meet at that same node itself which is not useful. Let's call the converging node as meet node. If the meet node is k hops away from the cycle node, the start node will also be k hops away from the cycle node. This logic is same as finding the cycle node in a cyclic linked list. The array is traversed a max of 3 times so O(n) time and O(1) space.

Note:

I have not found this approach anywhere yet. All solutions I found so far (here, here) go by finding the length of cycle and putting one pointer ahead by that length.

i: 0 1 2 3 |-|---| a: 2 1 3 2 |-| i: 0 1 2 3 |-| |-| a: 3 1 2 3 | |-| |---| i: 0 1 2 3 4 5 |---|-| |-| a: 3 4 2 3 1 5 | |-| | | | |---| | |-------|

//O(n) time, O(1) space findrepeating(a): x = findrepeating(a, findmeet(a), a[a.length() -1]) return x findmeet(a): slow = fast = a[a.length() -1] while true: slow = a[slow-1] fast = a[a[fast-1]-1] if slow == fast: break meet = slow // or fast return meet findrepeating(a, meet, start): m = meet s = start while m != s: m = a[m-1] s = a[s-1] return m // or s[Hat tip to IC]

## No comments:

## Post a Comment