Duplicate Zeros

c// class Solution {
// public:
//     void duplicateZeros(vector<int>& arr) {
//         vector <int> dup;
//         for(int i=0;i<arr.size();i++){
//             dup.push_back(arr[i]);
//         }
//         int i=0,k=0;
//         for(int i=0;i<arr.size() && k<arr.size();i++){
//             if(dup[i]==0){arr[k++]=0;
//                           if(k<arr.size())
//                              arr[k++]=0;}
//             else arr[k++]=dup[i];
//         }

//     }
// };

/*
 T.C O(n) two pass, space complexity O(1)
 Logic:
 We can find that what are the elments will be inside array after modification.
 so found the last index of element which will be present in array after first
 loop.

[8,4,5,0,0,0,0,7]   example of k>arr.size()
*/

class Solution {
public:
    void duplicateZeros(vector<int>& arr){
        int k=0,i=0;
        for(i=0;i<arr.size();i++){
            if(arr[i]==0) k+=2;
            else k++;
            if(k>=arr.size()) break;
        }
        int j=arr.size()-1;
        if(k>arr.size()){     //If k is more than arr.size() means last element is 0 and it should be in
             arr[j--]=arr[i--];  //array only one time at the last position.
        }
        for(i;i>=0;i--){
            if(arr[i]==0){ arr[j--]=arr[i]; arr[j--]=arr[i];}
            else arr[j--]=arr[i];
        }

    }
};