Find the Duplicate Number — Leetcode 287

Difficulty: Medium; Category: Matrix

Find the Duplicate Number - LeetCode

We know all the elements in nums are positive, ranging from 1 to n (the index of them in an array would be 0 to n-1).

We iterate over each element n through the array nums and mark its associated index as a negative number nums[abs(n)-1] *= -1, to indicate that we encountered the specific number.

Keep iterating over the nums, once the associated index of the element n is already a negative number if nums[abs(n)-1] < 0, which means that there has the same number n before this, then means we found the duplicate!

Why abs(n): Since we use negative marking, we must ensure that the element n is positive (i.e. if n is negative, then use its absolute value).

Solution

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        for n in nums:
            if nums[abs(n)-1] < 0:
                return abs(n)
            else:
                nums[abs(n)-1] *= -1

• Time complexity: O(n)
  One traversal over the nums array of size n
• Space complexity: O(1)
  All manipulation is done in place, so no additional storage is needed

Bonus

Set Mismatch — LeetCode 645

Set Mismatch - LeetCode

According to the problems, we need to return [duplicate, missing] of the array nums.

My first approach is like below:

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        nums_should_exist = [i for i in range(1, len(nums)+1)]
        nums_should_exist.extend(nums)
        total_count = Counter(nums_should_exist)
        result = []
        for val, count in total_count.items():
            if count == 3:
                result.insert(0, val)
            elif count == 1:
                result.append(val)
            if len(result) == 2:
                break
        return result

Make one array num_should_exist, which has numbers from 1 to n. And combine with given array nums. we could consider that only the missing number will occur once and only the duplicate number will occur three times while others all occur twice.

Create a list named result, if found duplicate, insert the number to the index 0 of the result, and if found missing, just append it to the result.

It’s easy to understand but use extra space of O(n) and time complexity would be O(n): Counter is O(n) and for loop of total_count is O(2n)

But we could use the same concept from the solution of Find the Duplicate Number — Leetcode 287, find the duplicate with the same method but instead of the return value, we store it as a valuable.

Then iterate the array again to find the missing number, because the associated index of all the numbers we encounter will be marked as negative, so we can know that when we encounter a positive number in the index, that is the missing number index we are looking for.

Remember that the associated index i needs to be incremented by one to be a missing value.

Solution

  class Solution:
      def findErrorNums(self, nums: List[int]) -> List[int]:
          dup = -1
          missing = -1
          for n in nums:
              if nums[abs(n)-1] < 0:
                  dup = abs(n)
              else:
                  nums[abs(n)-1] *= -1
          for i in range(len(nums)):
              if nums[i] > 0:
                  missing = i+1
          return [dup, missing]

• Time complexity: O(n)
  Two traversals over the nums array of size n are done
• Space complexity: O(1)
  Constant extra space is used

REFERENCE
https://leetcode.com/problems/set-mismatch/solutions/127759/set-mismatch/?orderBy=most_votes