Question - Two Sum

Problem understanding with Example

The problem requires finding the indices of two numbers in an array such that they add up to a given target value. The input array can have positive and negative integers. The output should be the indices of the two numbers in an array, and each element can be used only once.

Example:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Corner Cases

1. What if the input array is empty? In this case, we can return an empty array.

2. What if the input array has only one element? In this case, we cannot find a pair of numbers that adds up to the target, so we can return an empty array or an error message.

3. What if there are multiple pairs of numbers that add up to the target? We can return any of the valid pairs of indices.

Intuition

A simple brute-force approach to solve this problem is to iterate through each element in the array and check if there is another element in the array that adds up to the target. However, this approach would have a time complexity of O(n^2).

A better approach would be to use a hash table to store the values and their indices while iterating through the array. For each element in the array, we can check if the difference between the target and the current element exists in the hash table. If it exists, we have found the pair of elements that add up to the target.

Approach

1. Create a hash table to store the values and their indices.

2. Iterate through each element in the array.

3. For each element, calculate the difference between the target and the current element.

4. Check if the difference exists in the hash table. If it exists, we have found the pair of elements that add up to the target. Return the indices of the current element and the difference.

5. If the difference does not exist in the hash table, add the current element and its index to the hash table.

6. If we have iterated through the entire array and have not found a pair of elements that add up to the target, return an empty array or an error message.

Complexity

• Time complexity: O(n) The time complexity of this approach is O(n) because we iterate through the array only once, and each lookup in the hash table takes constant time on average.

• Space complexity: O(n) The space complexity of this approach is O(n) because we store each element and its index in the hash table.

Code in Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int difference = target - nums[i];
            if (map.containsKey(difference)) {
                return new int[] { map.get(difference), i };
            }
            map.put(nums[i], i);
        }
        return new int[] {};
    }
}

Data structure used and reason

In this approach, we used a hash table to store each element and its index. This allows us to lookup the index of a given element in constant time on average. Using an array to store the indices would not be efficient because we would have to search for the index of each element in the array, which would have a time complexity of O(n).