Note: Come up with a linear solution, since that is what you would be asked to do in an interview.
You have a sorted
array of integers. Write a function that returns a sorted array containing the squares of those integers.
array = [-6, -4, 1, 2, 3, 5], the output should be
sortedSquaredArray(array) = [1, 4, 9, 16, 25, 36].
The array of squared integers from
[36, 16, 1, 4, 9, 25]. When sorted, it becomes:
[1, 4, 9, 16, 25, 36].
- [time limit] 4000ms (py)
- [input] array.integer array
A sorted array of integers.
1 ≤ array.length ≤ 104,
-104 ≤ array[i] ≤ 104.
- [output] array.integer
A sorted array of integers composed of the squared integers from the input
We start from both ends and compare the smallest and largest numbers in the array. (The reason we need to do this is we may have negative numbers whose squared value will be greater than some of the positive numbers.) Every time we pick something from the start, we move the index forward, every time we pick something from the end, we move it backward.
We add the number we pick to a new array. The array is now in non-increasing (or decreasing) order. We return the reversed array.