Problem

Given an array of numbers sorted in increasing order, return a new array containing squares of all the numbers of the input array sorted in increasing order.

Examples

Example 1:

1
2
3
4

Input: a[] = [-5, -2, -1, 0, 4, 6]
Output: [0, 1, 4, 16, 25, 36]
Explanation: After squaring, the array becomes [25, 4, 1, 0, 16, 36].
After sorting, it becomes [0, 1, 4, 16, 25, 36].

Example 2:

1
2

Input: nums = [-5, -4, -3, -2, -1]
Output: [1, 4, 9, 16, 25]

Example 3:

1
2

Input: nums = [1, 2, 3, 4, 5]
Output: [1, 4, 9, 16, 25]

Solution

Method 1 - Brute Force

A simple approach is to square the array and then sort it to get the final array. This approach will have an O(n log n) time complexity.

But given that the array is sorted, we can use the two-pointer approach to solve it in O(n) time-complexity.

Method 2 - Two Pointer Approach 1

If the array only had positive integers, then we could just square it and return the squared array as output. The only caveat with this question is that it has negative integers as well.

But if we can view the negative part and positive part of the array separately, and iterate over both the parts then we can get the squared array in O(n) time complexity.

Here is how the approach will work:

  • Find the index of the first non-negative number in the array.
  • Use two pointers to iterate over the array - one pointer will move forward to iterate over the non-negative numbers, and the other pointer will move backward to iterate over the negative numbers.
  • At any step, we check which pointer gives a smaller square. We add the smaller square to the output array and advance the corresponding pointer.
1
2

  ←pointer1  pointer2→
[-5, -2, -1, 0, 4, 6]

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

public int[] sortedSquares(int[] nums) {
	int n = nums.length;
	int[] squaredArr = new int[n];

	// Find the index of first non-negative element
	int firstNonNegIdx = n;

	for (int i = 0; i < n; i++) {
		if (nums[i] >= 0) {
			firstNonNegIdx = i;
			break;
		}
	}

	// Pointer to iterate over the negative elements
	int negItr = firstNonNegIdx - 1;
	// Pointer to iterate over the non-negative elements
	int posItr = firstNonNegIdx;

	int sqrIdx = 0;

	while (negItr >= 0 && posItr  <  n) {
		int negElementSquare = nums[negItr] * nums[negItr];
		int posElementSquare = nums[posItr] * nums[posItr];

		if (negElementSquare < posElementSquare) {
			squaredArr[sqrIdx++] = negElementSquare;
			negItr--;
		} else {
			squaredArr[sqrIdx++] = posElementSquare;
			posItr++;
		}
	}

	// Add the square of remaining negative elements to the output
	while (negItr >= 0) {
		squaredArr[sqrIdx++] = nums[negItr] * nums[negItr];
		negItr--;
	}

	// Add the square of the remaining positive elements to the output
	while (posItr < n) {
		squaredArr[sqrIdx++] = nums[posItr] * nums[posItr];
		posItr++;
	}

	return squaredArr;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 3 - Two Pointer Approach Simplified 🏆

An alternate two pointer approach is to use two pointers - one starting from the rightmost element of the array and the other starting from the leftmost element.

1
2

pointer1→                 ←pointer2
       [-5, -2, -1, 0, 4, 6]

At every step, check which pointer gives the highest square. Add the highest square to the output array (starting from right) and advance the corresponding pointer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int[] sortedSquares(int[] nums) {
	int n = a.length;
	int[] squaredArr = new int[n];
	int highestSquareIdx = n - 1;

	int left = 0;
	int right = n - 1;

	while (left <= right) {
		int leftSquare = a[left] * a[left];
		int rightSquare = a[right] * a[right];

		if (leftSquare > rightSquare) {
			squaredArr[highestSquareIdx--] = leftSquare;
			left++;
		} else {
			squaredArr[highestSquareIdx--] = rightSquare;
			right--;
		}
	}

	return squaredArr;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)