Sorted Squared Array | Rust
Write a function that takes a sorted array and returns a array with squared values in ascending order (Sorted Squared values).
If the initial Array wasn’t sorted then the best we could do is O(n log(n)), as we have to traverse through every element once which takes O(n), then to sort the array with best sorting algorithm which takes O(n log(n)) on average. Since we are given a Sorted Array as input we could use that to get this done in O(n) Time and Space complexity.
As we know that negative values squared becomes positive, thus squares are in increasing order both sides, we can use this fact to build our result array from largest to smallest, just by comparing and moving the start and end pointers.
Code available here.
We begin by initializing the start index (0) and end index (length of the array-1) values, initialize a empty array with size of the input array, and an index i with length of the input array -1. if start value is greater, we increment the start index else if end value is greater, we will decrement the end index. we will continue this until our start index less than or equal to end index. Every time we update a value in the result array, we will decrement index i.
Thus works because we are taking the next largest value very time and updating the result array from the end.
