Problem Explanation

This problem is asking us to find two numbers in an array which gives the sum of the target number. We are given an integer array and a target number, we just need to find the index positions of two numbers in the array which gives the sum as the target number.

For example, let's say are given an array [2, 7, 11, 15] and the target is 9. The resultant index positions are [0, 1] as the numbers 2 and 7 (which are present at index 0 and 1 respectively) gives the sum as 9.

Approach

We can solve this problem by using a hashtable or dictionary. It will help us track the index of the numbers we have encountered so far.

The key idea here is, for every number in the array, we will check if we have already seen a number that, if added to the current number, would result in the target sum. If we haven't, we will store the current number with its index into the hashtable. If we have, we immediately return the current index and the index of the previously seen number from the hashtable.

Algorithm Walk-through

1. Define a hashtable.
2. We start traversing the array. For each number: 2.1 Calculate the complement of the current number (i.e., difference of the target and current number). 2.2 Check if the complement has already been encountered (i.e., if the complement exists in hashtable). 2.2.1 If it has been encountered, return its index (obtained from hash) as well as the current index. 2.2.2 If it hasn't been encountered, store the current number with its index into the hashtable.
3. If we reach the end of the array and haven't found any two numbers that sum to the target, return an appropriate error.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  vector<int> twoSum(vector<int>& nums, int target) {
6    unordered_map<int, int> numToIndex;
7    for (int i = 0; i < nums.size(); ++i) {
8      int complement = target - nums[i];
9      if (numToIndex.find(complement) != numToIndex.end())
10        return {numToIndex[complement], i};
11      numToIndex[nums[i]] = i;
12    }
13    throw out_of_range("No two sum solution");
14  }
15};

Python Solution

1
2python
3class Solution:
4    def twoSum(self, nums: List[int], target: int) -> List[int]:
5        num_to_index = {}
6        for i, num in enumerate(nums):
7            complement = target - num
8            if complement in num_to_index:
9                return [num_to_index[complement], i]
10            num_to_index[num] = i
11        raise Exception("No two sum solution")

Java Solution

1
2java
3class Solution {
4    public int[] twoSum(int[] nums, int target) {
5        Map<Integer, Integer> numToIndex = new HashMap<>();
6        for(int i = 0; i < nums.length; ++i){
7            int complement = target - nums[i];
8            if(numToIndex.containsKey(complement)){
9                return new int[]{ numToIndex.get(complement), i };
10            }
11            numToIndex.put(nums[i], i);
12        }
13        throw new IllegalArgumentException("No two sum solution");
14    }
15}

JavaScript Solution

1
2javascript
3class Solution {
4    twoSum(nums, target) {
5        const numToIndex = {};
6        for (let i = 0; i < nums.length; ++i) {
7            const complement = target - nums[i];
8            if (complement in numToIndex) {
9               return [numToIndex[complement], i];
10            }
11            numToIndex[nums[i]] = i;
12        }
13        throw Error("No two sum solution");
14    }
15}

C# Solution

1
2csharp
3public class Solution {
4    public int[] TwoSum(int[] nums, int target) {
5        Dictionary<int, int> numToIndex = new Dictionary<int, int>();
6        for (int i = 0; i < nums.Length; ++i)
7        {
8            int complement = target - nums[i];
9            if (numToIndex.ContainsKey(complement))
10            {
11                return new int[] { numToIndex[complement], i };
12            }
13            numToIndex[nums[i]] = i;
14        }
15        throw new Exception("No two sum solution");
16    }
17}

As we can see, the algorithm works well and in an efficient way because we are traversing the array only once and that too in a linear fashion, thus the time complexity of the algorithm is O(n).# Time Complexity Analysis

The time complexity of the presented solution can be described as follows:

1. Traversing the list of numbers: The time it takes to traverse the list is proportional to the number of elements, n, in the list. Thus, this operation has a time complexity of O(n).

2. Searching for the complement of the current number in the hash table: In the worst case, this operation requires searching for the complement of the current number in a hash table containing n elements. However, the beauty of hash tables/dictionaries is that searching for a specific key can generally be accomplished in O(1) time, regardless of the number of elements in the hash table.

3. Storing the current number and its index in the hash table: Similarly, this operation involves inserting a key-value pair into a hash table, which can generally be done in constant time, O(1), regardless of the size of the hash table.

Therefore, the provided solution has a time complexity of O(n), where n is the number of elements in the array. This linear time complexity makes this solution quite efficient, particularly for large inputs.

Space Complexity Analysis

In terms of space complexity, the dominate factor is the storage required for the hash table numToIndex. In the worst case scenario, where no two numbers in the list add up to the target, this dictionary will contain n key-value pairs. So, the space taken up by the hash table is proportional to the number of elements, n, in the list.

No other data structure in this solution uses a significant amount of space that scales with the size of the input.

Therefore, the provided solution has a space complexity of O(n), where n is the number of elements in the array.

Conclusion

The algorithm is efficient with time complexity O(n) and space complexity O(n). However, the space can be traded off for speed in many practical applications where there is abundant memory resources. The solution illustrated here represents a common technique in algorithm design, which is to use a data structure that efficiently supports the required operations, even though it may use a bit more space.