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.

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]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: