add version 2, which reduced the  time complexity from o(2n) to o(1.5n), however this method changed the input array