1. Two Sum

Easy

Problem:

Return the indices of two numbers in the array that can create the target by addition.

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

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

Solutions:

Brute Force

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]

Time complexity: $O(n^2)$

Searching using in

Let's try to change the problem to search whether the answer, namely the value subtracted from the target (target - n), exists, without comparing all combinations.

class Solution:
    def twoSum(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)

Why do we need to add (i + 1) at the return statement?

Let's say we have the following input:

nums = [2, 7, 11, 15] and target = 9

We'll walk through the loop step by step:

1. For i=0, n is 2 and the complement is 9 - 2 = 7.

2. The code then checks if 7 is in the rest of the list nums[i+1 :], which is [7, 11, 15]. It is, so the if condition passes.

3. The code then returns a tuple. The first element of the tuple is the index of n (which is 2) in nums, and it's 0 (because Python uses 0-indexing), so the first element is 0.

4. The second element of the tuple is the index of complement in the rest of the list nums[i+1 :] plus (i+1). nums[i+1 :] is [7, 11, 15], and the index of 7 in this list is 0. But this is not the index of 7 in the original nums list. To get the index of 7 in the original list, you add i+1 to the index. In this case, i is 0, so i+1 is 1. So the index of 7 in the original list is 0 + 1 = 1.

So the function returns (0, 1), which are the indices of 2 and 7 in the original nums list.

The time complexity of in is $O(n)$, so the total time complexity is the same as Brute Force, which is $O(n^2)$. However, the omitted constant term here can be considered much smaller than in the previous solution.

Key lookup for the result of subtracting the first number

1. Save the dictionary with the numbers from the given array as keys and the index as the value.

2. Subtract the first number from the target and look up the result as the key.

3. At this time, add a condition to prevent the target value from being achieved by adding oneself. Consider the input nums = [3, 2, 4] and target = 6. The target can be achieved by adding the numbers at indices 1 and 2 (2 and 4 respectively), but not by adding the number at index 0 (3 + 3) to itself.

class Solution:
    def twoSum(nums: List[int], target: int) -> List[int]:
        nums_map = {}
        for i, num in enumerate(nums):
            nums_map[num] = i
        
        for i, num in enumerate(nums):
            if target - num in nums_map and i != nums_map[target - num]:
                return nums.index(num), nums_map[target_num]

Dictionaries in Python are implemented as hash tables, and in this case, lookups are possible at an average of $O(1)$. In the worst case, it can be $O(n)$, but the time complexity according to the amortized analysis is $O(1)$, and the overall time complexity is $O(n)$.

Improvement of the lookup structure

class Solution:
    def twoSum(nums: List[int], target: int) -> List[int]:
        # Combine into one for loop
        nums_map = {}
        for i, num in enumerate(nums):
            if target - num in nums_map:
                return [nums_map[target - num], i]
            nums_map[num] = i
        

There are no significant performance advantages.

Two Pointers

This problem cannot be solved with two pointers.

If the sum of the left and right pointers is greater than the target, the right pointer is moved to the left, and if it's smaller, the left pointer is moved to the right to adjust the value.

The time complexity of the two-pointer approach is $O(n)$, and it does not require unnecessary additional calculations, so very fast speed is expected.

However, since the input nums is not sorted, it is inappropriate to mix the indexes through sorting in problems where we need to find indexes. This is because we cannot find the original indexes.

class Solution:
    def twoSum(nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums) - 1
        while not left == right:
            if nums[left] + nums[right] < target:
                left += 1
            else nums[left] + nums[right] > target:
                right -= 1
            else:
                return left, right

Know more about Two Ponters? Click the page below ⬇️

5. Longest Palindromic Substring 🔥