Simple Python solution having space complexity O(n) and time complexity O(n),


  • 0
    P

    It is a game of numbers. List has numbers from 1 to n, we can use the sum of first n natural numbers to find the missing and duplicated number.

    class Solution(object):
        def findErrorNums(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            n = len(nums)
            should_be = n*(n+1)//2
            
            missing = should_be - sum(list(set(nums)))
            duplicated = sum(nums)-sum(list(set(nums)))
            return [duplicated, missing]
    

  • 0

    how do you think set(nums) takes O(1) space?


  • 0
    P

    I may have missed it. Its corrected now.
    Thanks for point it out.


Log in to reply
 

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