Coderust: Hacking the Coding Interview/

...

/

Squares of a Sorted Array

Squares of a Sorted Array

Given a sorted array of integers, return a sorted array of their squares.

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) ...