1-TwoSum

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

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Thought Process

• create a dictionary to store the data where k = data, value = data index
• for num in dictionary, check if target - num exists in the rest of the array, if exist return the index of num and target-num
• the problem assumes each input would have exactly one solution, however just in case there’s no solution return false

issues

• however, there are issues with this solution, if there are repetitive elements, then we will have collision, the new element will replace the previous element
• the root cause of this issue is bc we put all elements into the hash table all at once, the search can be a dynamic process as below:
• for any given state:
  • at index i, we move to value v, all elements before v were moved into the hash table already
  • if target - v exists in the hash table, return [i, ht[target-v]]
  • else i += 1, so new v will replace the old v, since the problem assumes only 1 solution, we can confirm that:
    • [v, v] wont be a solution
    • after new v replace old v, it doesn’t matter which v is used for a potential solution that v + w = target
    • however, if the problem asks for all the solutions, it requires a different ds, maybe a stack?

White Board

Below is the white board:

Code

class Solution:
    def two_sum(self, nums, target):
        res_d = {}
        for i in range(len(nums)): #O(n)
            substrate = target - nums[i]

            if substrate in res_d:
                return [i, res_d[substrate]]
            else:
                res_d[nums[i]] = i

        return False

def test():
    nums = [3, 3]
    target = 6
    ts = Solution().two_sum(nums, target)

    print(ts)

test()

[1, 0]

Complexity

• when move array into a dict, time complexity is O(n); hash table search is O(1); so overall time complexity is O(n)
• Space complexity is O(n), as I created both a dict to store results

Optimization

This is not an optimization, more of an alternative thinking. If we sort the array first, I can use two pointers, l, r:

• since sorting will destroy the order, so make a copy of nums, nums2: O(n)
• l = 0, r = len(nums) - 1
• while l < r
  • if nums[l] + nums[r] == target, return [nums2.index(nums[l]), nums2.index(nums[r])]
  • elif nums[l] + nums[r] < target, l += 1
  • else r -= 1

class Solution2:
    def two_sum2(self, nums, target):
        nums2 = nums.copy()
        nums3 = nums.copy()
        nums = sorted(nums)
        l, r = 0, len(nums)-1
        while l <= r:
            if nums[l] + nums[r] == target:
                if nums2.index(nums[l]) != nums2.index(nums[r]):
                    return [nums2.index(nums[l]), nums2.index(nums[r])]
                else:
                    nums3[nums2.index(nums[l])] = None
                    return [nums2.index(nums[l]), nums3.index(nums[r])]
            elif nums[l] + nums[r] < target :
                l += 1
            else:
                r -= 1

        return False

def test_two_sum2():
    # nums = [2,7,11,15]
    # target = 9
    nums = [3,2,4]
    target = 6

    inter = Solution2().two_sum2(nums, target)
    print(inter)

test_two_sum2()

[1, 2]

We need to sort the arrays first, in python the time complexity for sorted method is O(nlogn), space complexity is O(n) as we need additional ds to store the results.