Squared Deviations

Easytwo pointersAlso known as Squares of a Sorted Array

A greenhouse sensor records how far each reading is from the ideal temperature. Too cold gives a negative number, too warm a positive one. The log is already sorted from lowest to highest, for example [-7, -3, 0, 2, 5].

The climate system cares about the size of each miss, and it punishes big misses more, so it uses the square of each deviation. It wants those costs sorted from smallest to largest.

Your task

Write squaredSorted(deviations). Return a new list with the square of every number, sorted from smallest to largest.

Aim for a single pass. The input is sorted; use that.

squaredSorted(deviations: int[]) → int[]

Examples

Example 1

Input

deviations = [-7, -3, 0, 2, 5]

Output

[0, 4, 9, 25, 49]

Why

The squares in input order are 49, 9, 0, 4, 25. Sorted: 0, 4, 9, 25, 49. Notice the biggest squares came from the two ends of the input: -7 and 5.

Example 2

Input

deviations = [-4, -1, 0, 3, 10]

Output

[0, 1, 9, 16, 100]

Why

Squares in order: 16, 1, 0, 9, 100. The largest, 100, comes from the right end. The next largest, 16, comes from the left end.

Constraints

0 ≤ deviations.length ≤ 10,000
-10,000 ≤ deviations[i] ≤ 10,000
deviations is sorted in non-decreasing order.

Start with brute force

Square every number, then sort the result. It is two lines of code and it is correct.

It costs O(n log n) because of the sort, and it ignores the fact that the input was already sorted. The sorted input is a gift: it tells you where the big values are.

Hints

0 of 4 shown

Hint 1
Squaring the numbers breaks the sorted order. But where in the input do the largest squares come from?
Hint 2
The biggest square is always at one of the two ends: either the most negative number or the most positive one. The middle holds the numbers closest to zero.
Hint 3
So you can find the answer from largest to smallest. Compare the squares at the two ends, and the bigger one is the largest value still to place.
Hint 4
Use left and right pointers at the ends, and fill the result from the back. Each step, write the larger of the two end squares at the current back position and move that pointer inward.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

The largest square is always at one end of the input, so build the answer from the largest down.

Trace [-7, -3, 0, 2, 5]. The result has 5 slots, filled from the back:

Ends are -7 and 5. 49 > 25, so slot 4 = 49. Move left to -3.
Ends are -3 and 5. 9 < 25, so slot 3 = 25. Move right to 2.
Ends are -3 and 2. 9 > 4, so slot 2 = 9. Move left to 0.
Ends are 0 and 2. 0 < 4, so slot 1 = 4. Move right to 0.
Both pointers are on 0. Slot 0 = 0. Result: [0, 4, 9, 25, 49].

Each step places exactly one value and moves exactly one pointer, so the loop runs n times.

Reference solution

function squaredSorted(deviations) {
  const n = deviations.length;
  const result = new Array(n);
  let left = 0, right = n - 1;
  for (let pos = n - 1; pos >= 0; pos--) {
    const l = deviations[left] * deviations[left];
    const r = deviations[right] * deviations[right];
    if (l > r) {
      result[pos] = l;
      left++;
    } else {
      result[pos] = r;
      right--;
    }
  }
  return result;
}

def squared_sorted(deviations):
    n = len(deviations)
    result = [0] * n
    left, right = 0, n - 1
    for pos in range(n - 1, -1, -1):
        l = deviations[left] ** 2
        r = deviations[right] ** 2
        if l > r:
            result[pos] = l
            left += 1
        else:
            result[pos] = r
            right -= 1
    return result

TimeO(n)One loop that places one value per step.

SpaceO(n)The result list. Apart from it, only two pointers.

Learn the idea: Two Pointers Arrays

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code