Whenever array value can be used as index, consider cycle detection..


  • 0
    D

    It looks like this question has given us a lesson that whenever array value (not index) can be used as index, then we need to consider cycle detection (quick & slow pointer method).

    public class Solution {
        public int findDuplicate(int[] nums) {
            if (nums == null || nums.length == 1) {
                return 0;
            }
            int n = nums.length - 1;
            int slowIndex = 0;
            int fastIndex = 0;
            do {
                slowIndex = nums[slowIndex];
                fastIndex = nums[nums[fastIndex]];
            } while (slowIndex != fastIndex);
            int index1 = 0;
            int index2 = slowIndex;
            while (index1 != index2) {
                index1 = nums[index1];
                index2 = nums[index2];
            }
            return index1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.