Arrays Q3: Sorted Squared Array, Data Structure Problems Series, Part 1 (Python)

Data Science, AI and ML
#1

Arrays Q3: Sorted Squared Array, Data Structure Problems Series, Part 1 (Python)

In case anyone missed Q1 of Part 1 Arrays, then please visit below link for the same:

Now, Sorted Squared Array: 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.

Sample Input
    array = [1, 2, 3, 5, 6, 8, 9]

Sample Output
    [1, 4, 9, 25, 36, 64, 81]

Try solving it!

Hints are in the first comment.

UnitTest.py is in the second comment.

Solutions will be posted in 6 hours

#2
#3

Below are the hints to solve the above problem:

Note: See hints only if you are unable to solve the problem at least twice. Be astute.

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

UnitTest.py

import SortedSquaredArray as program
import unittest

class TestProgram(unittest.TestCase):
    
    def test_case_1(self):
        output = program.sortedSquaredArray([-2,1,2,3,4])
        # This should return True
        self.assertTrue(output == [1, 4, 4, 9, 16])

    def test_case_2(self):
        output = program.sortedSquaredArray2([-2,1,2,3,4])
        # This should return True
        self.assertTrue(output == [1, 4, 4, 9, 16])

    def test_case_3(self):
       output = program.sortedSquaredArray2([1, 2, 3, 5, 6, 8, 9])
        # This should return True
        self.assertTrue(output == [1, 4, 9, 25, 36, 64, 81])

    def test_case_4(self):
        output = program.sortedSquaredArray2([2])
        # This should return True
        self.assertTrue(output == [4])


if __name__ == '__main__':
	unittest.main()
#5

Solution: SortedSquaredArray.py

@Author: Anish Arya

Date 4th July, 2022

2 approaches applied: using 1 pointer and using 2 pointers

# First Approach: Using 1 pointer
def sortedSquaredArray(array):
    """This function will return the sorted squared array. e.g. [-5, -2, 2, 6] --> [4, 4, 25, 36]"""
    # @Author: Anish Arya
    # Time Complexity: O(nlogn)
    # Space Complexity O(n), where n is the size of the input array

    array_copy = array.copy()
    for idx in range(len(array_copy)):
        array_copy[idx] = array_copy[idx] ** 2
    return sorted(array_copy)
#6

Solution: SortedSquaredArray.py

@Author: Anish Arya

Date 10th July, 2022

2 approaches applied: using 1 pointer and

using 2 main pointers

# Second Approach: Using 2  main pointers
def sortedSquaredArray2(array):
    # @Author: Anish Arya
    # Time Complexity: O(n)
    # Space Complexity: O(n)

    sortedArray = [None for _ in array] # placeholder for sorted array
    end = sortedIdx = len(array) - 1
    front = 0
    valueToBeSquaredAndStored = None
    # maintaining 3 ptrs for comparing absolute values of front and end 
    # of the sorted input array to keep track of smallest and largest value and the remaining 1 ptr for storing the 
    # sorted squared value in the end of the Sorted Array.
    # Compare array[front] and array[end], then, store the store 
    # the max absolute element's squared value to the last element and move the ptrs accordingly
    while front <= end:
        if abs(array[front]) > abs(array[end]):
            valueToBeSquaredAndStored = array[front]
            front += 1
        else:
            valueToBeSquaredAndStored = array[end]
            end -= 1
        sortedArray[sortedIdx] = valueToBeSquaredAndStored ** 2
        sortedIdx -= 1
    return sortedArray