Squares of a Sorted Array

🎯

Squares of a Sorted Array

easyTWO_POINTERAmazonGoogleFacebook

Imagine you have a list of elevations along a hiking trail, sorted from lowest to highest, and you want to analyze the squared elevation changes for some physics calculations.

💡 This problem involves transforming a sorted array by squaring each element and then returning a new array sorted by these squares. Beginners often struggle because squaring negative numbers can disrupt the original order, so a naive approach might fail to maintain sorted order.

📋

Problem Statement

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

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

💡

Example

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

Output[0,1,9,16,100]

Squares are [16,1,0,9,100], sorting them gives [0,1,9,16,100]

• All positive numbers → output is squares in same order
• All negative numbers → output is squares in reverse order
• Single element array → output is square of that element
• Array with zeros → zeros remain zeros after squaring

⚠️

Common Mistakes

Sorting the squared array without leveraging input sorted property

Slower O(n log n) solution, interviewer may consider incomplete optimization

✅ Use two pointers to build the output in O(n) time

Filling output array from start instead of end in two-pointer approach

Output array is not sorted correctly

✅ Fill output array from the last index backwards

Not handling negative numbers correctly when comparing absolute values

Incorrect squares chosen, wrong output order

✅ Compare absolute values of elements at pointers, not raw values

Modifying input array in place without clarifying constraints

May cause side effects or violate problem constraints

✅ Clarify if in-place modification is allowed; otherwise, use extra space

🧠

Brute Force (Square then Sort)

💡 This approach is the most straightforward and helps beginners understand the problem by directly applying the problem statement without optimization.

Intuition

Square every element and then sort the resulting array to get the final sorted squares.

Algorithm

1. Initialize an empty result array.
2. Iterate over each element in the input array.
3. Square the element and append it to the result array.
4. Sort the result array and return it.

💡 This algorithm is easy to understand but inefficient because it does not leverage the input array's sorted property.

</>

Code

def sortedSquares(nums):
    result = []
    for num in nums:
        result.append(num * num)
    result.sort()
    return result

# Driver code
if __name__ == '__main__':
    nums = [-4,-1,0,3,10]
    print(sortedSquares(nums))

Line Notes

result = []Initialize a list to store squared values

for num in nums:Iterate over each number in the input array

result.append(num * num)Square the current number and add it to result

result.sort()Sort the squared numbers to get the final sorted array

import java.util.*;
public class Solution {
    public static int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = nums[i] * nums[i];
        }
        Arrays.sort(result);
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {-4,-1,0,3,10};
        System.out.println(Arrays.toString(sortedSquares(nums)));
    }
}

Line Notes

int[] result = new int[n];Create array to hold squared values

