40
\$\begingroup\$

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.

\$\endgroup\$

migrated from stackoverflow.com Jan 6 '15 at 15:38

This question came from our site for professional and enthusiast programmers.

  • 6
    \$\begingroup\$ Don't you start with a sorted array? \$\endgroup\$ – FourScore Jan 6 '15 at 2:17
  • 8
    \$\begingroup\$ Assuming all the values were positive, I would simply iterate through the array, replacing each element with it's square. \$\endgroup\$ – Hot Licks Jan 6 '15 at 2:17
  • 8
    \$\begingroup\$ Are all the elements positive ? Then the sort is a red herring. \$\endgroup\$ – Quentin Jan 6 '15 at 2:17
  • 6
    \$\begingroup\$ @Quentin {-3,-2,0,4,5,8}; Reading is tech. ( and an int type can be negative, unless otherwise specified ) \$\endgroup\$ – 2501 Jan 6 '15 at 2:18
  • 4
    \$\begingroup\$ Technically the question itself does not specify the type of numbers used. Aside from negative ones, for floating-point you also must take care about the (-1;+1) range. \$\endgroup\$ – Stefan Hanke Jan 6 '15 at 12:08

12 Answers 12

69
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice. This is makes a lot of sense and is very easy to implement. Thanks \$\endgroup\$ – carbon_ghost Jan 6 '15 at 2:32
  • \$\begingroup\$ @2501, is it possible to merge the arrays in-place in linear time? I can implement this algorithm using a second array but I can't find a way to use less than linear memory. \$\endgroup\$ – user2023861 Jan 9 '15 at 22:23
19
\$\begingroup\$

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);
        }
};
\$\endgroup\$
  • \$\begingroup\$ Provide an answer like this in the interview and you don't even have to finish the test! ;) \$\endgroup\$ – glampert Jan 6 '15 at 14:23
  • \$\begingroup\$ your code doesn't compile. ideone.com/MKmTlF \$\endgroup\$ – MORTAL Jan 7 '15 at 5:43
  • 1
    \$\begingroup\$ @MORTAL: It worked fine with g++ 4.2.1. Now (with the addition of : public std::iterator<std::output_iterator_tag,int>) it also works with g++ 4.8. ideone.com/RWUnvj \$\endgroup\$ – Martin York Jan 7 '15 at 6:52
  • \$\begingroup\$ thanks a lot . but in VC++ 2013 wont compile unless i define assign operator like this SquarePushBackIterator& operator=(SquarePushBackIterator& lr) { return *this; }. it looks weird but it do the trick \$\endgroup\$ – MORTAL Jan 7 '15 at 7:06
12
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ Nice idea. It would be good though if you provided some text to go along with the algorithm. (and as a side note, the abs() when squaring is not needed) \$\endgroup\$ – Cornstalks Jan 6 '15 at 3:30
  • \$\begingroup\$ Minor point : the abs(arr[back]) is unnecessary, arr[back] will suffice. \$\endgroup\$ – Magoo Jan 6 '15 at 9:15
  • 3
    \$\begingroup\$ @Magoo: abs is also required for arr[back]. For example, consider an input of only negative numbers. \$\endgroup\$ – DarkDust Jan 7 '15 at 17:05
8
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ +1 perfect answer for me, but i have question if you not mind, i would like to know is there any benefit for using std::find_if over std::lower_bound \$\endgroup\$ – MORTAL Jan 6 '15 at 21:31
  • \$\begingroup\$ @MORTAL I believe there is benefit in using std::lower_bound (log(n)) since find_if is O(n), lower_bound is better since we know the list is sorted, but this doesn't change the overall complexity. \$\endgroup\$ – ryanpattison Jan 6 '15 at 22:50
  • \$\begingroup\$ @MORTAL Yeah, you're right, std::lower_bound would be better here - just skipped my mind when I was writing this. \$\endgroup\$ – Yuushi Jan 7 '15 at 3:15
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Though I like your solution (+1). I think you have written it in a way that is unreadable and thus unmaintainable. White space/comments and shorter lines would all be beneficial. Cramming everything onto one line is not always the best solution. \$\endgroup\$ – Martin York Jan 6 '15 at 18:29
  • \$\begingroup\$ @LokiAstari I don't see the cramming and unmaintainability but I tried applying your advice. \$\endgroup\$ – nwp Jan 6 '15 at 19:19
  • 2
    \$\begingroup\$ Of course you don't see it; you just wrote it. But put it back to the original and come back in 6 months and see if you still understand it. Much nicer now and easy to read now. Went overboard with comments on the merge. \$\endgroup\$ – Martin York Jan 6 '15 at 19:21
  • \$\begingroup\$ @nwp Yes, unfortunately I was not allowed to use any inbuilt libraries. \$\endgroup\$ – carbon_ghost Jan 7 '15 at 2:59
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Unless there's some previously undisclosed requirement to make the source code brutally short, this answer would really benefit from descriptive variable names and an infusion of whitespace. \$\endgroup\$ – Edward Jan 7 '15 at 22:32
  • 1
    \$\begingroup\$ l ends up being sorted backwards. \$\endgroup\$ – 200_success Jan 8 '15 at 11:04
  • \$\begingroup\$ do/while will cause failure on an empty array. An empty array fits the problem space, it is a trivial case of sorted array. \$\endgroup\$ – chqrlie Mar 24 '15 at 22:53
  • \$\begingroup\$ Or even have nested while <, while > and while == loops, testing for pointers met in the latter, only. \$\endgroup\$ – greybeard Jan 16 '16 at 13:22
0
\$\begingroup\$

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 << ' ';
}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.