Micron drift

A gauge hands you measurements already in order. Squaring them throws that order away — except at the two ends, where it does not.

The problem

A bore gauge on a machine shop floor measures every finished part and files it by signed error in microns: negative when the bore came out undersize, positive when it came out oversize, zero when it is on nominal. Because the rig files as it measures, the log arrives sorted from most undersize to most oversize.

Scrap cost is not proportional to the error but to its square — a bore 7 microns under costs the same rework as one 7 microns over, and four times what a 3-micron error costs. The shift report wants the squared errors listed from cheapest to dearest.

Input. deviations — a list of integers sorted non-decreasing, the signed micron error of each part in the order the gauge filed it.

Output. A list of the squared errors, sorted non-decreasing.

Example.

deviations = [-7, -3, -1, 0, 2, 5]   ->  [0, 1, 4, 9, 25, 49]

The squares in log order are 49, 9, 1, 0, 4, 25 — not sorted at all. The cheapest part sits in the middle of the log, and the dearest sits at the far left end.

A second example, where every part came out undersize:

deviations = [-9, -6, -2]   ->  [4, 36, 81]

Here the output is the log read backwards. So the answer is neither the log's order nor its reverse in general; it depends on where zero falls.

Constraints.

• 1 <= len(deviations) <= 10^4
• -10^4 <= deviations[i] <= 10^4
• deviations is sorted non-decreasing.

Hints

Approach

Brute force

Square every reading and sort the result. That is n multiplications and an n log n sort — for 10⁴ parts, around 130,000 comparisons on top of work you did not need to do, since the input was handed to you in order already.

The insight

In a sorted log the largest square is always at one end or the other, never in the middle.

Sorting puts the most negative reading first and the most positive last, so the two extremes of magnitude are exactly the two ends. Squaring is monotone in magnitude, so whichever end has the bigger absolute value carries the biggest square. Drop that end and the same statement holds for what remains — the remaining slice is still sorted, so its extremes are still its ends. That recursion is the whole algorithm, and it fills the answer from the back.

Algorithm

1. Make a result list of the same length.
2. Set left = 0, right = n - 1, and write = n - 1.
3. While left <= right, compare deviations[left] * deviations[left] with deviations[right] * deviations[right].
4. Write the larger square at write, move the pointer it came from inward, and decrement write.
5. When the pointers cross, the result is complete.

Complexity

Time O(n) — each reading is examined once and written once, so the pointers make n moves in total. Space O(n) for the output list; the working state is three integers, so the extra space is O(1).

Solution

"""Micron drift — two pointers walking a sorted log inward from both ends."""


def solve(deviations):
    n = len(deviations)
    ranked = [0] * n
    left, right, write = 0, n - 1, n - 1
    # Invariant: deviations[left..right] is still sorted, so the largest square
    # among the parts not yet placed is at one of its two ends.
    while left <= right:
        low_sq = deviations[left] * deviations[left]
        high_sq = deviations[right] * deviations[right]
        if low_sq > high_sq:
            ranked[write] = low_sq
            left += 1
        else:
            ranked[write] = high_sq
            right -= 1
        write -= 1
    return ranked

TESTS = [
    (([-7, -3, -1, 0, 2, 5],), [0, 1, 4, 9, 25, 49]),
    (([-9, -6, -2],), [4, 36, 81]),
    (([1, 2, 3, 8],), [1, 4, 9, 64]),
    (([0],), [0]),
    (([-4, -4, -4],), [16, 16, 16]),
    (([-10000, 10000],), [100000000, 100000000]),
]

Pitfalls

• Comparing the readings instead of their magnitudes. -7 < 2, so a value comparison picks 2 as the larger and writes 4 where 49 belongs. Compare squares, or absolute values.
• Filling the result from the front. The smallest square sits nearest zero, which is somewhere in the middle of the log, and you cannot find it from the ends without a scan. Only the largest is pinned to an end, so writing must go back to front.
• Using left < right as the loop condition. The two pointers meet on one final reading, and a strict comparison never writes it — the middle slot of the output keeps its initial value, usually a stray 0.
• Assuming an all-negative log just needs reversing. It does, but an all-positive one does not, and a mixed log needs neither. The pointers handle all three without a special case.

Variants

• Crate digging — two pointers again, but walking two sorted lists forward instead of one list inward.
• Hull trim — sorting first is the setup rather than the gift, and the inward walk sits inside another loop.