Is this in linear time and constant space? (sort array, so that all 0s are at the end, other numbers are at front (solution))

user_16937633 0
Viewed 80

The problem: You are given an array of a bunch of numbers and zeros, sort it so that all the numbers that are not zero, are at the front, and all the numbers at the end are zeros.

Question: Does my solution run in Linear time ? Or not ? Also is it constant space or not?

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main()
{
    cin.tie(0);
    std::ios_base::sync_with_stdio(false);

    vector<int> MyVec;
    int input;
    int i = 0;
    stack<int> mystack;
    stack<int> zerostack;
    while((input = getchar())&& (input!=10))
    {
        if(input != 32)
        {
            MyVec.push_back(input - '0');

            if(MyVec[i] == 0)
                zerostack.push(MyVec[i]);
            else
                mystack.push(MyVec[i]);

            i++;
        }
    }
    MyVec.clear();
    while(!mystack.empty())
    {
         MyVec.push_back(mystack.top());
         mystack.pop();
    }
    while(!zerostack.empty())
    {
         MyVec.push_back(zerostack.top());
         zerostack.pop();
    }
    for(auto a : MyVec)
        cout << a << " ";

    return 0;
}
c++
2 Answers

Answer to your question

  • Your solution does not consume a constant amount of space.
    You store each element you read into MyVec and mystack or zerostack. So it'll be O(n) in terms of space consumed.

  • Your solution does run in linear time (O(n)), but it's not a single-pass algorithm.
    All your loops will loop N times or less, there are no nested loops, so it'll run in O(n) time.
    However you can still reduce the real runtime of the program by using a better algorithm.

Potential solutions

It's not very clear to me if you need to optimize the entire program or only the part where you sort the vector, so i'll add solutions for both.

Whole Program

If the whole program is to be optimized you can take advantage of the fact that only the zeroes need to be shifted to the back.

So if it's not a zero you can directly output it and if it's a zero you just need to remember to output it later after all input has been processed.

e.g.:

#include <iostream>

int main()
{
    int zeroes = 0;
    char c;
    while((std::cin >> c) && c >= '0' && c <= '9') {
        if(c == '0')
          zeroes++;
        else
          std::cout << c << " ";
    }

    for(int i = 0; i < zeroes; i++)
        std::cout << "0 ";

    return 0;
}

godbolt example

This will run in linear time (O(n)) and consume a constant amount of space.

Just the sorting of the array

in case you just need to write a function that sorts a vector, you can apply a similar technique by swapping any zeroes you encounter to the end of the vector.

This will however not preserve the order of the elements (it's an unstable sorting algorithm).

void sortVector(std::vector<int>& values) {
    int insertPosition = values.size();
    for(int i = 0; i < insertPosition; i++) {
        while(values[i] == 0 && i < insertPosition)
            std::swap(values[i], values[--insertPosition]);
    }
}

godbolt example

This will also run in linear time (O(n)) and consumes a constant amount of space (we aren't allocating anything, just shifting stuff around)

It's linear time because each iteration of the while loop decrements the number of times the for loop needs to loop.

if it actually needs to be a stable sort, then you could accomplish it in a similar fashion like the whole program answer - you keep track of the zeroes and write out the numbers, e.g.:

void sortVector(std::vector<int>& values) {
    int zeroes = 0;
    for(int i = 0; i < values.size(); i++) {
        if(values[i] == 0)
            zeroes++;
        else {
            values[i-zeroes] = values[i];
            if(zeroes > 0) values[i] = 0;
        }
    }
}

godbolt example

This has the same time-complexity and space-complexity, but sorts them in a stable way.

user_84114060

Not optimized both in time and space complexity. You used extra vector to store and print the elements. You can print those elements without help of vector.

Better you can solve it with deque in C++ STL.

user_118208990
Related