Given an array, find the two sum.

Solution 1: Hash map approach

Our solution processes the input array by iterating through it while maintaining a hash map of previously seen elements and their indices. For each element, it calculates the complement (i.e., target - nums[i]) and checks if this complement is already present in the hash map. If the complement is found, it means we have identified a pair of indices that sum up to the target, and we return these indices. If no such pair is found by the end of the iteration, we return an empty array.

The solution uses a hash map (or unordered map) to achieve efficient lookups and insertions. This approach ensures that each element is processed only once, making it both readable and performant.

Time Complexity: The solution has a time complexity of O(n), where n is the number of elements in the array. This is because we iterate through the array once, performing constant-time operations (hash map lookups and insertions) for each element.

Space Complexity: The solution uses O(n) space for the hash map that stores the indices of the elements. In the worst case, if all elements are unique, the hash map will contain n entries.

Solution 2: Two-pointer approach

In this approach, we sort the input array first and then use a two-pointer technique to find the pair of numbers that sum up to the target. The idea is to place one pointer at the beginning (left) and another at the end (right) of the sorted array. We compute the sum of the elements at these two pointers.

• If the sum equals the target, we need to find the pair with the lowest index right number. We iterate from the current right pointer to find the smallest index where the number is equal to the current right value and ensure that right != left. This step ensures that if there are multiple pairs summing to the target, we return the indices of the pair where the numbers appear first in the array.

• If the sum is less than the target, we move the left pointer to the right to increase the sum.

• If the sum is greater than the target, we move the right pointer to the left to decrease the sum.

Sorting the array allows us to effectively narrow down our search using the two-pointer technique, and iterating to find the lowest index right number ensures we return the correct pair according to the problem's requirements.

Time Complexity: The time complexity of this solution is O(n log n) due to the sorting step. After sorting, the two-pointer traversal takes O(n) time, but sorting dominates the complexity.

Space Complexity: The space complexity is O(n) to store the original indices along with the elements of the array, which is necessary to return the correct indices after sorting.

In what situation would we go for Solution 2 (two-pointer approach) over Solution 1?