dosentmatter

I don't think Solution 2 is always better than Solution 3

First of all, it doesn't matter unless n is large, since both are O(n).

For both Solutions 2 and 3, you can skip operations when there are non-zeros at the beginning of the array by doing the following:
For Solution 2, you can skip moving when `lastNonZeroFoundAt == i`
For Solution 3, you can skip swapping when `lastNonZeroFoundAt == cur`

For Solution 2, even if you do a memset, that is an O(n) because it has to write each element to 0.
For Solution 3, we can say that swap is a 3 cost operation since it does 3 writes including the temporary variable.

ar-pa

// In the name of Allah.
// We're nothing and you're everything.
// Ya Ali!
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int maxn = 1e2 + 14, lg = 15;