Efficiently squaring each element in a sorted array, keeping it sorted

Question

The other day I was asked the following question during an interview:

Given a sorted array, how would you square each element of this array, while keeping it sorted?

I froze up and wrote a horribly inefficient solution I've included below. Basically, I iterate through the original array, squaring each element, and then sort that array via bubble sort. (I know, I could do better, but it's what came to mind at first).

Is there a way to do this more efficiently, perhaps an \$\mathcal{O}(N)\$ solution?

void bubbleSort(int *arr, int length);

int main(int argc, const char * argv[]) {

    int arr[] = {-3,-2,0,4,5,8};

    for(int i = 0; i < 6; i++) {
        arr[i] *= arr[i];
    }

    bubbleSort(arr, 6);

    for(int j = 0; j < 6; j++)
        cout << arr[j] << endl;
}

void bubbleSort(int *arr, int length) {
    int temp;

    for(int i = 0; i < length; i++) {
        for(int j = 0; j < length; j++) {
            if(arr[j] < arr[j+1]) {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

Elements can be negative or positive.

Answer 1

It can be done in O(n) time. Split your array into two logical parts. Positive and negative. Then apply square to each element in both arrays. Then merge the arrays( merging can be done in O(n) ), but merge the array with previously negative integers in reverse order, since its values will be reversed.

Answer 2

If the array is sorted.
Then the only re-ordering that will happen is negative numbers into positive (as a square of a negative results in a positive). So negative numbers will need to be re-sorted into the positive numbers.

  [ -10, -6, -4, -2, 1, 3, 5, 8]
                   ^
                   Split

You can actually just consider these two separate sorted arrays (one is ordered in the negative direction but that just means use -- rather ++ while iterating over it (we have an iterator for that)).

So you just need to perform a simple merge into a destination (we have an algorithm for that). Once that is done perform the square operation on the values. This algorithm is O(n). Though you are making two traversals of the array.

The only optimization is to perform the square at the same time you do the merge (A quick custom iterator solves that). Solution is O(n) but would be a single traversal of the array (and its not that difficult).

void mergeSortedArray(std::vector<int>& data)
{

    // Find the iterator range for the positive values.
    using iter          = std::vector<int>::const_iterator;
    iter  endPositive   = std::end(data);
    iter  loopPositive  = std::find_if(std::begin(data), std::end(data),
                                       [](int val) {return val >=0;});

    // Find the iterator range for the negative values.
    using reve          = std::reverse_iterator<iter>;
    reve  endNegative   = reve(std::begin(data));
    reve  loopNegative  = reve(loopPositive);

    // Create an array to put the results into.
    std::vector<int>  result;
    result.reserve(data.size());

    // Perform a standard merge
    std::merge(loopPositive, endPositive, loopNegative, endNegative,
               SquarePushBackIterator(result),
               [](int val1, int val2){return std::abs(val1) < std::abs(val2);});

    // Use move assignment to put the result in the output vector.
    // Alternatively we could return an array by value.
    data = std::move(result);
}

Just need a local customer iterator.
This squares the values and pushes them into a container on assignment.

class SquarePushBackIterator
    : public std::iterator<std::output_iterator_tag,int>
{
    std::vector<int>& dst;
    public:
        SquarePushBackIterator(std::vector<int>& dst) : dst(dst) {}
        // These just return references to the iterator.
        // The only operation that matters is assignment.
        SquarePushBackIterator& operator*()     {return *this;}
        SquarePushBackIterator& operator++()    {return *this;}
        SquarePushBackIterator& operator++(int) {return *this;}

        // The assignment squares and inserts into the destination.
        void operator=(int val)
        {
            dst.push_back(val * val);
        }
};

Answer 3

Since it is sorted, you could just loop through the array once, compare the absolute values of the first and last items in the array and then based on whichever is larger, square that item and place the value into the last item of a new array. Repeat this process by increasing the front index or decreasing the back index (depending on whichever value was larger), then placing the next largest item into the new array's second last item and so forth.

Basically, you're doing a sort and square the value at the same time in a single loop.

int arr[] = {-3,-2,0,4,5,8};
int size = 6;
int newArr[size];

int newArrInd = size - 1;
int front = 0;
int back = size - 1;

for(int i = 0; i < size; i++) {
    if (abs(arr[front]) > abs(arr[back])){
        newArr[newArrInd--] = arr[front] * arr[front];
        front++;
    }
    else{
        newArr[newArrInd--] =  arr[back] * arr[back];
        back--;
    }
}

for(int j = 0; j < size; j++)
    cout << newArr[j] << endl;

Answer 4

Here's a potentially simpler solution (that may take slightly longer to run; although it is still \$O(n)\$). The basic idea is of course that negative numbers only need to be reversed (before or after squaring, it doesn't really matter which). This doesn't have the property that the underlying container will remain sorted through the whole procedure; whether this is actually required or not (or whether it is only the final result that must abide that criterion) isn't 100% clear.

#include <algorithm>
#include <iterator>

template <typename Iterator>
void square_and_sort(Iterator begin, Iterator end)
{
    using value_type = typename std::iterator_traits<Iterator>::value_type;

    auto first_positive = std::find_if(begin, end, 
            [](const value_type& v) { return v >= value_type{}; });
    std::reverse(begin, first_positive);
    std::transform(begin, end, begin,
            [](const value_type& v) { return v * v; });
    std::inplace_merge(begin, first_positive, end);
}

Effectively we:

• Find the first zero or positive value,
• Reverse all values up to that first zero or positive value (since these must be negative),
• Square everything, and finally
• Merge the squared negative and squared positive values back, in place.

Answer 5

Your solution

If I wanted to do the obvious solution of squaring the array and sorting it it would look something like this:

#include <algorithm>
#include <iostream>

int main(){
    //arguably arr should be an std::array or even auto for an std::initializer_list
    int arr[] = { -3, -2, 0, 4, 5, 8 };
    //square array
    std::transform(std::begin(arr), std::end(arr), std::begin(arr),
        [](int n){ return n * n; }
    );
    //sort array
    std::sort(std::begin(arr), std::end(arr));
    //print result
    for (const auto &i : arr)
        std::cout << i << ' ';
}

Was it a requirement to not use the standard library? It saves you from some of the pain of implementing boring, difficult and error-prone things such as sorting-algorithms.

My solution

The problem with squaring the array is that negative numbers become positive, making the array not sorted anymore. My idea is to find the index mid of the first non-negative number and then squaring the whole array. The partial list [begin, mid[ is sorted in reverse order and the partial list ]mid, end[ is already correctly sorted. Two sorted lists can be efficiently std::merged into a sorted list. The reverse ordering of the first list can be compensated by using a reverse_iterator.

#include <algorithm>
#include <iostream>

int main(){
    int arr[] = { -3, -2, 0, 4, 5, 8 };
    //find index of first non-negative element
    auto midIndex = std::lower_bound(std::begin(arr), std::end(arr), 0);
    //square array
    std::transform(std::begin(arr), std::end(arr), std::begin(arr),
        [](int n){ return n * n; }
    );
    //new array of same size and type as old array
    decltype(arr) squareArray;
    //merge left list [begin, midIndex] and right list [midIndex, end[
    std::merge(
        //left list
        std::reverse_iterator<decltype(midIndex)>(midIndex), std::rend(arr),
        //right list
        midIndex, std::end(arr),
        //destination
        squareArray
    );
    //print result
    for (const auto &i : squareArray)
        std::cout << i << ' ';
}

This implementation uses a second array for the merged list. It is probably possible to do it in-place, but that requires some more effort. My solution reduced the complexity from O(n*log(n)) to O(n), but changed the space complexity from O(1) to O(n), which is not strictly necessary. I would probably favor your solution because it is easy unless it is proven by profiling that the small efficiency deficit is a significant problem.

Answer 6

If you are allowed to have the array unsorted after squaring, and sort it afterwards, at least use std::sort, or, for better time performance but more space usage, std::merge. If the standard library is out of bounds for the interview, run. :)

On the other hand, if you must sort after changing each element, leverage other parts of the standard library, say std::lower_bound and std::rotate. Be careful about the order you do things so you don't risk squaring any element twice.

Answer 7

I believe you have missed a critical requirement, that you need to keep the array sorted. Your solution does not. The negative values in the input start sorted, but as you square them, they reverse. You then correct it with a bubble-sort.

There is a way to do it while keeping all the data sorted at all times. It is not an \$O(n)\$ operation.

The algorithm to use would be to square all values on the right-side of the array that are larger than the abs-value of the left-most value.

Once you find a value that's smaller, you know the left-most value squared needs to be inserted at that point. Shift all values left, insert the square, and move on.

Your code is very C-like, and a C-like implementation would be:

void shift (int *data, int right) {
    for (int i = 1; i <= right; i++) {
        data[i - 1] = data[i];
    }
}

void sqsort(int *data, const int len) {
    int right = len - 1;
    while (right >= 0) {
        // square right-most values that are larger than the left-most.
        int limit = std::abs(data[0]);
        while (right >= 0 && data[right] >= limit) {
            data[right] *= data[right];
            right--;
        }
        // insert the square of the left-most.
        if (right > 0) {
            shift(data, right);
            data[right] = limit * limit;
            right--;
        }

    }
}

A rudimentary vector-based solution would be:

void shift (std::vector<int> & data, int right) {
    for (int i = 1; i <= right; i++) {
        data[i - 1] = data[i];
    }
}

void sqsort(std::vector<int> & data) {
    int right = data.size() - 1;
    while (right >= 0) {
        int limit = std::abs(data[0]);
        while (right >= 0 && data[right] >= limit) {
            data[right] *= data[right];
            right--;
        }
        if (right >= 0) {
            shift(data, right);
            data[right] = limit * limit;
            right--;
        }
    }
}

Note, don't use the above as an example of good C++ code, but it shows the algorithm to use. Note that, at some points, values are duplicated (during the shift), but, at no point is the array out-of-order.

Answer 8

If the array is sorted, you can find the position where it goes from negative to positive using an implementation of binary search

{-3 -2 | 0 4 5 8}
     A   B

Then using this position, compare the number on the left with the number on the right. Whichever number has the smaller absolute value, add its square into the next position in a new array, and move its pointer away from the middle, until either A reaches -1 or B reaches length

so a couple of iterations of the algorithm

array    {-3 -2 | 0 4 5 8}
pointer       A   B
squares  {              }


abs(arr[B]) < ab(arr[A])
B++
array    {-3 -2 | 0 4 5 8}
pointer       A     B
squares  {0              }

abs(arr[B]) > ab(arr[A])
A--
array    {-3 -2 | 0 4 5 8}
pointer    A        B
squares  {0 4            }

abs(arr[B]) > ab(arr[A])
A--
array    {-3 -2 | 0 4 5 8}
pointer  A          B
squares  {0 4 9          }

A == -1 && B != length
B++
array    {-3 -2 | 0 4 5 8}
pointer  A            B
squares  {0 4 9 16        }

etc...

I hope I explained myself well, its basically merge sorting.

Note. It takes O(log(n) (REMOVED: *) + n) time and O(n) space as far as I can tell.

Answer 9

It depends on the implementation of the sort algorithm. Since the case that an array is already mostly sorted, or sorted in descending order and so on, a good practical sorting algorithm will not be optimised for the case of random numbers, but for practical cases.

It is quite possible that if you just square all the numbers and then call a sorting algorithm provided by your implementation, that it will figure out that your array consists of a large number of integers in descending order, followed by a large number of integers in ascending order, and merge both sequences in an optimal way.

Answer 10

The fastest way is to use 2 indices:

int main()
{
    vector<double> k={-5, -3, 1, 2 ,6 };
    deque<double> l;
    int p1=0,p2=k.size()-1;

    double s ,e;
    do {
        s=k[p1]; e=k[p2];
        if(s*s>e*e) { l.push_front(s*s); p1++; }
        else { l.push_front(e*e); p2--; }
    } while(p2>=p1);
}

• Insert only once
• Test only twice per switch
• Read value \$2*n\$
• Worst case \$2*n\$ test due to perfect aliased vector

Just add int main() and change test to make it works for multiple values (I thought that was obvious change).

Also, deque is your friend.

Answer 11

you may consider using std::set for sorting array via insert member function.

It is an O(N*log(size() + N)), where N is the number of elements to insert.

according to http://en.cppreference.com/w/cpp/container/set/insert

#include <iostream>
#include <set>
int main()
{
    using namespace std;
    int arr[] = { -3, -2, 0, 4, 5, 8 };

    set<int> sort_squae;

    // it will sort and square the array for free
    for (auto&& i : arr)
        sort_squae.insert(i * i);

    // print it
    for (const auto& i : sort_squae)
        cout << i << ' ';
}

Answer 12

The Direct Question

Is there a way to do this more efficiently, perhaps an O(N) solution?

Yes, it can be done more efficiently than bubbleSort's O(n^2). And No. The limit of general comparison sorting algorithms is O(n log n).

The Interview Question

Given a sorted array, how would you square each element of this array, while keeping it sorted?

Sorting algorithms for an array are baked into most programming languages or can be found in a library [the kind with books if not the language's standard ones]. Sure they don't handle arbitrary objects directly, but they all handle integers appropriately for the purposes to which the language is usually put. These are off the shelf parts. There's a whole chapter in Knuth for anyone needing to take seriousness up a notch.

Keeping the array sorted while changing it's values means concurrency semantics. That's the sort of hard problem that matters to a sensible interviewer. Presenting an unreliable answer in O(n log n) is often worse than a reliable one in O(n^2) even if a reliable answer in O(n log n) is preferable.

• C++ is object oriented. This suggests encapsulation via class and object semantics.
• C++ is a flavor of C. Pointer manipulation is idiomatic.
• Chapter 5 of Knuth is on sorting. It's entirely based on manipulating pointers to records rather than moving actual records. There are worse authorities to try to imitate.

The bones of a solution that addresses the while might look something like:

 Class : Sorter
    Private Field : sorted_array
    Private Field : sorted_pointers
    Private Field : temp_value
    Public Field  : Sorted_Array


    Public Method : Sorter.get();
                    return Sorted_Array

    Private Method : Sorter.insert(v);
                     AtomicTransaction
                       sorted_array.insert(v)
                       sorted_pointers.update(sorted_array)
                       sorted_pointers.write(sorted_array)
                       SortedArray.copyfrom(sorted_array)

    Private Method : Sorter.delete(i)
                     AtomicTransaction
                       // etc ... //

    Public Method : Sorter.square()
                    For i in 0 to sorted_array.length
                        temp_value = sorted_array[i].squared
                          AtomicTransaction
                            Sorter.delete(i)
                            Sorter.insert(temp_value)

Without considering the while it's a toy problem. Buy an Xtreme CPU, store everything in RAM - or even better the L1 cache and go drag racing. But ultimate performance is tuning rather than problem solving. Complexity remains constant.