[Leet Code] Two Pointers (투포인터): 189. Rotate Array - Medium (What "modify in-place" means on Leetcode?)

문제 / 코드

 

사실 이 문제도 미디움치고는 정말 빨리 풀었다. 나중에 나오는 링크드 리스트 미디움에 비하면 정말.. 이건 이지다.

릿코드에서 이 문제를 투포인터로 분류해놨는데 나는 왜 이 문제가 투 포인터인지 한참을 생각했다 (심지어 투 포인터로 푸는 방법이 따로 있는지 계속 생각함). 원리를 이해하니 두 점을 찍고 푼다는 점에서 투 포인터가 맞는데 기존의 투 포인터 푸는 방식과 다르다는 이유로 투 포인터라고 생각을 안했다니, 역시 고정관념에서 벗어나는 것이 참 힘들다.

 

Leetcode said it's a Two pointers problem, I was confused how it can be done with two pointers  with O(1) extra space (well, it wasn't mandatory but... you know) because normal two pointers problems need start, end and mid & while loop.

However, this problem is also solved by setting two points and moving those, just needed to be one line expression to meet the requirement(in-placement modification). So it can be called two pointers anyway.

too hard to think out of the box :(

 

Description

Rotate the given array to the right by k steps, where k is non-negative.

Do not return the array but modify it in place.

What modify an obj in place means on Leetcode?

Test cases call the object in your answer by the id, not the name of it. Therefore, in this case, the id of the given array nums should be same after it rotates.

As you can see the above snap shot, if we define nums with nums =, id(nums) will be changed because this expression means we want to create a new reference. Always keep in mind that variable = value (a sliced list is same with values in Python)means creating a new reference. That's why the program recognizes nums as a new list in spite of we define it with the same name.

On the other hand, nums[:] = doesn't means you want to create whole new nums but will keep the current container, just assign new values. So the pointer keeps referencing a current heap memory space. That's why nums[:] = expression keeps the previous id.

Therefore, you can put any type of object at right side of nums = expression but you only can put iterable items at the right side of nums[:] = expression.

In conclusion, when Leet Code problem asks to modify an object "in place", you needs to be aware of a "reference".

 

How to solve

First of all, if k is mutiple of the length of nums, it means k is full rotation and nums will be as is after rotation. In other words, rotation by remainder after dividing k by the length of nums will be same with the result after rotation by k.

So to make k smaller than the length of nums, change it to the reaminder after dividing it by len(nums).

We can devide the list into the two parts: Not rotated part, rotated part

• The original list: Not rotated part + rotated part
• The answer: rotated part + Not rotated part
• After we rotate the given list by k, indexes will be changed as below.
• Not Rotated part: From nums[0] to the last not rotated element (nums[len(n)-k-1])

Before Rotating	After Rotating
0	k+1
1	k+2
2	k+3
...	...
len(n)-k-2	len(n)-2
len(n)-k-1	len(n)-1

• Rotated part: From len(n)-k to len(n)-1

Before Rotating	After Rotating
len(n)-k	0
len(n)-k+1	1
...	...
len(n)-3	k-2
len(n)-2	k-1
len(n)-1	k

 

So we can define the nums after rotating as below:

nums[len(nums)-k : len(n)-1] + nums[0:len(n)-k-1]

[0:len(n)-1] is same with [:] so above can be changed to below:

nums[-k:] + nums[:-k]

 

Pseudo Code

* actually below is not a pseudo code, just an answer.

k=%len(nums)
# you can add if k==0:pass
nums[:] = nums[-k:] + nums[:-k]