1
impl Solution {
2
  pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
3
    // The code works without this, but it removes a
4
    // lot of useless allocations for a base case
5
    if nums.len() == 1 {
6
      return vec![i32::pow(nums[0], 2)];
7
    }
8

9
    // We'll use this for inserting later
10
    let mut location = nums.len();
11

12
    // Pre-allocate so we can start indexing from the end
13
    let mut output = vec![0; location];
14

15
    // These are our markers for the 2 ends of the array
16
    let mut left = 0 as usize;
17
    let mut right = nums.len() - 1;
18

19
    // We're only going to compute each value once
20
    let mut computed_left = i32::pow(nums[left], 2);
21
    let mut computed_right = i32::pow(nums[right], 2);
22

23
    while left != right {
24
      // Every loop we're moving one spot further to the left
25
      location -= 1;
26
      // Every loop iteration we check which value is larger and
27
      // put that at the end of the output vector that we pre-allocated
28
      if computed_left > computed_right {
29
        output[location] = computed_left;
30
        left += 1;
31
        computed_left = i32::pow(nums[left], 2);
32
      } else {
33
        output[location] = computed_right;
34
        right -= 1;
35
        computed_right = i32::pow(nums[right], 2);
36
      }
37
    }
38
    // Could do either one, because at this point they should be the
39
    // same index / value
40
    output[0] = computed_right;
41
    return output;
42
  }
43
}