Squares of a Sorted Array
Two pointers (fill from end)
TimeO(n)SpaceO(n)Good solution
Single pass over the array. Each element is compared and written once. Optimal for this problem.
Animation
Two pointers: compare |nums[i]| vs |nums[j]|, place larger square at p (fill from end).
Input nums
0
-4
1
-1
2
0
3
3
4
10
Output arr
0
—
1
—
2
—
3
—
4
—
Speed:
i (left) j (right) p (write)