Sweaty Imposter

Squares of a Sorted Array

EasyTwo PointersNeetCode 150JuniorOpen on LeetCodeUpdated

You're given an integer array nums sorted in non-decreasing order, which may include negative numbers. Return a new array holding the square of every element, also sorted in non-decreasing order. Squaring can reorder values, because a negative number like -4 squares to 16, which is bigger than the square of 3.

Examples

nums = [-4,-1,0,3,10] returns [0,1,9,16,100]

In the original order the squares are 16, 1, 0, 9 and 100. Sorted, they become 0, 1, 9, 16, 100, with the square of -4 landing between those of 3 and 10.

nums = [-7,-3,2,3,11] returns [4,9,9,49,121]

-3 and 3 both square to 9, so 9 appears twice. -7 squares to 49, which still comes before 121.

Constraints

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

Hints

Hint 1

After squaring, where in the original sorted array can the largest value be?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

In a sorted array the largest square is always at one of the two ends, since it comes from the most negative or the most positive value. Put left and right at the ends, compare their squares, write the larger into result from the back, and move that pointer inward. Repeating until the pointers cross fills result from largest to smallest, with only a few index variables beyond the output. Squaring then sorting would be O(n log n).

Time

O(n)

Space

O(1)

Pitfall

Looping while left < right instead of left <= right leaves the last element unwritten, so [1,2] returns [0,4]. And fill from the back: the largest square is always at an end, but the smallest can sit in the middle.

Solutions

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