2

I'm doing this exercise:

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

My solution that does not work:

def reverseString(s: List[str]) -> None:
    """
    Do not return anything, modify s in-place instead.
    """
    s = s[::-1]

Correct answer:

def reverseString(s: List[str]) -> None:
    """
    Do not return anything, modify s in-place instead.
    """
    s[::] = s[::-1]

Why does my solution not work?

mkrieger1
  • 19,194
  • 5
  • 54
  • 65
ChinaMahjongKing
  • 155
  • 1
  • 7
  • 2
    Does this answer your question? [How does assignment work with list slices?](https://stackoverflow.com/questions/10623302/how-does-assignment-work-with-list-slices) – mkrieger1 Apr 01 '22 at 09:26
  • 1
    `s[:] = s[::-1]` works here too – Learning is a mess Apr 01 '22 at 09:32
  • In your solution, you are assigning to a local variable `s`. In the "correct solution" you are trying to access the slice of a variable `s`. Since there is no local variable `s` yet, it uses `s` from the outer scope and modifies that instead. – Mortz Apr 01 '22 at 09:36

3 Answers3

2

The expression s[::-1] will create a new list with its elements reversed.

Then,

s[:] = s[::-1]

...causes the new list to be copied into the address space previously occupied by the original list whereas...

s = s[::-1]

Assigns a reference to the reversed list to a local variable s.

As an aside and because I don't know what "O(1) extra memory" means, it's worth noting that the functionally correct answer does require duplication of the memory used by the original list whereas...

def reverseString(s):
    i = 0
    j = len(s) - 1
    while i < j:
        s[i], s[j] = s[j], s[i]
        i += 1
        j -= 1

...does not because it's swapping elements in situ

DarkKnight
  • 19,739
  • 3
  • 6
  • 22
  • O(1) extra memory means that no matter how big the array is, the memory needed for the operation is always the same. If, for example, you copied the array to another variable, then reverted it, that would make that new variable the same size of the original one, and if the original grows, the new one also grows at the same rate, making it O(n). Big O notation in a nutshell, and basically what you've explained with your example and the duplication of memory. – Shinra tensei Apr 01 '22 at 09:47
  • @Shinratensei Thank you for explaining that which is very interesting because the accepted answer (i.e., with s[::-1]) is presumably **not** O(1) due to duplication of the address space – DarkKnight Apr 01 '22 at 09:58
  • As far as I understand, in `s[::] = s[::-1]` the same array in memory is being sliced twice so no extra memory should be used right? – Shinra tensei Apr 01 '22 at 10:03
  • @Shinratensei No. Because s[::-1] will generate a new list before any copying is done - unless there's some kind of optimisation within the Python interpreter which I doubt – DarkKnight Apr 01 '22 at 10:07
1

You have to do an in-place modification.

S[::] = is doing the modification on actual memory byte of s while s = s[::-1] is pointing the variable name s and not doing any modification.

Isaac
  • 155
  • 9
1

Reassigning the list inside the function will not change the original list, s[:] = or s[::] = slice-assigns, replacing what was previously in the list

Bouabdallah khaled
  • 43
  • 4