 # Problem 2: Sorted Square Array: Array Problem - O(n) Optimal Time Complexity

Problem Statement:

Write a function that takes in a non-empty array of integers that are sorted in ascending order and returns a new array of the same length with the squares of the original integers also sorted in ascending order.

Optimal Time Complexity: O(n), where n is the length of the input array.

Sample Input 1:
array = [-5, -2 , 5, 6, 8, 9]
Sample Output 1:
sortedOutput = [4, 25, 25, 36, 64, 81]

Sample Input 2:
array = [5, 5, 8, 9]
Sample Output 2:
sortedOutput = [25, 25, 64, 81]

array = [-2, -1, 0, 1]

[0, 0, 0, 0]… len = 4

O/P = [0, 1, 1, 4]

startIdx = 0
endIdx = len - 1 ====> 3

I)
if |-2| <= |1| arrStartVal <= arrEndVal

else:
[0, 0, 0, 4]
sortedArray[idx] = arrStartVal * arrStartVal
startIdx += 1 …1

II)
if |-1| <= |1| arrStartVal <= arrEndVal
if abs(array[startIdx]) <= abs(array[endIdx]):
sortedArray[idx] = arrEndVal * arrEndVal
endIdx -= 1

Solution:

``````def sortedSquaredArray(array):
# Write your code here. // Anish Arya
startIdx, endIdx = 0, len(array) - 1
sortedArray = [0 for _ in array]
for idx in reversed(range(len(array))):
arrStartVal = array[startIdx]
arrEndVal = array[endIdx]
if abs(arrStartVal) <= abs(arrEndVal):
sortedArray[idx] =  arrEndVal * arrEndVal
endIdx -= 1
else:
sortedArray[idx] = arrStartVal * arrStartVal
startIdx += 1
return sortedArray
``````