Two Pointers - Squares of a Sorted Array

Given an integer array sorted in non-decreasing order, return an array of the squares of each number, sorted in non-decreasing order.

Input: [-4,-1,0,3,10] → Output: [0,1,9,16,100]

Input: [-7,-3,2,3,11] → Output: [4,9,9,49,121]

Two pointers from both ends. The largest square is at either end. Fill result array from right to left.

lo=0, hi=n-1, pos=n-1.
While lo<=hi: compare abs(nums[lo]) with abs(nums[hi]).
Place the larger square at result[pos--], advance corresponding pointer.

class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] result = new int[n]; int lo = 0, hi = n - 1, pos = n - 1; while (lo <= hi) { int left = nums[lo] * nums[lo], right = nums[hi] * nums[hi]; if (left > right) { result[pos--] = left; lo++; } else { result[pos--] = right; hi--; } } return result; } }

Time Complexity: O(N)
Space Complexity: O(N) for result