Squares of a Sorted Array solution and explanation
TCS
Google
Infosys
9 more videos on this problem
Squares of a Sorted Array - Leetcode 977 - PythonNeetCode · 8:14 · 60K views
Squares of a Sorted Array - Leetcode 977 - 2 Pointers (Python)Greg Hogg · 7:23 · 29K views
Squares of Sorted Array (LeetCode 977) | Full Solution with examples & animation | Study AlgorithmsNikhil Lohia · 11:01 · 19K views
Squares of a Sorted Array | Live Coding with Explanation | Leetcode #977Algorithms Made Easy · 3:25 · 8K views
LeetCode Problem 977: How to Find the Squares of a Sorted Array in O(n) TimeEngineering Digest · 6:28 · 5K views
977. Squares of a Sorted Array | when to use 2 Pointer | Sorting | 2 WaysAryan Mittal · 11:52 · 4K views
Leetcode | 977. Squares of a Sorted Array | Easy | Java Solution [O(n) Time]Developer Docs · 7:31 · 1K views
SQUARES OF A SORTED ARRAY LEETCODE 977 SOLUTION IN JAVA | LEETCODE | 977 | SQUARES OF A SORTED ARRAYEconomic Coder · 14:08 · 100 views
Leetcode 977 - Squares of a Sorted Array (JAVA, Solution Explain!)LC Bear · 2:15 · 96 views
Squares of a Sorted Array | LeetCode 977 | Two Pointers ExplainedTechTrouble Solved · 10:54 · 56 views
The 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.
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]
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104numsis sorted in non-decreasing order.
O(n) solution using a different approach?Approach overview
Problem Overview: Given a non-decreasing sorted integer array nums, return a new array containing the squares of each number, also sorted in non-decreasing order. The challenge comes from negative values: squaring them can produce larger values than some positive numbers.
Approach 1: Sorting After Squaring (O(n log n) time, O(1) or O(n) space)
The most direct strategy is to square every element in the array and then sort the result. Iterate through nums, replace each value with its square using x * x, then run a standard sorting algorithm on the array. This works because sorting reorders the squared values correctly regardless of the original sign of the numbers. The implementation is simple and easy to reason about, but the sorting step dominates the runtime at O(n log n). Prefer this approach when clarity matters more than optimal performance or when you want a quick baseline solution.
Approach 2: Two Pointer Technique (O(n) time, O(n) space)
The optimal solution uses the structure of the sorted array. The largest square must come from either the most negative value on the left or the largest positive value on the right. Use two pointers: one at the start (left) and one at the end (right). Compare nums[left]^2 and nums[right]^2, place the larger square at the end of the result array, and move the corresponding pointer inward. Continue filling the result array from right to left. Each element is processed exactly once, giving O(n) time and O(n) extra space for the output array. This pattern frequently appears in problems involving sorted arrays and symmetric comparisons.
The key insight is that squaring breaks the sorted order only because negative values flip sign. The largest magnitude values sit at the edges of the array. A two pointers strategy lets you compare those extremes directly without re-sorting.
Recommended for interviews: Interviewers expect the Two Pointer Technique. The sorting approach shows you understand the problem but misses the optimization opportunity. Using two pointers demonstrates that you recognize patterns in a sorted array and can avoid unnecessary sorting. The optimal solution runs in linear time, processes each element once, and is considered the standard interview answer.
Approach 1: Approach 1: Sorting After Squaring
This approach involves first squaring every element, and then sorting the resultant array. Since the sorting algorithm typically used is O(n log n) in terms of time complexity, this approach is straightforward but not the most optimal for this problem.
def sorted_squares(nums):
nums = [num * num for num in nums]
nums.sort()
return nums
nums = [-4, -1, 0, 3, 10]
print(sorted_squares(nums))import java.util.Arrays;
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};
int[] result = sortedSquares(nums);
for (int num : result) {
System.out.print(num + " ");
}
}
}#include <iostream>
#include <vector>
#include <algorithm>
std::vector<int> sortedSquares(std::vector<int>& nums) {
for (auto& num : nums) {
num = num * num;
}
std::sort(nums.begin(), nums.end());
return nums;
}
int main() {
std::vector<int> nums = {-4, -1, 0, 3, 10};
nums = sortedSquares(nums);
for (const int num : nums) {
std::cout << num << " ";
}
return 0;
}function sortedSquares(nums) {
nums = nums.map(num => num * num);
nums.sort((a, b) => a - b);
return nums;
}
let nums = [-4, -1, 0, 3, 10];
console.log(sortedSquares(nums));#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
void sortedSquares(int* nums, int numsSize, int* returnSize) {
for (int i = 0; i < numsSize; i++) {
nums[i] = nums[i] * nums[i];
}
qsort(nums, numsSize, sizeof(int), cmp);
*returnSize = numsSize;
}
int main() {
int nums[] = {-4, -1, 0, 3, 10};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int returnSize;
sortedSquares(nums, numsSize, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", nums[i]);
}
return 0;
}using System;
using System.Linq;
public class Solution {
public static int[] SortedSquares(int[] nums) {
nums = nums.Select(x => x * x).ToArray();
Array.Sort(nums);
return nums;
}
public static void Main() {
int[] nums = {-4, -1, 0, 3, 10};
int[] result = SortedSquares(nums);
Console.WriteLine(string.Join(" ", result));
}
}This Python solution utilizes list comprehensions to square each element, followed by the built-in sort() method that sorts the array in place.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), utilizing in-place sort.
Approach 2: Approach 2: Two Pointer Technique
Utilizing a two-pointer technique allows us to traverse the array from both ends, taking advantage of the non-decreasing order of the input array. By comparing the squares of elements from both ends, we can construct the output array from the largest to the smallest square, ensuring an O(n) time complexity.
def sorted_squares(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[right] ** 2
right -= 1
else:
result[i] = nums[left] ** 2
left += 1
return result
nums = [-4, -1, 0, 3, 10]
print(sorted_squares(nums))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[right] * nums[right];
right--;
} else {
result[i] = nums[left] * nums[left];
left++;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {-4, -1, 0, 3, 10};
int[] result = sortedSquares(nums);
for (int num : result) {
System.out.print(num + " ");
}
}
}#include <iostream>
#include <vector>
#include <cmath>
std::vector<int> sortedSquares(std::vector<int>& nums) {
int n = nums.size();
std::vector<int> result(n);
int left = 0, right = n - 1;
for (int i = n - 1; i >= 0; i--) {
if (std::abs(nums[left]) < std::abs(nums[right])) {
result[i] = nums[right] * nums[right];
right--;
} else {
result[i] = nums[left] * nums[left];
left++;
}
}
return result;
}
int main() {
std::vector<int> nums = {-4, -1, 0, 3, 10};
std::vector<int> result = sortedSquares(nums);
for (const int num : result) {
std::cout << num << " ";
}
return 0;
}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[right] * nums[right];
right--;
} else {
result[i] = nums[left] * nums[left];
left++;
}
}
return result;
}
let nums = [-4, -1, 0, 3, 10];
console.log(sortedSquares(nums));#include <stdio.h>
#include <stdlib.h>
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
int* result = (int*)malloc(numsSize * sizeof(int));
int left = 0, right = numsSize - 1;
int position = numsSize - 1;
while (left <= right) {
if (abs(nums[left]) > abs(nums[right])) {
result[position] = nums[left] * nums[left];
left++;
} else {
result[position] = nums[right] * nums[right];
right--;
}
position--;
}
*returnSize = numsSize;
return result;
}
int main() {
int nums[] = {-4, -1, 0, 3, 10};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int returnSize;
int* result = sortedSquares(nums, numsSize, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
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[right] * nums[right];
right--;
} else {
result[i] = nums[left] * nums[left];
left++;
}
}
return result;
}
public static void Main() {
int[] nums = {-4, -1, 0, 3, 10};
int[] result = SortedSquares(nums);
Console.WriteLine(string.Join(" ", result));
}
}In this Python solution, two pointers help determine where to put the squares in a new result list, based on the largest square from either end. This results in a O(n) efficient solution.
Time Complexity: O(n) as only one traversal is needed.
Space Complexity: O(n) for storing the result.
Approach 3: Two Pointers
Since the array nums is already sorted in non-decreasing order, the square values of the negative numbers in the array are decreasing, and the square values of the positive numbers are increasing. We can use two pointers, each pointing to the ends of the array. Each time we compare the square values of the elements pointed to by the two pointers, we put the larger square value at the end of the result array.
The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).
func sortedSquares(nums []int) []int {
n := len(nums)
ans := make([]int, n)
for i, j, k := 0, n-1, n-1; i <= j; k-- {
a := nums[i] * nums[i]
b := nums[j] * nums[j]
if a > b {
ans[k] = a
i++
} else {
ans[k] = b
j--
}
}
return ans
}impl Solution {
pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut ans = vec![0; n];
let (mut i, mut j) = (0, n - 1);
for k in (0..n).rev() {
let a = nums[i] * nums[i];
let b = nums[j] * nums[j];
if a > b {
ans[k] = a;
i += 1;
} else {
ans[k] = b;
j -= 1;
}
}
ans
}
}class Solution {
/**
* @param Integer[] $nums
* @return Integer[]
*/
function sortedSquares($nums) {
$n = count($nums);
$ans = array_fill(0, $n, 0);
for ($i = 0, $j = $n - 1, $k = $n - 1; $i <= $j; --$k) {
$a = $nums[$i] * $nums[$i];
$b = $nums[$j] * $nums[$j];
if ($a > $b) {
$ans[$k] = $a;
++$i;
} else {
$ans[$k] = $b;
--$j;
}
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting After Squaring | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Two Pointer Technique | Time Complexity: O(n) as only one traversal is needed. |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting After Squaring | O(n log n) | O(1) to O(n) | Simple baseline solution or when using built-in sort is acceptable |
| Two Pointer Technique | O(n) | O(n) | Optimal approach when the input array is already sorted |
Frequently asked questions
Is Squares of a Sorted Array easy or hard?
Squares of a Sorted Array is classified as an Easy problem on LeetCode. The straightforward solution uses sorting, while the intended interview solution applies a two-pointer strategy to achieve linear time complexity.
Squares of a Sorted Array Python/Java solution
Most implementations follow the two-pointer approach. In Python or Java, create a result array of the same size, compare squared values from both ends of the input array, and insert the larger square from the back of the result array while moving the pointers inward.
How to solve Squares of a Sorted Array in O(n)?
Use two pointers at the leftmost and rightmost positions of the sorted array. Compare the squares of both values and place the larger one at the end of a result array, then move the corresponding pointer inward. Continue filling the result array from right to left until all elements are processed.
What is the best approach for Squares of a Sorted Array?
The two pointer technique is the best approach. Place one pointer at the start and one at the end of the sorted array, compare the squared values, and fill the result array from the back. This works because the largest squared value must come from either extreme of the array. The algorithm runs in O(n) time with O(n) space.
Is Squares of a Sorted Array asked at Google/Amazon/Meta?
Squares of a Sorted Array is a common interview-style problem that appears in coding screens and practice sets used by companies like Amazon, Google, and Meta. It tests recognition of the two-pointer pattern and the ability to exploit properties of a sorted array.
What data structure is used in Squares of a Sorted Array?
The problem primarily uses arrays along with the two-pointer technique. Two indices track values at both ends of the sorted array, and a result array stores squared values in sorted order.
What is the time complexity of Squares of a Sorted Array?
The optimal solution runs in O(n) time using the two-pointer approach because each element is processed once. A simpler alternative squares all elements and sorts them, which takes O(n log n) time due to the sorting step.