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