Move all zeros to end of array

[koopey]

can't figure out why my code isn't showing any output. any help will be appreciated.

the question is:
Given an array of random numbers, Push all the zero’s of a given array to the end of the array. For example, if the given arrays is {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0}, it should be changed to {1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0}.

source: https://practice.geeksforgeeks.org/problems/move-all-zeroes-to-end-of-array/0

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

void rearrange(vector<int> &vec){
    auto vecend=vec.end();
    for(auto itr=vec.begin();itr!=vecend;itr++){
        if(*itr==0){
            vec.erase(itr);
            vec.push_back(0);
            itr--;
        }
    }
}

void print(vector<int>& vec){
    for(auto& i:vec)
        cout<<vec[i]<<" ";
    cout<<endl;
}

int main() {
	int t,size;
	vector<int> vec;
	cin>>t;
	while(t--){
	    cin>>size;
	    for(int i=0;i<size;i++){
	        int temp;
	        cin>>temp;
	        vec.push_back(temp);
	    }
		cout<<"into function";
	   rearrange(vec);
	   cout<<"out of function";
	   print(vec);
	   vec.clear();
	}
	return 0;
}

[H00G0]

Well why did you use vectors if you wanted to deal with arrays?

Assuming you already defined and initialised your array. Here's a pseudocode for how you could work with your assignment:

void arrrangeArray(int array)
{
     for (counter; as long as counter is lower than array size, increment counter)
    {
          if (array[counter] is equal to 0)
          {
                for (another counter; counter is less than array size; increment counter)
                {
                       if (array[counter] is the last member of the array)
                              array[counter] = 0;
                       else
                              array[counter] = array[counter + 1];
                }
          }
     }
 }

this function would shift all non 0 numbers to the left and place a 0 at the last sport of the array.

I hope this is clear and understandable enough, and hope that helps.

Regards,

Hoogo.

[Thomas1965]

Maybe like this:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

void rearrange(vector<int> &vec) 
{
  auto first = 0;
  auto last = vec.size() - 1;
  while(vec[last] == 0) // find last non-zero elem
    last--;

  while(first < last)
  {
    if (vec[first] == 0)
    {
      swap(vec[first], vec[last]);
      while (vec[last] == 0) // find new last
        last--;
    }
    first++;
  }
}

void print(vector<int>& vec) 
{
  for (auto& i : vec)
    cout << i << " ";
  cout << endl;
}

int main() 
{
  vector<int> vec = { 1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0 };
  cout << "Original vector\n";
  print(vec);
  cout << "After rearrange\n";
  rearrange(vec);
  print(vec);
}

Output:

Original vector
1 9 8 4 0 0 2 7 0 6 0
After rearrange
1 9 8 4 6 7 2 0 0 0 0

[Peter87]

i on line 18 is the element, not an index.

cout << i << " ";

The erase function invalidates all iterators to the erased element and to the elements that comes after. This means that when you call erase on line 9 vecend and itr will no longer be valid to use before you have assigned a new valid iterator value to them.

The erase function returns an iterator to the element that comes after the erased element so you could use that to fix the issue of itr being invalidated, but in that case you don't want to increment it so you need to write it in the else-part of the if-statement so that it is only executed when an element is not erased.

auto vecend=vec.end();
for(auto itr=vec.begin();itr!=vecend;){
	if(*itr==0){
		itr = vec.erase(itr);
		vec.push_back(0);
	} else {
		itr++;
	}
}

You still need to solve the issue of vecend being invalidated. You might find it easier working with indices, or simply write it in a way that doesn't invalidate iterators (e.g. by swapping values into their correct position rather than adding and removing).

[keskiverto]

The Standard library has partition and stable_partition:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void print(vector<int>& vec) 
{
  for (auto& i : vec)
    cout << i << " ";
  cout << endl;
}

int main() 
{
  vector<int> vec = { 1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0 };
  cout << "Original vector\n";
  print(vec);
  cout << "After rearrange\n";
  std::partition( vec.begin(), vec.end(), [](int x) -> bool {return x;} );
  // std::stable_partition( vec.begin(), vec.end(), [](int x) -> bool {return x;} );
  print(vec);
}

http://www.cplusplus.com/reference/algorithm/partition/
http://www.cplusplus.com/reference/algorithm/stable_partition/

One of those pages presents a sample implementation. The stable's does not, but the complexity analysis is telling.

If one would take http://www.cplusplus.com/reference/algorithm/remove/ but rather than plainly overwriting the removed values, one would move them into temporary memory and once the "remove" is complete return data from temporary to tail part of the array.


We have a special case though: the "pushed values" are plain 0. Order of 0's does not matter. We don't have to preserve the values we read from array and move them to the end. A "fresh" 0 is indistinguishable from "old" 0.

void rearrange( std::vector<int> &vec )
{
    auto tail = std::remove( vec.begin(), vec.end(), 0 );
    std::fill( tail, vec.end(), 0 );
}

[koopey]

@hoogo actually i just learnt about vector's erase function. so I wanted to make use of it, just for practice.

