Solution 1 (Runtime: 40 ms Memory Usage: 13.9 MB) Time complexity is O(n). Space complexity is O(n).
Solution 1 (Runtime: 1288 ms Memory Usage: 14.6 MB) Solution 2 (Runtime: 60 ms Memory Usage: 15.2 MB) Time complexity of solution 1 is O(n*n). Time complexity of solution 2 is O(n). Because dictionary offer O(1) lookup time. Space complexities of both of them are O(n).