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

Software Development
#1

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]

Problem 1 Link:
https://discuss.boardinfinity.com/t/problem-1-two-numbers-target-sum-array-problem-o-n-time-and-space-complexity/12453

#2

Scatchpad For Reference

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

#3

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