Squared deviations in sorted order

The largest square comes from one of the two ends, because the most negative and the most positive values have the biggest magnitudes. Compare the ends, write the bigger square at the back of the output, and move that pointer inward. Filling from the back gives sorted output in one O(n) pass; the output takes O(n) space and the rest is O(1).

Squaring then sorting is O(n log n): correct, and a fine first answer to mention.

Filling from the back is the trick: the biggest square is easy to find, the smallest is not.

With all non-negative input the squares are already sorted; the two-pointer version handles every case without branching.

def sorted_squares(dev: list[int]) -> list[int]:
    out = [0] * len(dev)
    lo, hi = 0, len(dev) - 1
    for pos in range(len(dev) - 1, -1, -1):
        if abs(dev[lo]) > abs(dev[hi]):
            out[pos] = dev[lo] * dev[lo]
            lo += 1
        else:
            out[pos] = dev[hi] * dev[hi]
            hi -= 1
    return out

Common mistakes

• Filling from the front, which requires finding the value closest to zero first.
• Comparing raw values instead of absolute values or squares at the two ends.

Say 'the biggest square is at an end' first. That observation is the whole solution.

Follow-up questions

Think of your answer first, then open the hint.

1. What if the input were unsorted?

   Show hint

   Then O(n log n) is the honest answer: sort the squares.

2. How would you merge without extra space?

   Show hint

   You need the output list anyway; the O(1) refers to extra working space.