Crack the Backend

Problem Statement

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number, also sorted in non-decreasing order. The array can contain negative numbers.

After squaring, the smallest value might be in the middle (e.g. [-4,-1,0,3,10] → squares [16,1,0,9,100]; sorted [0,1,9,16,100]). So we cannot simply square and sort in one direction; we use two pointers from the two ends (largest absolute values) and fill the result from the end (largest squares first).

Key Observations

The largest square is either nums[0]^2 (if all non-negative) or nums[n-1]^2 (if all non-positive) or the larger of the two ends (if mixed). So we put two pointers at left=0 and right=n-1, compare |nums[left]| and |nums[right]| (or compare nums[left]^2 and nums[right]^2). The larger square goes at the end of the result array. We fill the result from index n-1 down to 0.
Each step we place one square and move the pointer that contributed it. O(n) time, O(1) extra space (excluding the output array).

Approach

High-level: left=0, right=n-1, result array res of length n, index k=n-1. While left <= right: if |nums[left]| >= |nums[right]|, res[k--] = nums[left]*nums[left], left++; else res[k--] = nums[right]*nums[right], right--. Return res.

Steps:

int[] res = new int[nums.length]; left=0, right=nums.length-1, k = nums.length-1.
While left <= right: if nums[left]*nums[left] >= nums[right]*nums[right], res[k--] = nums[left]*nums[left], left++; else res[k--] = nums[right]*nums[right], right--.
Return res.

Implementation

Java

public int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int left = 0, right = n - 1, i = n - 1;

    while (left <= right) {
        if (Math.abs(nums[left]) >= Math.abs(nums[right])) {
            result[i--] = nums[left] * nums[left];
            left++;
        }
        else {
            result[i--] = nums[right] * nums[right];
            right--;
        }
    }

    return result;
}

Test Cases

Example 1

Input

nums = [-4,-1,0,3,10]

Expected

[0,1,9,16,100]

Explanation

Squares sorted.

Complexity Analysis

Time: O(n).
Space: O(1) excluding output.

Follow-ups

In-place: possible with O(1) extra space but trickier.