977. Squares of a Sorted Array

Problem 977

https://leetcode.com/problems/squares-of-a-sorted-array/ Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Solution

• Sort

  • Time Complexity: O(NlogN), where NN is the length of A.

  • Space Complexity: O(N).

• Tow pointer

  • Time Complexity: O(N), where N is the length of A.

  • Space Complexity: O(N).

note: 1 <= A.length <= 10000

collection

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        Ans = collections.deque()
        r,l = len(A)-1, 0
        while( l <= r ):
            left, right = A[l]**2, A[r]**2
            if left > right:
                Ans.appendleft( left )
                l += 1
            else:
                Ans.appendleft( right )
                r -= 1
        
        return list(Ans)

list-append

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        Ans = [0]*(len(A))
        r,l = len(A)-1, 0
        while( l <= r ):
            left, right = A[l]**2, A[r]**2
            if left > right:
                Ans[r-l] = left
                l += 1
            else:
                Ans[r-l] = right
                r -= 1
        
        return Ans

sort

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        #B = [ a*a for a in A ]
        #B.sort()
        return sorted( [ a*a for a in A ] )