Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Squares of a Sorted Array

Explore how to transform a sorted integer array into a sorted array of squared values using both naive and optimized two-pointer approaches. Understand the logic behind handling negative and positive values, and learn to analyze time and space complexities for each method to improve algorithm efficiency.

We'll cover the following...

Statement

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

Example

Consider an integer array, sorted in non-decreasing order:

g array 0 1 2 3 4 -4 -1 0 3 10

The returned array looks like this:

g array 0 1 2 3 4 0 1 9 16 100

Sample input

[-4, -1, 0, 3, 10]

Expected output

[0, 1, 9, 16, 100]

Try it yourself

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> SortedSquares(vector<int>& nums) {
	vector<int> result(nums.size());
	// TODO: Write your code here
	return result;
}

Solution

Naive approach

Create an array of the squares of each element, and sort them. The time complexity of this approach is O(nlog⁡n)O(n \log n) or O(n2)O(n^2) ...