[Leet Code] Two Pointers (투포인터): 283. Move Zeroes - Easy

* Two Pointers 알고리즘 설명

 

문제 / 코드

 

 개인적으로 label은 easy인데 swap하는 방법을 생각을 못해 medium보다 오래 걸렸던 문제. 아직도 a, b = b, a로 구현하는 코드가 익숙하지 않다.

 그리고 문제 푸는 시간을 정확하게 기록하는 습관을 들여야하는데 계속 까먹는다..

 

Description

 move all zeros in the array to the end of array. Other integers keep it's order, just move foward to keep the length of the original input array.

 Requirements - Do in-place w/o making a copy of the array.

 

How to solve

 The point is find the index of first zero before non-zero integer & the index of first non-zero integer after the first zero and swap the values of those. We need to use two pointers algorithm cuz there're 2 runners (tracing zero's position & rotating the array)

 

Simple way

 Rotating the array, checking the value, count 0. If there were zereos, the non-zero integers next to 0 needs to move the amount of 0 before them.

 In conclusion, we can solve this problem by adding 1 to count if value is 0, or swap the values of index and index-count if the value is not 0.

 

Two pointers

 First of all, we need to set a pointer for zero. The initial value is 0 because we don't know where the first zero is. This pointer is a slow runner.

 Starting to rotate the array by index from 1, the index is a fast runner because zero should be before non-zero before swapping the values. (We don't need to check 0 because whether the first value is 0 or not, swapping is not needed).

 

4 cases can happen in the loop:

1. array[index] == 0 & array[pointer] == 0

    Both values are 0 so no actions are needed. Just pass the loop, index will be increased by the loop.

 

2. array[index] == 0 & array[pointer] != 0

    This means zero(fast runner is pointing) is next to non-zero(slow runner is pointing) so swaping is not needed. If swapping happened before, slow runner should be pointing zero. Conversely, array[pointer] != 0 means array[pointer] have never found 0 before.

    Therefore, we need to add 1 to pointer to check the next value is zero or not at the next loop.

 

3. array[index] != 0 & array[pointer] == 0     

     Now the index of the first zero before non-zero integer and the index of the first non-zero integer after the first zero is founded, swap the two values.

     After swaping, the pointer is poiniting the position of the first zero, so we can use this at the following loops.

 

4. arrray[index] != 0 & array[pointer] != 0

     It tells there wasn't 0 before (as explained at 3.) so swaping isn't needed but the slow runner needs to run to find 0. So add 1 to pointer.

 

Pseudo Code

TC = O(n) for both but simple way's leetcode test result was a bit faster (not sure both were tested with the same test cases)

Simple way

Two pointers