LeetCode 1. Two Sum

Description

https://leetcode.com/problems/two-sum/

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9, 
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Explanation

The question is about finding two elements in an array that they add up to a given target.

Simply, we can use a nested loop to solve. We can use a variable i to visit each element and use another variable j to check if there is another element in array add variable i value equal to target. The idea is easy. However, the solution is not efficient. The time complexity would be O(N²).

There is a better way to solve the problem. We can introduce a HashMap to reduce time complexity. The HashMap stores visited element values and indexes. Every time we visit an element, we store the element value and index into the HashMap, and we check if the current element’s complement already exists in the HashMap. If the complement exists, we find a solution. The solution is efficient. Time Complexity is O(N).

Java Solution

public class Solution {

  public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];

    Map<Integer, Integer> visited = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
      if (visited.containsKey(target - nums[i])) {
        result[0] = visited.get(target - nums[i]);
        result[1] = i;
        return result;
      }
      visited.put(nums[i], i);
    }

    return result;
  }
}

Python Solution

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

3 Thoughts to “LeetCode 1. Two Sum”

  1. This is *time* efficient but not *space* efficient. If we are not permitted to use extra space then sorting in place and using pointers is an O(nlogn) solution.

Leave a Reply

Your email address will not be published. Required fields are marked *