Squares Of A Sorted Array
March 6, 2020
The simple solution first computes the squares, then sorts:
> (sort < (map square '(-4 -1 0 3 10))) (0 1 9 16 100)
That solution requires time O(n log n) because of the sort. An O(n) solution exploits the fact that the input is already sorted, using two pointers lo and hi to scan from opposite ends of the input array:
(define (sq-sort xv)
(let loop ((lo 0) (hi (- (vector-length xv) 1)) (xs (list)))
(if (= lo hi) (cons (square (vector-ref xv lo)) xs)
(if (< (abs (vector-ref xv lo)) (abs (vector-ref xv hi)))
(loop lo (- hi 1) (cons (square (vector-ref xv hi)) xs))
(loop (+ lo 1) hi (cons (square (vector-ref xv lo)) xs))))))
> (sq-sort '#(-4 -1 0 3 10)) (0 1 9 16 100)
You can run the program at https://ideone.com/UUaAnI.
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