Leetcode Daily Challenge - Find the Duplicate Number

Today's challenge on Leetcode in based on a problem oftenly asked in the interviews. It is a medium level problem and I came up with a couple of solutions for the problem using Sorting approach and Two Pointer Approach.

Find the Duplicate Number

Intuition

The intuition is pretty straightforward as compared to the actual implementation. However, the time space trade off is the actual crunch in this problem as there can be various ways to solve the the best one is the foremost demand always.

Logic: (Approach a)

This approach is the easiest of all as it takes the list and sorts it to check if we can find the element in O(nlogn), for the obvious sorting reasons.

Algorithm:

1. Sort the input list
2. Traverse through list
     if nums[i] == nums[i+1]
       return nums[i]
3. Return -1    

Logic (Approach b)

The approach can be applied with the use of Floyd Circle algorithm which can be bifurcated into two parts. First where it is checked if there exists a cycle in the list.

Further, it is made sure with the use of indexing for the element that is repeated.

Code No. 1

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                return nums[i]

Code No. 2

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        turtle = 0
        hare = 0
        while True:
            if turtle >= len(nums):
                turtle = 0
            if hare >= len(nums):
                hare = 0
            if nums[turtle] == nums[hare] and turtle != hare:
                return nums[turtle]
            turtle += 1
            hare += 1
        return None