Python Algorithm Q7

November 27, 2021

Q7 two-sum

Q

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Sample Input

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

1. My Solution == Given Solution #1

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if (nums[i]+nums[j])==target:
                        return [i, j]

#for testing
a = Solution()
nums = [3, 2, 4]
target = 6
print(a.twoSum(nums, target))

[Brute Force]
My answer is by using brute force. Skip additional commentary. (Book answer is also same as mine.)

2. Given Solution #2

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i, n in enumerate(nums):
        complement = target - n

        if complement in nums[i+1:]:
            return [nums.index(n), nums[i+1:].index(complement)+(i+1)]

[Brute Force]
This method is derived from brute force. Just changed from “double for-loop” to “searching by in” algorithm. Still Big O(time complexity) is n^2, but it takes significantly less time than just using brute force. That’s because using “in” is much faster than comparing each element.

Simply explaining, in Nth loop, define complement as “target-Nth element”. Then check whether complement exist in the array “nums” beyond the Nth index.

3. Given Solution #3

def twoSum(self, nums: List[int], target: int) -> List[int]:
    nums_map = {}
    #change key&value, then save it to the dictionary
    for i, num in enumerate(nums):
        nums_map[num]=i #key is the value of the array, "num", and value is its idx.

    
    for i, num in enumerate(nums): #just nums_map(dict name) = key returns.
        #check whether target-num in dict keys & filter if it is double-used (by checking "i")
        #++to prevent the event when target-num == num by checking index, "i"
        if target-num in nums_map and i != nums_map[target-num]:
            return [i, nums_map[target-num]]

[Using “in”]
This method changed little bit from before. In for loop(variable = X), search “target - X” in dict key. Of course repeated usage of number should be prevented(by i != nums_map[target-num]). This method’s Big O is generally O(1) (In worst case, O(n)). So, it’s much better algo than before.

4. Given Solution #4

def twoSum(self, nums: List[int], target: int) -> List[int]:
    nums_map = {}
    for i, num in enumerate(nums):
        if target-num in nums_map:
            return [nums_map[target-num], i]
        nums_map[num] = i

[Searching structure improvement]
Almost same as given sol #3, but code is cleaned up. Shorten than before. #3 saves all value to dict, but this can escape earlier when it finds solution. This solution prevents returning double-used case. It is because prior to returning answer, “target-num” should be contained in “nums_map”. If not, that case passes and registered in nums_map dictonary. (따라서 target-num = num 일지라도, nums_map에 등록이 안되어 있으므로 if문을 통과해버리는 방식으로 원소를 두 번 쓰는 케이스를 방지)

5. Given Solution #5

** Prior to solution, double-pointer answer has essential prerequisite - input array have to be sorted. Using nums.sort() to sort the input array, but this can not be the solution that index of the original array will be messed up. Therefore, in general case, this solution can not be the proper answer.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    left, right = 0, len(nums) - 1 #left = 0 / right = len-1
    while not left == right: #until it is same
        if nums[left] + nums[right] < target:
            left+=1
        elif nums[left] + nums[right] > target:
            right-=1
        else:
            return [left, right]

Overall Review

Problem itself is not that much hard. Just using brute force, you can solve it. But as you expect, using brute force takes significantly large time, O(n^2). Therefore knowing other optimized answer as well is very important. Just changing method, “double-for-loop” to “searching by in” can improve the execution time(of course, just little bit). Also adopting dictionary remarkably decreases the time consumption because dictionary is shaped by hash table(Most method is O(1)). Python has various ways to optimize…

Hyuntae H