Wednesday 25 November 2020

What is the time and space complexity of the following program? - leetcode 1291

enter image description here

Can somebody pls tell me what the time and space complexity of my answer is?

I think the time complexity is O(nlogn) assuming this is how long the sorted function takes. I'm also assuming that the double for loop takes constant O(1) time because the length of the numbers string does not change.

I think the space complexity is O(n) where n is the number of elements in our results array. But, I'm unsure of this answer.

Any help is appreciated.

class Solution(object):
    def sequentialDigits(self, low, high):
        """
        :type low: int
        :type high: int
        :rtype: List[int]
        """
        numbers = "123456789" #every possible substring of this string represents the set of valid numbers that we can have
        
        results = []
        
        #get every substring from the 'number' string 
        for i in range(len(numbers)):
            for j in range(i, len(numbers)):
                # sustring in range i to j
                subString = numbers[i:j+1]
                
                #convert it to an integer
                subString= int(subString)
                
                #if its within the required range, add it to our array
                if low<=subString<=high:
                    results.append(subString)
                    
        return sorted(results)


from What is the time and space complexity of the following program? - leetcode 1291

No comments:

Post a Comment