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]

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: