287. Find the Duplicate Number

Problem Statement

link: LeetCode.cn LeetCode

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example:

Input: nums = [1,3,4,2,2] Output: 2

Input: nums = [3,1,3,4,2] Output: 3

Solution Approach

To find the duplicate number within the given array nums, we utilize Floyd’s Tortoise and Hare algorithm, also known as the cycle detection algorithm.

Algorithm

1. Initialize two pointers, slow and fast, pointing to the first element and the element at the index specified by the value of the first element, respectively.
2. Traverse through the array using the pointers: Increment slow by one step. Increment fast by two steps.
3. Repeat until slow and fast meet at the same index, indicating the presence of a cycle. Reset slow to the starting point (index 0), and keep fast at its current position.
4. Move both pointers one step at a time until they meet again. The meeting point is the duplicate number within the array.

Implement

    class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
      slow, fast = nums[0], nums[nums[0]]
      while slow != fast:
          slow = nums[slow]
          fast = nums[nums[fast]]
      slow = 0
      while slow != fast:
          slow = nums[slow]
          fast = nums[fast]
      return slow
    
       

    
    

Twitter  facebook  Email