Squares in sorted order
The biggest is always at one of the ends. About 10 minutes.
Squaring scrambles the order
Square every number in −4, −1, 0, 3, 5 and you get 16, 1, 0, 9, 25. The list was sorted, but the negative numbers turned into big squares.
Here's the useful bit: the biggest square always comes from one of the two ends, either the most negative number or the most positive one. Whichever is further from zero wins.
−4 against 5: 5 is further from zero. Its square, 25, goes in the last box, and the right finger moves in.
Fill the answer from the back
Make an answer list of the same length and fill it from its last box backwards, biggest square first. Put a finger at each end of the numbers. Each time, compare the two ends, write the bigger square into the next empty box from the back, and move that finger inwards.
Keep going until the fingers pass each other. The number where they meet needs a place too.
n = len(nums)
result = [0] * n
left, right = 0, n - 1
for pos in range(n - 1, -1, -1):
if abs(nums[left]) > abs(nums[right]):
result[pos] = nums[left] ** 2
left += 1
else:
result[pos] = nums[right] ** 2
right -= 1
return resultThe numbers are −7, −2, 1, 6. Which square goes into the last box of the answer?
- A49, from −7
- B36, from 6
- C4, from −2
Show the answer
49, from −7. −7 is further from zero than 6, so its square is the biggest.
Squares in sorted order
You get numbers sorted from smallest to largest. Some may be negative. Return a new list with the square of every number, sorted from smallest to largest. Try it without sorting.
nums = [-4, -1, 0, 3, 5] → [0, 1, 9, 16, 25]
0 ≤ n ≤ 10,000 · sorted ascending · −10,000 ≤ each value ≤ 10,000