Squares of Sorted Array — Problem Statement & Solution Guide

ArraysEasyTwo Pointers

TimeO(n)

SpaceO(1) auxiliary

Problem Description

You are provided with a non-decreasing sequence of integers. Your task is to compute the square of each element and return a new sequence containing these squared values, arranged in non-decreasing order.

Because the input is already sorted, the largest absolute values reside at the two ends of the array. A naive approach of squaring all elements and then sorting them would be inefficient. Instead, leverage the sorted property to construct the result in linear time by comparing the magnitudes of the elements at the boundaries and placing the larger square at the end of the result array, working backwards.

Input: A 0-indexed array nums of length n, where nums[i] <= nums[i+1] for all valid i.

Output: An array result of length n such that result[i] = nums[k]^2 for some permutation k, and result is sorted in non-decreasing order.

DSA Pattern Breakdown

"Squares of Sorted Array"

easy

WHY DOES IT MATTER?

The two‑pointer from both ends pattern turns a seemingly O(n log n) problem into O(n) by exploiting sorted order, a technique that recurs in many interview problems such as container with most water, sorted squares, and merging intervals.

OPTIMIZATION CHALLENGE

The insight is that the maximum absolute value resides at the array's extremes, allowing you to place the largest square at the result's tail without sorting, effectively performing a linear merge of two sorted sequences (negative side reversed, positive side forward).

REAL-WORLD CONNECTION

Think of scanning a sorted log file for the most extreme timestamps: you can start from both the earliest and latest entries and converge inward, avoiding a full scan of the entire dataset.

During the interview, write the two‑pointer loop first, then fill the result array from the back; this prevents off‑by‑one errors and makes the code easier to reason about.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1) auxiliary

Core Theory — Why This Approach?

The input array is sorted in non‑decreasing order, but after squaring each element the order can change because negative numbers become positive. A naïve solution would square every element and then invoke a general‑purpose sort, which costs O(n log n) time. However, the key observation is that the largest squared value must come from either the leftmost (most negative) or the rightmost (most positive) element, since absolute value dictates magnitude after squaring. By using a two‑pointer technique—one starting at the beginning and one at the end—we can compare the squares of these two candidates, place the larger one at the end of a result array, and move the corresponding pointer inward. Repeating this process fills the result array from back to front in linear time, achieving O(n) time and O(1) auxiliary space (excluding the output array). This approach exemplifies the "two‑pointer from both ends" pattern, which leverages existing order to avoid extra sorting.

Why the naïve method fails on large inputs is twofold: first, the O(n log n) sorting step becomes a bottleneck for arrays with millions of elements; second, it discards the valuable information that the original array is already sorted, leading to unnecessary work. The optimal paradigm embraces the sorted property, transforms the problem into a merge‑like operation, and thus attains optimal linear complexity while preserving stability and memory efficiency.

Interview Questions on This Problem

Q1How would you modify the two‑pointer solution if the input array were sorted in non‑increasing order?

Reverse the direction of the pointers: start one pointer at the beginning (largest positive) and the other at the end (most negative). Compare squares, but now fill the result array from the front because the smallest squares will appear first. The logic remains the same—pick the smaller square and move the corresponding pointer.

Q2Can you solve the problem in‑place without using extra O(n) space?

In‑place is not feasible while preserving the original order because squaring can change relative positions; you would need to overwrite values that are still needed for comparison. The optimal trade‑off is O(n) time with O(1) extra space plus the output array.

Q3What would be the impact on time and space complexity if the input array could contain 64‑bit integers and you needed to avoid overflow?

You would need to use a larger numeric type (e.g., 128‑bit or arbitrary‑precision) for the squares, but the algorithmic complexity stays O(n) time and O(1) extra space. The only change is handling the data type safely during multiplication.

Examples

Example 1

Input

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

Output

[0, 1, 9, 16, 25]

Explanation: Squares are [16, 1, 0, 9, 25]. Comparing ends: |5| > |-4|, so 25 goes to end. Next, |5| is consumed, compare |-4| vs |3|: 16 > 9, so 16 goes to position 3. Compare |-4| vs |3|: 16 already placed, now compare |-4| vs |3| again? No, pointers move. Left=-4, Right=3. 16>9, place 16. Left=-1, Right=3. 9>1, place 9. Left=-1, Right=0. 1>0, place 1. Left=0, Right=0. Place 0. Result: [0, 1, 9, 16, 25].

Example 2

Input

nums = [-10, -5, -2, 1, 4]

Output

[1, 4, 25, 100, 16]

Example 3

Input

nums = [0, 0, 0, 0]

Output

[0, 0, 0, 0]

