## Squares Of A Sorted Array

### March 6, 2020

This problem has been going around the internet the last few days. I’ve seen it on several message boards, though I don’t know the original source:

Given an array of integers sorted in non-decreasing order, return an array of the squares of each number, also sorted in non-decreasing order. For instance, given (-4 -1 0 3 10), the desired output is (0 1 9 16 100).

Your task is to write a program to compute the sorted squares of a sorted array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 9 Responses to “Squares Of A Sorted Array”

1. Zack said

Nifty little drill. Here is my take on it using Julia: https://pastebin.com/DQ8wHgjK

Clearly, whoever was the original poster of this exercise 1. had a moderate command of the English language, and 2. opted for a more interesting approach than just squaring the list and then sorting it. This solution adheres to the 2nd assumption.

Have a nice weekend!

PS – a more elegant way of saying “non-decreasing order” is “increasing order” or “ascending order”. Why confuse people needlessly?

2. Paul said

The sort method in Python is a mergesort, that tries to find runs of increasing and decreasing numbers and then merges those runs. So, for this problem Python sorting is not O(nlogn), but a lot faster, as the squares form a run of decreasing numbers and a run of increasing numbers. The method below works faster, than the method proposed by PP in Python.

```def sol1(arr):
return sorted(a**2 for a in arr)
```
3. Daniel said

Here’s a solution in C.

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

// assumes input is sorted
void sorted_squares(int* in, int* out, int n) {
int lo = 0;
int hi = n - 1;
for (int i = n - 1; i >= 0; --i) {
if (abs(in[lo]) > abs(in[hi])) {
out[i] = in[lo] * in[lo];
++lo;
} else {
out[i] = in[hi] * in[hi];
--hi;
}
}
}

static void print_array(int* array, int n) {
for (int i = 0; i < n; ++i) {
if (i > 0) printf(", ");
printf("%d", array[i]);
}
printf("\n");
}

int main(int argc, char* argv[]) {
int n = argc - 1;
int* in = malloc(sizeof(int) * n);
int* out = malloc(sizeof(int) * n);
for (int i = 0; i < n; ++i) {
in[i] = atoi(argv[i + 1]);
}
sorted_squares(in, out, n);
print_array(out, n);
free(in);
free(out);
return EXIT_SUCCESS;
}
```

Example:

```\$ ./a.out -4 -1 0 3 10
0, 1, 9, 16, 100
```
4. Daniel said

@Zack, “non-decreasing” may have been used to suggest that the input and output arrays can have duplicates. “increasing” could be interpreted to suggest otherwise.

5. Daniel said

…analogous to how “non-negative” is used to include positive numbers and zero, whereas “positive” used alone would exclude zero.

6. Daniel said

Here’s a solution in Python.

```from bisect import bisect_left
from heapq import merge

def sorted_squares(l):
idx = bisect_left(l, 0)
squares1 = (x * x for x in reversed(l[:idx]))
squares2 = (x * x for x in l[idx:])
return list(merge(squares1, squares2))

print(sorted_squares([-4, -1, 0, 3, 10]))
```

Output:

```[0, 1, 9, 16, 100]
```
7. Steve said
```Klong version

{x^2}'[-4 -1 0 3 10]
[16 1 0 9 100]

l@<l::{x^2}'[-4 -1 0 3 10]
[0 1 9 16 100]

l@<l::{x^2}'[-4 -1 0 3 4 10]
[0 1 9 16 16 100]

?l@<l::{x^2}'[-4 -1 0 3 4 10]
[0 1 9 16 100]

```
8. Sam Claflin said

Python solution:

import numpy as np

Get user input

arr = np.array(input(“Type an array of integers in increasing order (a b c x y z): “).split())
arr_ints = []

Create new array of integers and sort by increasing order

for i in range(len(arr)):
arr_ints.append(int(arr[i]))

Append each square value to a new array

squares = []
for num in arr_ints:
squares.append(num ** 2)

Print final array

print(np.sort(squares))

===================

OUTPUT

Type an array of integers in increasing order (a b c x y z): -4 -1 0 3 10

[ 0 1 9 16 100]