Space complexity of dictionary python

Question

Its a leethcode Question

https://leetcode.com/problems/find-the-duplicate-number/

Here they are saying :

You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n^2). There is only one duplicate number in the array, but it could be repeated more than once.

So in my code i am creating a dictionary using Collection in python.

How my code is satisfying the this line "You must use only constant, O(1) extra space." and what do they mean by this line are they taking about Space complexity. Below is my code, which clears all testcase.

from collections import Counter 

class Solution:
    
    def findDuplicate(self, nums: List[int]) -> int:
        
        dict1=Counter(nums)
        
        for i in dict1:
            if(dict1[i]>1):
                return(i)

Please help. Thanks in advance.

user_2726773 · Answer

Generally, a dictionary has always space complexity of O(N), because it depends on the number of elements of your array.

A space complexity of O(1) means that you have the same number of pointers regardless of the array size. For instance, if you use a boolean variable in your search algorithm to get your duplicate, this would imply O(1).

Side note:

Another thing is the runtime complexity, which in the case of a dictionary, is O(1) since they are based on hash-tables where you only need a key to get the value. Oppositely, to find a particular value in a list, the runtime complexity is O(N), since in the worst case you have to iterate all the elements.

user_13008439 · Answer

Dictionaries take O(n) space, so your solution takes O(n) space and violates the O(1) space requirement.

This is an old LeetCode problem, when LeetCode's focus was on job interviews, where such requirements can come up and be discussed (and used to be discussed in LeetCode's forum). It was never enforced by the LeetCode system, that's why your solution gets accepted despite violating the requirement. By now LeetCode is competition-focused and has become just like any other coding challenges site: It only matters whether you get your solution accepted, now how. They still don't (can't?) enforce such space requirements, and I think their new questions don't ask for something like that anymore. I miss the old days.

user_6553328 · Answer

Your main question has been answered already. For this problem, we'd binary search:

class Solution:
    def findDuplicate(self, nums):
        lo, hi = 0, len(nums) - 1
        mid = (lo + hi) // 2
        while hi - lo > 1:
            count = 0
            for num in nums:
                if mid < num <= hi:
                    count += 1
            if count > hi - mid:
                lo = mid
            else:
                hi = mid
            mid = (lo + hi) // 2
        return hi

References

For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2} in there.

Space complexity of dictionary python

3 Answers

References