I used Java to implement my solutions. My first solution passed the test with O(n) complexity in time and space. The follow-up solution dealt with reducing the space complexity to O(1).