SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

The twoSum problem requires finding two distinct indices in an array such that the elements at these indices sum up to a given target value. A brute-force approach would involve checking all pairs of elements to see if they sum up to the target, but this results in O(n^2) time complexity, which is inefficient for large arrays. To optimize, we can use a hash map (dictionary) to store the difference between the target and each element as we iterate through the array. This allows us to check for the required pair in constant time.

Approach

1. Initialization: Create an empty dictionary (complement_map) to store the complement of each number encountered (i.e., target - current number).

2. Iteration: Loop through the array using a single pass.

   • For each element, calculate its complement with respect to the target (complement = target - nums[i]).
   • Check if this complement is already in the dictionary:
     • If it is, return the indices of the current element and the complement stored in the dictionary.
     • If it is not, add the current element and its index to the dictionary.

3. Output: Since the problem guarantees exactly one solution, the function will always return a valid pair of indices.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. This is because we traverse the array once, and each dictionary operation (insertion and lookup) is O(1) on average.

Space Complexity:

O(n), where n is the number of elements in the array. In the worst case, we store all elements in the dictionary.

Code

C++

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        std::unordered_map<int, int> num_map;
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (num_map.find(complement) != num_map.end()) {
                return {num_map[complement], i};
            }
            num_map[nums[i]] = i;
        }
        return {};
    }
};

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        complement_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in complement_map:
                return [complement_map[complement], i]
            complement_map[num] = i

Java

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

JavaScript

var twoSum = function(nums, target)
{
  let length = nums.length - 1
  for (let i = 0; i < length; i++)
  {
    let goal = target - nums[i]
    let index = nums.indexOf(goal, i+1)
    if (index !== -1) {
      return [i, index]
    }
  }
};