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.
Programming Praxis 
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?
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)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:
@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.
…analogous to how “non-negative” is used to include positive numbers and zero, whereas “positive” used alone would exclude zero.
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:
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]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]
Racket: https://github.com/xojoc/programming-challenges/blob/master/programming-praxis/2020_03_06.rkt