for (int i = 0; i < n; i++) {Loop through input array indices

result[i] = nums[i] * nums[i];Square each element and store

Arrays.sort(result);Sort the squared array to get final output

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> sortedSquares(vector<int>& nums) {
    vector<int> result;
    for (int num : nums) {
        result.push_back(num * num);
    }
    sort(result.begin(), result.end());
    return result;
}

int main() {
    vector<int> nums = {-4,-1,0,3,10};
    vector<int> res = sortedSquares(nums);
    for (int val : res) cout << val << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<int> result;Initialize vector to store squared values

for (int num : nums) {Range-based loop over input array

result.push_back(num * num);Square and append each element

sort(result.begin(), result.end());Sort the squared values for final output

function sortedSquares(nums) {
    const result = [];
    for (const num of nums) {
        result.push(num * num);
    }
    result.sort((a, b) => a - b);
    return result;
}

// Test
console.log(sortedSquares([-4,-1,0,3,10]));

Line Notes

const result = []Create array to hold squared numbers

for (const num of nums)Iterate over each element in input

result.push(num * num)Square and add to result array

result.sort((a, b) => a - b)Sort array numerically to get sorted squares

⏱

Complexity

TimeO(n log n)

SpaceO(n)

We square all n elements (O(n)) and then sort the resulting array (O(n log n))

💡 For n=1000, this means about 1000*log2(1000) ≈ 10,000 operations, which is acceptable but not optimal.

Interview Verdict: Accepted but not optimal

This approach works but is inefficient because it ignores the sorted property of the input array.

🧠

Two Pointers from Ends (Merge-like)

💡 This approach leverages the sorted property of the input array and the fact that the largest squares come from the largest absolute values at the ends.

Intuition

Use two pointers at the start and end of the array, compare absolute values, and fill the output array from the end to the start.

Algorithm

1. Initialize two pointers: left at 0, right at n-1.
2. Create an output array of the same size.
3. Iterate from the end of the output array to the start:
4. Compare absolute values at left and right pointers, square the larger, place it at current position, and move that pointer.

💡 This algorithm is efficient but requires careful pointer management and filling the output array backwards.

</>

Code

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    for i in range(n - 1, -1, -1):
        if abs(nums[left]) > abs(nums[right]):
            result[i] = nums[left] * nums[left]
            left += 1
        else:
            result[i] = nums[right] * nums[right]
            right -= 1
    return result

# Driver code
if __name__ == '__main__':
    nums = [-4,-1,0,3,10]
    print(sortedSquares(nums))

Line Notes

n = len(nums)Store length for convenience

result = [0] * nPre-allocate output array for efficiency

left, right = 0, n - 1Initialize pointers at array ends

for i in range(n - 1, -1, -1)Fill output array from end to start

import java.util.*;
public class Solution {
    public static int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0, right = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            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;
    }
    public static void main(String[] args) {
        int[] nums = {-4,-1,0,3,10};
        System.out.println(Arrays.toString(sortedSquares(nums)));
    }
}

Line Notes

int[] result = new int[n];Allocate output array to store squares

int left = 0, right = n - 1;Set pointers at both ends of input

for (int i = n - 1; i >= 0; i--) {Fill output from last index backwards

if (Math.abs(nums[left]) > Math.abs(nums[right])) {Compare absolute values to decide which square is larger

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n);
    int left = 0, right = n - 1;
    for (int i = n - 1; i >= 0; i--) {
        if (abs(nums[left]) > abs(nums[right])) {
            result[i] = nums[left] * nums[left];
            left++;
        } else {
            result[i] = nums[right] * nums[right];
            right--;
        }
    }
    return result;
}

int main() {
    vector<int> nums = {-4,-1,0,3,10};
    vector<int> res = sortedSquares(nums);
    for (int val : res) cout << val << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<int> result(n);Pre-allocate vector for output

int left = 0, right = n - 1;Initialize pointers at array ends

for (int i = n - 1; i >= 0; i--) {Fill output array backwards

if (abs(nums[left]) > abs(nums[right])) {Compare absolute values to pick larger square

function sortedSquares(nums) {
    const n = nums.length;
    const result = new Array(n);
    let left = 0, right = n - 1;
    for (let i = n - 1; i >= 0; i--) {
        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
console.log(sortedSquares([-4,-1,0,3,10]));

Line Notes

const result = new Array(n);Allocate output array with fixed size

let left = 0, right = n - 1;Initialize pointers at both ends

for (let i = n - 1; i >= 0; i--) {Fill output array from end to start

if (Math.abs(nums[left]) > Math.abs(nums[right])) {Compare absolute values to decide which square to place

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the array once with two pointers, performing constant work per element.

💡 For n=1000, this means about 1000 operations, which is very efficient.

Interview Verdict: Accepted and optimal

This approach is the best practical solution and is expected in interviews.

🧠

In-place Modification with Extra Pass (Not Recommended)

💡 This approach tries to square elements in place and then sort, but it is less efficient and not recommended in interviews.

Intuition

Square all elements in place, then sort the array to get the final result.

Algorithm

1. Iterate over the array and square each element in place.
2. Sort the array in place.
3. Return the modified array.

💡 This approach is simple but wastes the opportunity to use two pointers for O(n) time.

</>

Code

def sortedSquares(nums):
    for i in range(len(nums)):
        nums[i] = nums[i] * nums[i]
    nums.sort()
    return nums

# Driver code
if __name__ == '__main__':
    nums = [-4,-1,0,3,10]
    print(sortedSquares(nums))

Line Notes

for i in range(len(nums))Iterate over all indices to modify in place

nums[i] = nums[i] * nums[i]Square each element directly in input array

nums.sort()Sort the squared elements in place

return numsReturn the modified input array

import java.util.*;
public class Solution {
    public static int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
    public static void main(String[] args) {
        int[] nums = {-4,-1,0,3,10};
        System.out.println(Arrays.toString(sortedSquares(nums)));
    }
}

Line Notes

for (int i = 0; i < nums.length; i++) {Loop to square elements in place

nums[i] = nums[i] * nums[i];Square each element directly

Arrays.sort(nums);Sort the squared array in place

return nums;Return the modified array

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> sortedSquares(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        nums[i] = nums[i] * nums[i];
    }
    sort(nums.begin(), nums.end());
    return nums;
}

int main() {
    vector<int> nums = {-4,-1,0,3,10};
    vector<int> res = sortedSquares(nums);
    for (int val : res) cout << val << ' ';
    cout << endl;
    return 0;
}

Line Notes

for (int i = 0; i < nums.size(); i++) {Square elements in place

nums[i] = nums[i] * nums[i];Modify each element directly

sort(nums.begin(), nums.end());Sort the squared elements

return nums;Return the modified vector

function sortedSquares(nums) {
    for (let i = 0; i < nums.length; i++) {
        nums[i] = nums[i] * nums[i];
    }
    nums.sort((a, b) => a - b);
    return nums;
}

// Test
console.log(sortedSquares([-4,-1,0,3,10]));

Line Notes

for (let i = 0; i < nums.length; i++) {Loop to square elements in place

nums[i] = nums[i] * nums[i];Square each element directly

nums.sort((a, b) => a - b);Sort the squared array numerically

return nums;Return the modified input array

⏱

Complexity

TimeO(n log n)

SpaceO(1)

Squares in place (O(n)) then sorts in place (O(n log n)) with no extra space.

💡 This uses less space but is slower than the two-pointer approach.

Interview Verdict: Accepted but not optimal

This approach is acceptable but interviewers prefer the two-pointer O(n) solution.

📊

All Approaches - One-Glance Tradeoffs

💡 The two-pointer approach is the best choice for interviews due to its optimal time and space balance.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n log n)	O(n)	No	N/A	Mention only - never code
2. Two Pointers from Ends	O(n)	O(n)	No	N/A	Code this approach
3. In-place Modification + Sort	O(n log n)	O(1)	No	N/A	Mention only if asked about space optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.State the brute force approach: square all elements and sort.Explain its inefficiency and propose the two-pointer approach.Describe the two-pointer algorithm and implement it.Test your code with edge cases and discuss complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your ability to leverage sorted input, optimize time complexity, and write clean, bug-free code.

Common Follow-ups

• Can you do this in O(n) time? → Use two pointers from ends.
• Can you do this in-place? → Discuss tradeoffs and limitations.

💡 These follow-ups check if you can optimize and understand space-time tradeoffs.

🔍

Pattern Recognition

When to Use

1) Input array is sorted; 2) Need to transform elements (square); 3) Output must be sorted; 4) Negative numbers involved

Signature Phrases

'sorted in non-decreasing order''return an array of the squares sorted'

NOT This Pattern When

Sorting arbitrary arrays after transformation without leveraging sorted input

Similar Problems

Merge Sorted Array - similar two-pointer merging techniqueSorted Squares of Two Arrays - merging squares from two sorted arrays

Practice

1. The following code attempts to move zeroes to the end of the array in-place:

def moveZeroes(nums):
    lastNonZeroFoundAt = 0
    for num in nums:
        if num != 0:
            nums[lastNonZeroFoundAt] = num
            lastNonZeroFoundAt += 1
    # Bug introduced here
    for i in range(lastNonZeroFoundAt, len(nums)):
        nums[i] = nums[i]

What is the bug in this code?

medium

A. The variable lastNonZeroFoundAt is incremented incorrectly.

B. The first loop does not correctly identify non-zero elements.

C. The second loop does not fill zeroes after lastNonZeroFoundAt, leaving old values intact.

D. The assignment inside the first loop overwrites zeroes incorrectly.

Solution

1. Step 1: Analyze second loop behavior

   The second loop assigns nums[i] = nums[i], which does nothing and fails to fill zeroes.

2. Step 2: Identify correct fix

   It should assign nums[i] = 0 to move zeroes to the end properly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Zeroes remain unfilled, causing incorrect output [OK]

Hint: Second loop must fill zeroes, not copy existing values [OK]

Common Mistakes:

• Forgetting to fill zeroes after moving non-zero elements
• Misunderstanding loop purpose

2. What is the time complexity of the optimal two-pointer approach for removing duplicates from a sorted array of length n?

medium

A. O(n) because each element is visited at most twice

B. O(n log n) due to sorting overhead

C. O(n²) due to nested comparisons

D. O(1) since it modifies the array in-place

Solution

1. Step 1: Identify loops and operations

   The algorithm uses a single for loop iterating over n elements once, with constant time operations inside.

2. Step 2: Confirm no nested loops or sorting

   No nested loops or sorting steps; each element is compared once or twice, so total time is linear.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear scan with two pointers yields O(n) time [OK]

Hint: Single pass over array means O(n) time [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Thinking in-place means O(1) time

3. Identify the bug in the following code snippet for removing elements equal to val from nums in-place:

medium

A. The end pointer is not decremented after swapping, causing infinite loop

B. The start pointer is incremented even when a swap occurs

C. The condition in the while loop should be start < end, not start <= end

D. Swapping elements without checking if nums[end] is also val

Solution

1. Step 1: Analyze pointer updates after swap

   After swapping nums[start] and nums[end], end must be decremented to exclude the swapped val at the end.

2. Step 2: Consequence of missing end decrement

   Without end--, the loop may repeatedly swap the same elements, causing infinite loop or incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing end decrement after swap breaks loop progress [OK]

Hint: Always decrement end after swapping val to end [OK]

Common Mistakes:

• Forgetting to decrement end after swap
• Incrementing start incorrectly after swap

4. Suppose the 4Sum problem is modified so that elements can be reused multiple times in quadruplets (i.e., indices can repeat). Which modification to the optimal hash map approach correctly handles this variant?

hard

A. Remove the index overlap check and allow all pairs to combine freely.

B. Use the same hash map approach but skip sorting the array to allow duplicates.

C. Modify the pair combination step to allow pairs with overlapping indices and remove index checks, but ensure quadruplets are sorted and unique.

D. Switch to brute force four nested loops since hash map approach cannot handle reuse.

Solution

1. Step 1: Understand reuse means indices can repeat

   Index overlap check must be removed or relaxed to allow repeated elements.

2. Step 2: Adjust pair combination logic

   Allow pairs with overlapping indices but still sort quadruplets and use a set to avoid duplicates.

3. Step 3: Evaluate other options

   Removing sorting breaks duplicate handling; brute force is inefficient; simply removing checks without sorting leads to duplicates.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Allow index overlap but keep sorting and deduplication [OK]

Hint: Allow index overlap but keep sorting and deduplication [OK]

Common Mistakes:

• Removing sorting causes duplicates
• Assuming brute force is only solution

5. Suppose the problem changes: you want to count pairs with absolute difference at most K, but now the array can contain duplicate elements and you want to count pairs where elements can be reused multiple times (i.e., pairs (i, j) with i ≤ j). Which modification to the binary search approach correctly handles this variant?

hard

A. Start binary search from i instead of i + 1 and count pairs where j ≥ i, adjusting count accordingly.

B. Use brute force nested loops to count all pairs with i ≤ j and difference ≤ K, as binary search cannot handle reuse.

C. Use two pointers with left starting at 0 and right starting at 0, moving right pointer forward and counting pairs including i = j.

D. Keep the same code but change bisect_right to bisect_left to include duplicates and allow i ≤ j pairs.

Solution

1. Step 1: Understand reuse and duplicates impact

   Allowing i ≤ j means pairs with the same element twice are valid; binary search must include current index.

2. Step 2: Modify binary search start index

   Starting bisect_right from i (not i+1) includes pairs where i == j; counting j ≥ i pairs correctly.

3. Step 3: Adjust counting logic

   Count pairs as j - i + 1 if including i == j, or carefully count pairs with j ≥ i.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Starting search at i and counting pairs with j ≥ i handles reuse correctly [OK]

Hint: Start binary search at i to include pairs with i == j [OK]

Common Mistakes:

• Using bisect_left instead of bisect_right incorrectly
• Ignoring pairs where i == j
• Assuming two pointers cannot handle reuse