I want to document my thought process on this Leetcode question, https://leetcode.com/problems/two-sum/

First I'll try get an idea of what the function signature should be like while listening to the question. Then I'll start ask clarifying questions and come up with examples. After clarifying, I'll brainstorm some ideas to solve the problem. I want to try throwing different data structures at the problem for now, some may just be for the sake of considering them.

Function signature:

• public int[] twoSum(int[] nums, int target)

Clarifying Questions / Assumptions:

• Input: null/empty? sorted? has duplicates? Overflow/underflow when adding?
  Can use same element twice?

• Output: How to handle null / length==0 / no solution / multi solution?

Examples:

• nums = [1,2,3], target = 2

• nums = [5, 5], target = -1

• nums = null, nums = [] // invalid

Brainstorm:

What would I do if I had to solve this in real life with paper and pen?

• If nums array is small, I'd check the numbers one by one, and try to find its complement number

(n = s.length)

1. Brute force, 2 for loops:

   • For every num, try find its complement number in the remaining array.

   • time O(n^2)
     space O(1)

2. Backtracking:

   • Try choosing every num. Stop when 2 numbers are chosen and check their sum. A complex way of implementing the brute force approach.

   • time O(n^2) // O(branches^depth), branches=n, depth=2
     space O(1) // O(depth) but depth is a constant

3. Sort first + Binary search:

   • Sort first, then for every num, try find its complement number in the remaining array using binary search.

   • time O(nlogn) ~ O(n^2) // bottleneck at quicksort
     space O(logn) ~ O(n) // bottleneck at quicksort

4. Sort first + 2 pointers:

   • Sort first. Start with 2 pointers at the start and end of the array, and try to match target sum, move ptr till found or no pairs left.

   • time O(nlogn) ~ O(n^2) // bottleneck at quicksort
     space O(logn) ~ O(n) // bottleneck at quicksort

5. HashMap<Integer> seen

   • For every num, try find its complement number in the HashSet. Add current num and index to HashMap while we are still searching.

   • time O(n)
     space O(n)

Code:

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

Let me know if there is anything I should have considered, or has an error! I'm happy to get any feedback.