Algorithm

Sorted Squared Array

  Problem Given an array integers in ascending order Return a new output array that contains square of integer of input array...

Written by Vortana Say · 1 min read

 

Problem

Given an array integers in ascending order

Return a new output array that contains square of integer of input array in ascending order

Note: do not modify input array and must create new output array

Example:

Input: nums = [-7,-5,-4,3,6,8,9]

Output: [9,16,25,36,49,64,81]

 

 

 

Solution 1: Square and sort

Traverse the input array. Square each element and assign to the output array. Sort the out put array to get the wanted result.

Example

Input: nums = [-7,-5,-4,3,6,8,9]

Output: outPutArray = [9,16,25,36,49,64,81]

Explanation:

index = 0; element = -7

Square of -7 = 49

outPutArray = [49]

index = 1; element = -5

Square of -5 = 25

outPutArray = [49,25]

index = 2; element = -4

Square of -4 = 16

outPutArray = [49,25,16]

index = 3; element = 3

Square of 3 = 9

outPutArray = [49,25,16,9]

index = 4; element = 6

Square of 6 = 36

outPutArray = [49,25,16,9,36]

index = 5; element = 8

Square of 8 = 64

outPutArray = [49,25,16,9,36,64]

index = 6; element = 9

Square of 9 = 81

outPutArray = [49,25,16,9,36,64,81]

Then we sorted the outPutArray, we get [9,16,25,36,49,64,81]

Complexity Analysis:

  • Time Complexity: O(nlogn), where N is the length of the input array.

    • We traverse through array for each number – O(n)
    • sort – O(nlogn)
  • Space Complexity: O(n) – we create array list for output array

Kotlin

Solution 2: two pointers

We know:

  • if a > b => square of a > square of b
  • we get positive value from square of negative 

We assign first element to left pointer (LP), and we assign last element to right pointer (RP). We assign index = last position of the array (size – 1 because array position start with 0)

If absolute value of LP >= RP (|LP| > |RP|)

We square LP then add it to the index position of the output array

Decrease the index value 

Move LP to the next value (on the right)

Else if absolute value of LP < RP (|LP| < |RP|)

we square RP then add it to the index position of the output array

Decrease the index value

Move RP to the next value (on the left)

Example

Input: nums = [-7,-5,-4,3,6,8,9]

Output: outPutArray = [9,16,25,36,49,64,81]

Explanation:

LP = -7, RP = 9 and index = 6 (LAST position = size -1)

|-7| < |9|

Square of 9  = 81

Add 81 to outputArray[6] // outputArray= [81]

index = index – 1 = 5

LP = -7, RP = 8 and index = 5

|-7| < |8|

Square of 8  = 64

Add 64 to outputArray[5] // outputArray= [64,81]

index = index – 1 = 4

LP = -7, RP = 6 and index = 4

|-7| > |6|

Square of 7  = 49

Add 49 to outputArray[4] // outputArray= [49,64,81]

index = index – 1 = 3

LP = -5, RP = 6 and index = 3

|-5| < |6|

Square of 6  = 36

Add 36 to outputArray[3] // outputArray= [36,49,64,81]

index = index – 1 = 2

LP = -5, RP = 3 and index = 2

|-5| > |3|

Square of 5  = 25

Add 36 to outputArray[2] // outputArray= [25,36,49,64,81]

index = index – 1 = 1

LP = -4, RP = 3 and index = 1

|-4| > |3|

Square of 4  = 16

Add 16 to outputArray[1] // outputArray= [16,25,36,49,64,81]

index = index – 1 = 0

LP = 3, RP = 3 and index = 0 // LP and RP on the same position 

|3| = |3|

Square of 3  = 9

Add 9 to outputArray[0] // outputArray= [9,16,25,36,49,64,81]

return outputArray= [9,16,25,36,49,64,81] (no sort needed)

Complexity Analysis:

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

  • Space Complexity: O(n) – we create array list for output array

Kotlin