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

Bash

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()

Python

[1, 0]

Bash

Complexity

• when move array into a dict, time complexity is On; hash table search is O1; so overall time complexity is On
• Space complexity is On, 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: On
• l = 0, r = lennums - 1
• while l < r
  • if nums[l] + nums[r] == target, return [nums2.indexnums[l], nums2.indexnums[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()

Python

[1, 2]

Bash

We need to sort the arrays first, in python the time complexity for sorted method is Onlogn, space complexity is On as we need additional ds to store the results.