1. Two Sum

Reference: LeetCode
Difficulty: Easy

Problem

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].

Analysis

Brute-Force

public int[] twoSum(int[] nums, int target) {
  // Assume nums is not null
  int n = nums.length;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) { // j = i + 1 since we cannot use the same element twice
      if (nums[i] + nums[j] == target) {
        return new int[] { i, j };
      }
    }
  }
  throw new IllegalArgumentException("No two-sum solution");
}

Time: $O(N^2)$ 18 ms
Space: $O(1)$

Hash Table

Note: The order of the indices in the return array does not matter.

Reduce the look-up time from $O(N)$ to $O(1)$ by trading space for speed.

Two-pass: 2 ms

public int[] twoSum(int[] nums, int target) {
  // Assume nums is not null
  int n = nums.length;
  Map<Integer, Integer> map = new HashMap<>(); // <val, idx>
  for (int i = 0; i < n; ++i) {
    map.put(nums[i], i);
  }
  for (int i = 0; i < n; ++i) {
    int val = target - nums[i];
    if (map.containsKey(val) && map.get(val) != i) {
      return new int[] { map.get(val), i };
    }
  }
  throw new IllegalArgumentException("No two sum solution");
}

One-pass: 2 ms

public int[] twoSum(int[] nums, int target) {
  // Assume nums is not null
  int n = nums.length;
  Map<Integer, Integer> map = new HashMap<>(); // <val, idx>
  for (int i = 0; i < n; ++i) {
    int val = target - nums[i];
    if (map.containsKey(val)) {
      return new int[] { map.get(val), i };
    }
    map.put(nums[i], i);
  }
  throw new IllegalArgumentException("No two sum solution");
}

Time: $O(N)$
Space: $O(N)$