[Leet Code] Two Pointers (투포인터): 977.Squares of a sorted array - Easy

* Two Pointers 알고리즘 설명

 

문제 / 코드

 

Description

  Return an array, sorted in non-decreasing order, of the squares of each value in the input array.

 

How to solve

 The point is if there was/were neg numbers, the order of values can be changed from the input array after squaring.   So we can't just return the original order of the input array but we need to compare the square of each value and change the value's index if needed.

 

 The square of the first value is always smaller than the square of the last value if it's not a negative number. If it's a neg number, it's squre is the biggest number of the squares of the negative numbers in the input array and the last value's squre is the biggest number of the squares of the positive numbers in the input array. Therefore, we need to compare the squares of the first and the last value and input the bigger one at the last index of a new array which has same length of the input array.

 3 cases are possible:

    1. First > Last:

        It tells that the first value was a neg num and it's square is bigger than the squre of the biggest number among the pos nums. That means the sqare of the first value is the biggest number among the squres of each values in the input array.

        So we put the square of the first value at the last index of a new array,  and

          new array idx: -1

          first value idx: +1

        We still don't know which one is bigger btw the second value and the last value, so no need to move the index of the last value sothat we can compare the square of the second value and the last value

    2. First < Last:

        In this case, whether the first value is neg or pos, the square of the last value is the biggest one among the squres of each values in the input array. So we just can put the squre of the last value at the last index of a new array,  and

           new array idx: -1

           last value idx: -1

        We still don't know which one is bigger btw the second value and the last value, so no need to move the index of the last value.

        Same as 1, We still don't know which one is bigger btw the input[-1] value and the first value, so no need to move the index of the first value sothat we can compare the square of input[-1] value and the first value.

    3. First == Last:

         We regard this case same as either < or > because the array is sorted in non-decreasing order.

    4. Terminates condition:

         We need to input the value until the pointers point the same one last value(=the smallest value in the input array). Therefore, terminate the loop when the index of first value is bigger than the last value.

 

Pseudo Code

티스토리 UI가 너무 거지같아서 캡쳐로 대체..

TC = O(n)