top-interview-questions/easy/array/08_move_zeroes.cc


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // Invariant: left subset of array satisfies requirement.
        bool sorted = false;
        for (size_t i = 0; (i < nums.size()) && !sorted; ++i) {
            if (nums[i] == 0) {
                // Look for j>i with which to swap this 0.
                // If not found, then we're done.
                bool found = false;
                for (size_t j = i+1; j < nums.size(); ++j) {
                    if (nums[j] != 0) {
                        nums[i] = nums[j];
                        nums[j] = 0;
                        found = true;
                        break;
                    }
                }
                sorted = !found;
            }
        }
    }
};