O(nlogN) Binary Search and O(n) Circle Detect

  • 1

    The special of this problem is its space limitation

    1. You must not modify the array (assume the array is read only).
    2. You must use only constant, O(1) extra space.

    So, we could turn to Binary Search on values (not the index). I'm still learning this approach. What I could conclude is that:

    Suppose there is an unsorted array with n elements, each element is less than N, how could we find the kth smallest element?


    We could tweak it to fit finding the duplicate one:

      def find_duplicate(nums)
        left, right = 1, nums.max
        while left < right
          mid = (left + right)/2
          count = nums.count{|x| x <= mid}
          if count > mid
            right = mid
            left = mid + 1

    P.S. There is also a O(n) solution. I'm working on it.


    Oh, I love this problem. The O(n) solution makes use of Circle Detection in a perfect way. I've checked several posts in the discussion. Here is my note:

    First, we could transfer the problem into a linked list one, as it says

    Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive)


    Then I learnt Floyd's cycle-finding algorithm: Two pointers, slow runs 1 step each time and fast runs 2, would definitely meet if there is a cycle.

    Well, they might meet any position in the circle, how would we find the entry point?


    What we know

    1. fast has run a+b+c+b steps, and slow with a+b steps
    2. fast runs double steps of slow

    We could conclude that

    a+b+c+b = 2*(a+b)
    # => a == c

    It means, steps between start point to circle entry equals steps between meet point to circle entry. So when we find the meet point, we could set a new pointer at start position, which would meet slow at the entry point.


      def find_duplicate(nums)
        slow, fast = nums[0], nums[ nums[0] ]
        # A loop guaranteed
        while slow != fast
          slow = nums[slow]
          fast = nums[ nums[fast] ]
        # Set a tag at start point. It would meet slow at the entry of circle.
        tag = 0
        while tag != slow
          tag  = nums[tag]
          slow = nums[slow]
        return slow


Log in to reply

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