Square every element in the array, then sort the result. This works because sorting guarantees non-decreasing order regardless of negative inputs.
Use two pointers at both ends of the array. Since the input is sorted, the largest squares must come from the extremes (most negative or most positive). Compare absolute values, place the larger square at the end of the result, and move the pointer inward. Build the result from right to left.
""" 0977.1 - Solution 1 - Brute Force (Sort) """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def sortedSquares(self, nums: List[int]) -> List[int]:
"""Squares of a Sorted Array Function"""
return sorted(x * x for x in nums)
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().sortedSquares([-4, -1, 0, 3, 10]))
print(Solution().sortedSquares([-7, -3, 2, 3, 11]))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0977.2 - Solution 2 - Two Pointer Approach """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def sortedSquares(self, nums: List[int]) -> List[int]:
"""Squares of a Sorted Array Function"""
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
left_sq = nums[left] ** 2
right_sq = nums[right] ** 2
if left_sq > right_sq:
result[pos] = left_sq
left += 1
else:
result[pos] = right_sq
right -= 1
pos -= 1
return result
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().sortedSquares([-4, -1, 0, 3, 10]))
print(Solution().sortedSquares([-7, -3, 2, 3, 11]))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()