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

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);
        }
};

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;

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.

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.

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.

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.

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.

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.

The fastest way is to use 2 indexes

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

EDIT: just add int main() and change test to make it works for multiple values ( I thought that was obvious change but well ... ) EDIT2: deque is your friend

instead of bubble sort. you can try insertion sort. it is very fast and efficient when used with smaller arrays. Unfortunately, it loses this efficiency when dealing with large amounts of data.

#include <iostream>

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

    const int size = 6;

    int j = 0;

    for (int i = 0; i < size; ++i)
    {
        // apply double values
        int key = arr[i] * arr[i];

        // loop for sorting elements
        for (j = i - 1; arr[j] > key; --j) 
        {
            arr[j + 1] = arr[j]; // shift array
        }

        // apply insertion
        arr[j + 1] = key;

    }

    // print array
    for (const auto& i : arr)
    {
        std::cout << i << ' ';
    }
}

as @Michael Urman suggest it can be done by SDL-stylish like this:

#include <iostream>
#include <algorithm>
#include <functional> 
#include <iterator>

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

    for (auto i = std::begin(arr); i != std::end(arr); ++i)
    {
        std::rotate(std::upper_bound(std::begin(arr)
            , i
            , (*i *= *i)
            , std::less<std::iterator_traits<decltype(std::begin(arr))>::value_type>())
            , i
            , std::next(i));
    }

    for (const auto& i : arr)
    {
        std::cout << i << ' ';
    }
}