Explanation: All elements are zero. Squaring any zero yields zero. The sorted order of zeros is trivially [0, 0, 0, 0]. The two-pointer approach will fill the result array with zeros from the end to the beginning, resulting in the same array.

Example 4

Input

nums = [-3, -2, -1, 2, 3]

Output

[1, 4, 4, 9, 9]

Explanation: Squares: [9, 4, 1, 4, 9]. Sorted: [1, 4, 4, 9, 9]. L=0 (-3), R=4 (3). 9=9. Place 9 at end (index 4). R=3. L=0 (-3), R=3 (2). 9>4. Place 9 at index 3. L=1. L=1 (-2), R=3 (2). 4=4. Place 4 at index 2. R=2. L=1 (-2), R=2 (-1). 4>1. Place 4 at index 1. L=2. L=2 (-1), R=2 (-1). 1=1. Place 1 at index 0. Result: [1, 4, 4, 9, 9].

Constraints

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

Optimal Approach & Strategy

Use two pointers at the array's ends, compare the squares, and fill a new array from the back with the larger square, moving the appropriate pointer inward each step. This yields a sorted squares array in linear time.

Brute Force Approach

Square each element of the array and then sort the resulting array using a standard O(n log n) sorting algorithm. This approach ignores the original ordering information.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) process.exit(0);
const n = data[0];
const nums = data.slice(1, 1 + n);

function sortedSquares(nums) {
    const res = new Array(nums.length);
    let left = 0, right = nums.length - 1, pos = nums.length - 1;
    while (left <= right) {
        const leftSq = nums[left] * nums[left];
        const rightSq = nums[right] * nums[right];
        if (leftSq > rightSq) {
            res[pos--] = leftSq;
            left++;
        } else {
            res[pos--] = rightSq;
            right--;
        }
    }
    return res;
}

const result = sortedSquares(nums);
console.log(result.join(' '));

#include <bits/stdc++.h>
using namespace std;

vector<int> sortedSquares(const vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n);
    int left = 0, right = n - 1, pos = n - 1;
    while (left <= right) {
        long long leftSq = 1LL * nums[left] * nums[left];
        long long rightSq = 1LL * nums[right] * nums[right];
        if (leftSq > rightSq) {
            res[pos--] = static_cast<int>(leftSq);
            ++left;
        } else {
            res[pos--] = static_cast<int>(rightSq);
            --right;
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> nums(n);
    for(int i=0;i<n;++i) cin>>nums[i];
    vector<int> res = sortedSquares(nums);
    for(size_t i=0;i<res.size();++i){
        if(i) cout << ' ';
        cout << res[i];
    }
    cout << '\n';
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static int[] 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 leftSq = nums[left] * nums[left];
            int rightSq = nums[right] * nums[right];
            if (leftSq > rightSq) {
                res[pos--] = leftSq;
                left++;
            } else {
                res[pos--] = rightSq;
                right--;
            }
        }
        return res;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Integer> all = new ArrayList<>();
        String line;
        while ((line = br.readLine()) != null) {
            line = line.trim();
            if (line.isEmpty()) continue;
            for (String s : line.split("\\s+")) {
                all.add(Integer.parseInt(s));
            }
        }
        if (all.isEmpty()) return;
        int n = all.get(0);
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = all.get(i + 1);
        int[] res = sortedSquares(nums);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (i > 0) sb.append(' ');
            sb.append(res[i]);
        }
        System.out.println(sb.toString());
    }
}

import sys

data = list(map(int, sys.stdin.read().strip().split()))
if not data:
    sys.exit()

n = data[0]
nums = data[1:1+n]

def sorted_squares(nums):
    n = len(nums)
    res = [0] * n
    left, right, pos = 0, n - 1, n - 1
    while left <= right:
        left_sq = nums[left] * nums[left]
        right_sq = nums[right] * nums[right]
        if left_sq > right_sq:
            res[pos] = left_sq
            left += 1
        else:
            res[pos] = right_sq
            right -= 1
        pos -= 1
    return res

result = sorted_squares(nums)
print(' '.join(map(str, result)))

const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) process.exit(0);
const n = data[0];
const nums = data.slice(1, 1 + n);

function sortedSquares(nums) {
    const res = new Array(nums.length);
    let left = 0, right = nums.length - 1, pos = nums.length - 1;
    while (left <= right) {
        const leftSq = nums[left] * nums[left];
        const rightSq = nums[right] * nums[right];
        if (leftSq > rightSq) {
            res[pos--] = leftSq;
            left++;
        } else {
            res[pos--] = rightSq;
            right--;
        }
    }
    return res;
}

const result = sortedSquares(nums);
console.log(result.join(' '));

Asked in Top Tech Interviews

AccentureZomato

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Squares of Sorted Array Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Squares of Sorted Array — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor