[LeetCode] 977. Squares of a Sorted Array

977. Squares of a Sorted Array 투포인터

풀이_#1

투포인터 활용 / 시간복잡도 O(N) 공간복잡도 O(1) (리턴값을 위한 리스트는 공간복잡도 계산에 포함되지 않음)

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        low = 0
        high = n - 1
        writeIdx = n - 1
        r = [0] * n


        while(writeIdx >= 0):
            left = nums[low] ** 2
            right = nums[high] ** 2
            if (left <= right):
                r[writeIdx] = right
                high -= 1
            else:
                r[writeIdx] = left
                low += 1
            writeIdx -= 1
        return r

풀이_#2

deque 를 활용한 투포인터 활용
Time O(N) , Space O(N)
우아하고 직관적이며 유지보수가 쉬운 코드

from collections import deque
class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        r = [0] * n
        queue = deque(nums)
        writeIdx = n - 1

        while (queue):
            # deque 는 stack + queue 이기때문에 어쩃든 인덱스로 접근가능하다.
            head = queue[0] ** 2
            tail = queue[-1] ** 2

            if (head <= tail):
                r[writeIdx] = tail
                queue.pop()
            else:
                r[writeIdx] = head
                queue.popleft()           
            writeIdx -= 1
        return r