Squares of a Sorted Array - Practice Coding Problems

Squares of a Sorted Array - Problem

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

You must solve this problem efficiently, considering that the input array is already sorted.

Input & Output

Example 1 — Mixed Positive and Negative

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

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

💡 Note: Squares are [16,1,0,9,100]. After sorting: [0,1,9,16,100]. Note that negative numbers become positive when squared.

Example 2 — All Negative Numbers

$ Input: nums = [-7,-3,-2,-1]

› Output: [1,4,9,49]

💡 Note: All numbers are negative. Squares are [49,9,4,1]. After sorting in non-decreasing order: [1,4,9,49].

Example 3 — All Positive Numbers

$ Input: nums = [1,2,3,4,5]

› Output: [1,4,9,16,25]

💡 Note: All numbers are positive and already sorted. Squares maintain the same order: [1,4,9,16,25].

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array [-4,-1,0,3,10] with mixed signs

Process

Square each element: [16,1,0,9,100]

Output

Sort squared values: [0,1,9,16,100]

Key Takeaway

🎯 Key Insight: Use two pointers to identify largest squares from array extremes, avoiding the need to sort

Asked in

F Facebook 35 a Amazon 28 M Microsoft 22 A Apple 18

The optimal solution uses the two-pointers technique to leverage the sorted property of the input array. The key insight is that the largest squared values come from the extreme ends (most negative or most positive). Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Square and Sort	O(n log n)	O(1)	Square all elements then sort the result
Two Pointers (Optimal)	O(n)	O(1)	Use two pointers from both ends to build result in reverse order

Square and Sort — Algorithm Steps

Square each element in the array
Sort the squared array
Return the sorted result

Visualization

Tap to expand

Step-by-Step Walkthrough

Square All

Square each element regardless of order

Sort

Sort the squared values

Result

Final sorted array of squares

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    
    // Square each element
    for (int i = 0; i < numsSize; i++) {
        nums[i] = nums[i] * nums[i];
    }
    
    // Sort the squared array
    qsort(nums, numsSize, sizeof(int), compare);
    
    return nums;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, size, &returnSize);
    
    // Print result
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n) to square elements + O(n log n) to sort = O(n log n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space (excluding output array)

✓ Linear Space

125.0K Views

High Frequency

~15 min Avg. Time

4.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Square and Sort — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler