977. Squares of a Sorted Array

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

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]

Explanation: Sorted Squares of a Sorted Array

✅ Problem Summary:

Given a sorted array nums (in non-decreasing order), return a new array where:

• Each number is squared.
• The resulting array is also sorted in non-decreasing order.

❓ Why Not Just Square and Sort?

You could square each number and then sort the result. But that would be O(n log n) time due to sorting.

However, since the input is already sorted, we can do better using two pointers to get an O(n) solution.

🚀 Optimal Solution: Two Pointer Technique

🔍 Strategy:

• Negative numbers, when squared, might be larger than positive ones (e.g., -4² = 16 > 3² = 9).
• Use two pointers:
  • One starting at the beginning (left)
  • One at the end (right)
• Compare absolute values and insert the larger square at the end of the result array (from right to left).

🔧 Implementations

🔹 Go

func sortedSquares(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    left, right := 0, n-1
    pos := n - 1

    for left <= right {
        leftVal := nums[left] * nums[left]
        rightVal := nums[right] * nums[right]

        if leftVal > rightVal {
            result[pos] = leftVal
            left++
        } else {
            result[pos] = rightVal
            right--
        }
        pos--
    }

    return result
}

🔸 PHP

function sortedSquares($nums) {
    $n = count($nums);
    $result = array_fill(0, $n, 0);
    $left = 0;
    $right = $n - 1;
    $pos = $n - 1;

    while ($left <= $right) {
        $leftVal = $nums[$left] * $nums[$left];
        $rightVal = $nums[$right] * $nums[$right];

        if ($leftVal > $rightVal) {
            $result[$pos] = $leftVal;
            $left++;
        } else {
            $result[$pos] = $rightVal;
            $right--;
        }
        $pos--;
    }

    return $result;
}

🔹 C#

public class Solution {
    public int[] SortedSquares(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        int left = 0, right = n - 1;
        int pos = n - 1;

        while (left <= right) {
            int leftVal = nums[left] * nums[left];
            int rightVal = nums[right] * nums[right];

            if (leftVal > rightVal) {
                result[pos--] = leftVal;
                left++;
            } else {
                result[pos--] = rightVal;
                right--;
            }
        }

        return result;
    }
}