Space complexity in python

Python
#1

hi I got a really simple problem "write a function that reorders a list so that all lowercase letter appear first and afterward uppercase letters " for example [‘K’, ‘f’, ‘H’, ‘T’, ‘m’] will turn to [‘m’, ‘f’, ‘H’, ‘T’, ‘K’] (letters order doesn’t matter as long as lowercase letters appear first)
so the time complexity of my solution is O(n) but what is the space complexity?(required to be O(1)).
also if someone could tell me how to know more in general how to tell the space complexity of a function?

def sortt(lst):
    new_lst=[]
    for letter in lst:
        if ord(letter)>=ord("a") and ord(letter) <=ord("z"):
            new_lst.append(letter)
    for letter in lst:
        if ord(letter) >=ord("A") and ord(letter)<=ord("Z"):
            new_lst.append(letter)
    return new_lst
print(sortt(['K', 'f', 'H', 'T', 'm']))
#2

You’re creating a new list that will grow to the same size as the input, so you’ve got O(n) space complexity as well. You get O(1) space complexity by swapping elements in place, since you wouldn’t be allocating a list, just using some constant number of variables. The exercise is almost certainly looking for an in-place algorithm as the solution.

1 Like
#3

@chuckadams thank you for your answer , i couldnt find a way to keep time complexity n and make space complexity 1 . is that even possible?

#4

Yep, it’s doable in O(n) time and O(1) space. You’ll need to keep two indexes into the array and swap items. Make those two indexes meet in the middle.

2 Likes
#5

@chuckadams I tried again today using your tip and this is what I got .
is it O(1) space complexity and O(n) in time?
I’m not sure if variable y takes space or not…i am storing him

def sortt(lst):
   x=0
   y=len(lst)-1
   while x<y:
       if ord(lst[x]) >=ord("A") and ord(lst[x])<=ord("Z"):
           lst[x],lst[y]=lst[y],lst[x]
           y-=1
       else:
           x+=1
   return lst
print(sortt(['K', 'f', 'H','s','k', 'T', 'm','T','A','a']))
#6

Variables count as space, but if you’re storing scalars in them, then their space usage is constant. So if you’re not allocating any new arrays or objects, then you’ve got O(1) space complexity. Technically it’s using O(n) space because of the input, but space complexity is always about calculating additional space used.

That looks like the solution I’m familiar with. For an extra challenge try your hand at the Dutch National Flag Problem which is a variant of this problem with three values instead of two.

1 Like
#7

OK thx for the tips and help!