@Thomas1965 i too did the way you did it initially, but the online judge didn't accept it. althought not mentioned explicitly, it turned out that the order of the number had to be maintained. so the solution has to be:
{1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0}. and not 1 9 8 4 6 7 2 0 0 0 0

@Peter87

The erase function invalidates all iterators to the erased element and to the elements that comes after.

thanks, i didn't kow that and i learnt sth imp. to work around vecend problem, i did this.(though it's quite dirty)

int count=0; //global variable

void rearrange(vector<int> &vec){
    auto vecend=vec.end();
    for(auto itr=vec.begin();itr!=vecend-count;itr++){
        if(*itr==0){
            itr=vec.erase(itr);
            vec.push_back(0);
            itr--;
			count++;
			vecend=vec.end();
        }
    }
}

Though this produces right output on my ide, this exceeds time limit in online judge. I'll have to go back to using array.

@keskiverto the links seems interesting, i ll have a look at it.

@ALL OF THE ABOVE
I have quite confusion on this part of the code though.

cin>>size;
		vector<int> vec(size,-1);// q1) is it okay to dynamically allocate vector like this
	    for(int i=0;i<size;i++){
	      cin>>vec[i];
		  cout<<"printing i:"<<i<<endl;
	    }
		cout<<"into function";// q2) the error was on the rearrange function above. but this part was never 
//printnted, before i changed rearrange funcion. why so? as this is before rearrange() was called
	   rearrange(vec);

[Peter87]

to work around vecend problem, i did this.(though it's quite dirty)

Unfortunately that won't work if the first element is erased because itr-- will step out of bounds.

[koopey]

@Peter87 that's true. i ' ll just go back to using good old arrays.
any idea on the dynamically allocating vector part, mentioned above, though?

[Peter87]

ll just go back to using good old arrays.

Vector is not the problem. You would face the exact many of the same problems with array iterators (pointers). If you find it easier working with indices you can do that with vector just like you do with arrays.

any idea on the dynamically allocating vector part, mentioned above, though?

The vector uses dynamic allocations internally but the vector object itself is not dynamically allocated. If you are asking about the dynamic size that's just fine with vectors. vector<int> vec(size,-1); creates a vector containing size number of elements that are initialized to -1.

[lastchance]

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

template <typename Container, typename T> void moveToEnd( Container &C, int size, T value )
{
   int to = 0, from = 1;
   for ( ; to < size; to++ )
   {
      if ( C[to] == value )                                     // Value to be moved to end
      {
         if ( from <= to ) from = to + 1;
         while ( from < size && C[from] == value ) from++;      // Find next non-value
         if ( from >= size ) return;
         C[to] = C[from];
         C[from] = value;
      }
   }
}


int main()
{
   int A[] = { 3, 4, 0, 0, 2, 0, 6, 9 };
   int Aval = 0;

   vector<int> B = { 13, 14, 0, 0, 20, 0, 16, 19 };
   int Bval = 0;

   string C = "CDxxBxFI";
   char Cval = 'x';


   cout << "\nInteger array before: ";   for ( int i : A ) cout << i << ' ';
   moveToEnd( A, sizeof( A ) / sizeof( A[0] ), Aval );
   cout << "\nInteger array after:  ";   for ( int i : A ) cout << i << ' ';

   cout << "\nVector before: ";   for ( int i : B ) cout << i << ' ';
   moveToEnd( B, B.size(), Bval );
   cout << "\nVector after:  ";   for ( int i : B ) cout << i << ' ';

   cout << "\nString before: ";   cout << C;
   moveToEnd( C, C.size(), Cval );
   cout << "\nString after:  ";   cout << C;
}

Integer array before: 3 4 0 0 2 0 6 9 
Integer array after:  3 4 2 6 9 0 0 0 
Vector before: 13 14 0 0 20 0 16 19 
Vector after:  13 14 20 16 19 0 0 0 
String before: CDxxBxFI
String after:  CDBFIxxx

[keskiverto]

The single erase approach requires:

3 4 0 0 2 0 6 9
# move 5 elements left and assign one
3 4 0 2 0 6 9 0
# move 5 elements left and assign one
3 4 2 0 6 9 0 0
# move 4 elements left and assign one
3 4 2 6 9 0 0 0

That was 14 moves to get 3 values where they should be. In addition, the erase and push_back modify the vector's size.

Lastchance's:

3 4 0 0 2 0 6 9
# move the 2
3 4 2 0 0 0 6 9
# move the 6
3 4 2 6 0 0 0 9
# move the 9
3 4 2 6 9 0 0 0

That was 3 moves.

Both approaches assign the value 0 for 3 times as they should.

The remove-fill:

3 4 0 0 2 0 6 9
std::remove performs 3 moves
3 4 2 6 9 X X X
std::fill assigns 3 values
3 4 2 6 9 0 0 0

std::remove and std::fill do work on vectors/arrays/strings. They are generic algorithms.

You should look up "remove erase idiom" too.