Squares of a Sorted Array

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

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

Examples:

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].

Input: nums = [-7,-3,2,3,11]

Output: [4,9,9,49,121]

Input: nums = [0,2,4,6,8]

Output: [0,4,16,36,64]

Constraints

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

Editorial

Intuition:

The array is sorted in non-decreasing order. The largest square will come from the element with the largest absolute value, which could be at either end. By using two pointers from both ends, we can fill the result array from the end with the largest squares first.

Approach:

Initialize an output array res of length n (same as nums).
Set pointers: left = 0, right = n-1, and pos = n-1.
While left <= right:
- Compute leftSquare = nums[left] * nums[left] and rightSquare = nums[right] * nums[right].
- If leftSquare > rightSquare, set res[pos] = leftSquare and increment left; else set res[pos] = rightSquare and decrement right.
- Decrement pos.
After the loop, for C++ and Java, copy res back to nums. For Python and JavaScript, return res.

#include <vector>
using namespace std;

class Solution {
public:
    void sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        int left = 0, right = n - 1, pos = n - 1;
        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            if (leftSquare > rightSquare) {
                res[pos] = leftSquare;
                left++;
            } else {
                res[pos] = rightSquare;
                right--;
            }
            pos--;
        }
        nums = res;
    }
};
class Solution {
    public void sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int left = 0, right = n - 1, pos = n - 1;
        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            if (leftSquare > rightSquare) {
                res[pos] = leftSquare;
                left++;
            } else {
                res[pos] = rightSquare;
                right--;
            }
            pos--;
        }
        for (int i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }
}
class Solution:
    def sortedSquares(self, nums):
        n = len(nums)
        res = [0] * n
        left, right = 0, n - 1
        pos = n - 1
        while left <= right:
            left_sq = nums[left] ** 2
            right_sq = nums[right] ** 2
            if left_sq > right_sq:
                res[pos] = left_sq
                left += 1
            else:
                res[pos] = right_sq
                right -= 1
            pos -= 1
        return res
class Solution {
    sortedSquares(nums) {
        const n = nums.length;
        const res = new Array(n);
        let left = 0, right = n - 1, pos = n - 1;
        while (left <= right) {
            const leftSquare = nums[left] * nums[left];
            const rightSquare = nums[right] * nums[right];
            if (leftSquare > rightSquare) {
                res[pos] = leftSquare;
                left++;
            } else {
                res[pos] = rightSquare;
                right--;
            }
            pos--;
        }
        return res;
    }
}

Complexity Analysis:

Time Complexity: O(n), because we traverse the array once with two pointers.

Space Complexity: O(n), for the auxiliary array used to store the result.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories