What THEY Do Not Teach YOU In Data Science! - Data Structures Problem #4 By Anish Arya (Machine Learning and Reinforcement Learning Consultant)

Data Science, AI and ML
#1

Hello Aspiring Real Data and Decision Scientists,

In case you missed, the introduction to the series of problems, please go through the following discussion:
.
.

What THEY Do Not Teach YOU In Data Science! - By Anish Arya (Machine Learning and Reinforcement Learning Consultant)

.
.
PROBLEM #3 STATEMENT: Problem Level: Very Easy

Sorted Squared Array

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]
#2
#3

Solution: Time Complexity: O (n * log(n)), where n is the number of elements in the array or length of the input array. Space Complexity: O (n)

def sortedSquaredArray(inputArray):
	init_sequence_list = []
	for element in inputArray:
		init_sequence_list.append(element**2)
	init_sequence_list.sort()
	return init_sequence_list
#4

Solution 2:

# O(n) time | O(n) space - where n is the length of the input array
def sortedSquaredArray(array):
    sortedSquares = [0 for _ in array]
    smallerValueIdx = 0
    largerValueIdx = len(array) - 1
    for idx in reversed(range(len(array))):
        smallerValue = array[smallerValueIdx]
        largerValue = array[largerValueIdx]
        if abs(smallerValue) > abs(largerValue):
            sortedSquares[idx] = smallerValue * smallerValue
            smallerValueIdx += 1
       else:
            sortedSquares[idx] = largerValue * largerValue
            largerValueIdx -= 1
    return sortedSquares
#5

Hints:

Hint 1:
While the integers in the input array are sorted in increasing order, their squares won’t necessarily be as well, because of the possible presence of negative numbers.

Hint 2:
Traverse the array value by value, square each value, and insert the squares into an output array. Then, sort the output array before returning it. Is this the optimal solution?

Hint 3:
To reduce the time complexity of the algorithm mentioned in Hint #2, you need to avoid sorting the output array. To do this, as you square the values of the input array, try to directly insert them into their correct position in the output array.

Hint 4:
Use two pointers to keep track of the smallest and largest values in the input array. Compare the absolute values of these smallest and largest values, square the larger absolute value, and place the square at the end of the output array, filling it up from right to left. Move the pointers accordingly, and repeat this process until the output array is filled.