Question

LeetCode Link | 977. Squares of a Sorted Array | Easy

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

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in non-decreasing order.

Examples

Example 1

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2

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

Solution Approach

Method: Two-pointers

Constrains

  • Sorted array

The algorithm assumes that the input array nums is sorted in non-decreasing order. If this condition is not met, the output will not be correctly sorted. Thus, the function is not generalizable to unsorted arrays without additional steps (e.g., sorting the array first, which would increase the time complexity).

Concept Explanation

Array is sorted in non-decreasing order, it’s just that squaring a negative number might turn it into the largest number. Thus, the maximum value of an array after squaring is either on the far left or the far right of the array, not in the middle based on the abusolute value. At this point, you can consider using the two-pointer technique, where left points to the start position, and right points to the end position.

Initialize Pointers: Start with two pointers:

  • left at the beginning of the array (0 index).
  • right at the end of the array (nums.length - 1).

Fill the Result Array from the far end: Iterate array from two-end and pick a number form one of two sides until two pointers meets in the middle. Compare the absolute values of the numbers at the left and right pointers:

  • Square the larger absolute value and place it in the next available position from the end of the result array.
  • Move the corresponding pointer (left or right) inward.

Two Pointer Iteration

Use Array.prototype.unshift() to insert new number from the left which make sure the bigest always at the right.

Code

  • Time complexity: O(n)
  • Space complexity: O(n)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function sortedSquares(nums: number[]): number[] {
	let result: number[] = [];
	let left = 0, right = nums.length - 1;
	while (left <= right) {
		if (Math.abs(nums[left]) > nums[right]) {
			result.unshift(nums[left] ** 2);
			left++;
		} else {
			result.unshift(nums[right] ** 2);
			right--;
		}
	}
	return result;
}

Conclusion

In conclusion, the two-pointer technique should be considered when working with sorted arrays or when a problem can be structured to allow linear scanning from one or both ends of a sequence. This method shines in its simplicity, efficiency, and minimal space requirements, making it an excellent tool for a wide array of problems in competitive programming, interviews, and real-world applications. Always assess the nature of the problem and the data involved to decide if two pointers are the right approach, keeping in mind the problem’s requirements and constraints.