all articles

leetcode war 1 - two sum

2016-09-16 @sunderls

leetCode

following solutions are all created by myself, if I didn't tackle it and got solution from editorial solution, it will be made clear at the heading.

LeetCode War 1. two-sum

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.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].

solution 1 - brute force

just for two for loop

var twoSum = function twoSum(nums, target) {
    var length = nums.length;
    for (var start = 0; start < length; start++) {
        for (var end = start + 1; end < length; end++) {
            if (nums[start] + nums[end] === target) {
                return [start, end];
            }
        }
    }
};

it has O(n2) time complexity. cost 195 ms(this is from leetcode result)

solution 2 - search counterpart

When we traverse the array, we search the counterpart, it found then return result.

var twoSum = function twoSum(nums, target) {
    var length = nums.length;
    for (var start = 0; start < length; start++) {
        var end = nums.indexOf(target - nums[start]);
        if (end > -1 && end !== start){
            return [start, end]
        }
    }
};

With the traversing at O(n) & the search at O(n) ( at best O(log n) for sorted input array), so totally still at O(n2) time complexity. Actually it got worse result at 302ms.

solution 3 - reverse indexing

We can store the all the numbers in a hashmap, so we can access the counterpart at O(1).

var twoSum = function twoSum(nums, target) {
    var map = {};
    var length = nums.length;
    for (var i = 0; i < length; i++) {
        map[nums[i]] = i;
    }

    for (var start = 0; start < length; start++) {
        var end = map[target - nums[start]];
        if (end !== undefined && end !== start){
            return [start, end];
        }
    }
};

Overall we got O(n) at time & O(n) at space. It costs 95ms.

Editorial Solution

I did it OK, but not perfect, solution 3 can be actually improved, from 2-pass to 1-pass iterations. While we are hashing, we check the hashmap. SO I SHOULD! The complexity stays the same though, and it got 98ms, the same as above.

var twoSum = function twoSum(nums, target) {
    var map = {};
    var length = nums.length;

    for (var start = 0; start < length; start++) {
        var end = map[target - nums[start]];
        if (end !== undefined && end !== start){
            return [start, end];
        }

        map[nums[start]] = start;
    }
};