# 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.

# Sample Input
# array = [1, 2, 3, 5, 6, 8, 9]
# Sample Output
# [1, 4, 9, 25, 36, 64, 81]

# Solution 1: Time complexity: O(n), Space complexity: O(n) space including
# output, O(1) otherwise.
# The problem comes from the fact that negative numbers have positive squares
# and so, an array such as [-4, -3, -2, 1] would result in [1, 4, 9, 16].
# So, use two pointers on the array and check whose absolute value is lower,
# and append the square of that element to the array. Finally, move the right
# pointer to left or left pointer to right based on the element chosen.
def sorted_squared_array(arr):
	result = [0 for _ in arr]
	left = 0
	right = len(arr) - 1
	current = len(arr) - 1
	while left <= right:
		if abs(arr[left]) > abs(arr[right]):
			result[current] = arr[left] ** 2
			left += 1
		else:
			result[current] = arr[right] ** 2
			right -= 1
		current -= 1
	return result

print(sorted_squared_array([1, 2, 3, 4]))
print(sorted_squared_array([-4, -3, -2, 1]))