I spent a little bit of time and wrote a more idiomatic Rust implementation of your algorithm. No idea how it compares to the others, and I haven't checked its output for correctness beyond seeing that the first example leaves no empty values.
Edit: On the playground, in release mode, your first 100 test cases get solved in 1019 ms (sample of 1).