CODEWITHSUNDEEP
pythonalgorithmbig-otime-complexity
Mridul Birla
Mridul Birla

Reputation: 124

Finding complexity of my Code

I am trying to solve the question the following question taken from leetcode(https://leetcode.com/problems/first-missing-positive/)

Given an unsorted integer array, find the first missing positive integer.

For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space. 

class Solution(object):
    def firstMissingPositive(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
        for i in range(len(nums)):
            while nums[i] != i+1:
                if nums[i]<=0 or nums[i]>len(nums) or nums[i]==nums[nums[i]-1]:
                    break
                else:
                    temp=nums[nums[i]-1]
                    nums[nums[i]-1]=nums[i]
                    nums[i]=temp
        for i in range(len(nums)):
           if nums[i]!=i+1:
               return i+1
        return len(nums)+1
b=Solution()
print b.firstMissingPositive([1,1])

I am sure this solution has has complexity of O(n^2). But still many online solutions have used same algorithm.

Can anyone explain how this code has O(n) complexity

Upvotes: 2

Views: 213

Answers (1)

amit
amit

Reputation: 178431

This solution is indeed O(n).

First, note that the if clause in the main loop is happening at most n times (at most once per value of i).

In addition, the else clause is also happening O(n) times, since if a value is already in its position, you never change its location again (guaranteed from the if condition).

Thus, in the main loop, there are at most n entries to the if clause, and at most n entries to the else clause, giving us total run time of O(n) for this loop.

The second loop (which is not nested in the first one), is O(n) as well, so total complexity is O(n)

Upvotes: 3

Related Questions