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
