Leetcode Two Sum Problem solution(Java)

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

Our goal in this problem is finding indices of two numbers in given array and their sum should be the target number. The first solution that comes to mind is to check all numbers and find complement of them in the array. It is called Brute-force Search(https://en.wikipedia.org/wiki/Brute-force_search) and must be the easiest solution of them all.

1. Brute-force Search

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int complement; 
        //loop to check every element in the array
        for (int x = 0; x<nums.length; x++) {  
            complement = target - nums[x];
            //loop to find complement of current element
            for (int y = 0; y<nums.length; y++) { 
                //we cannot use same element twice.
                if (x ==  y) { continue; } 
                if (nums[y] == complement) {
                    return new int[] {x, y};
                }
            }            
        }
        return new int[] {0, 0};
    }
}

However, the problem is time-complexity. It is not efficient to check every number in the array. Specifically, if we consider n as a size of given array, our pathetic computer have to compare the first element with n-1 other elements following it, and compare the second element with n-2 other elements following it, and so on. So, the computer have to do (n-1)*n/2 operations. In short, it has O(n²) time complexity.

Then, how can we reduce the number of operations? It depends on how we rearrange this array. If computer is able to find numbers immediately by its value, not searching them sequentially, time complexity will be significantly improved. Hash table(https://en.wikipedia.org/wiki/Hash_table) is a perfect example.

2. Hash table

Hash table is a data structure that uses a hash function to get an index of specific element in the array. It receives pairs of key and value, and store each value at the index calculated by applying the key to the hash function. Sometimes calculated indices can be overlapped and how many times overlap of indices occurs(Hash collision) is one of criteria measuring performance of hash table.

In Java, HashTable and HashMap are frequently used implementations of hash table but HashMap is more recommended way to use since HashMap tends to have less hash collision thanks to additional hash function. The following is basic operations of HashMap.

import java.util.HashMap;
//declare HashMap object
//HashMap <type of key, type of value>
// = new HashMap<type of key, type of value>();
HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
//Adding an element into HashMap
map.put(4, 7);
//Finding an element from HashMap by index
int value = map.get(4);
//Checking whether the key is in HashMap or not.
boolean contain = map.containsKey(4);

3. Reducing time complexity

If we use HashMap to store numbers and indices of given array, finding complement of each number will be way faster than searching them sequentially. Its time complexity is O(1) to find complement since HashMap calculates, not searching, the index based on the key. So, if we store n elements in the HashMap(O(n)) and determine whether each element’s complement is in the HashMap or not(O(1)), time complexity of our program will be O(n). Written below is the code and comments implementing things I mentioned above.

import java.util.HashMap;
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap <Integer, Integer> map 
            = new HashMap<Integer, Integer>();
        int complement;
        //loop to check every element in the array
        for (int i = 0; i<nums.length; i++) {
            complement = target - nums[i];
            //if we already have the complement in HashMap,
            //return an array that contains indices of them.  
            if (map.containsKey(complement)) {
                return new int[] {i, map.get(complement)};
            }
            //if its complement is not in HashMap but in the array,
            //they will be matched when the complement is 
            //regarded as current element.
            //add current element into HashMap.
            map.put(nums[i], i);
        }
        //Exception which says it is unavailable to find solution
        //with these arguments.
        throw new IllegalArgumentException("No solution");
    }
}