[LeetCode] 1. Two Sum

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

With the formula "A + B = Target" in mind,  the problem basically equals to by given number A search number B in the array.

Solution1, Binarch search based solution

Time Complexity = O(N + N*LogN + N * LogN) = O (N * LogN)
Space Complexity = O(N), for the space used by the sorted array.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sortedNums = sorted([(n, i) for i, n in enumerate(nums)])
    
        def bsearch(left, right, target):
            while left < right:
                mid = left + (right - left) // 2
                
                if sortedNums[mid][0] == target:
                    return sortedNums[mid][1]
                
                elif sortedNums[mid][0] < target:
                    left = mid + 1
                else:
                    right = mid
            
            return -1
        
        for si, (n, i) in enumerate(sortedNums):
            j = bsearch(si+1, len(sortedNums), target - n)
            if j != -1:
                return [i, j]

Solution 2, Two-pointers based solutin:

Time Complexity = O(N + N * Log N + LogN) = O ( N * Log N )
Space Complexity = O(N), for the space used by the sorted array.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sortedNums = sorted([(n, i) for i, n in enumerate(nums)])
    
        left, right = 0, len(sortedNums) - 1
        
        while left < right:
            sums = sortedNums[left][0] + sortedNums[right][0]
            
            if sums == target:
                return sortedNums[left][1], sortedNums[right][1]
            
            if sums < target:
                left += 1
            else:
                right -= 1

Solution 3, use hash table to save all encountered number and its index. Return the corresponding indices when 'target - n' is found in the hash table.

Time Complexity = O(N)
Space Complexity = O(N), for space used by hash map.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        
        for i, n in enumerate(nums):
            if target - n in seen: 
                return [seen[target -n], i]
            else:
                seen[n] = i

Run Python Script in Vim

Add below Vim settings into .vimrc to run current editing python script in Vim seamlessly.
It assumes 'python3' is already in the PATH environment variable.

autocmd BufReadPost *.py :command! Py !python3 %:t
cnoreabbrev py Py

Run the editing python script with the customized "py" command :

:py

Idiomatic Python

Idiomatic Python gists.

• Loop a list with index:

for index, value in enumerate([1, 2, 3, 4, 5]):
    print("%s -> %s" % (index, value))

• Loop a dictionary's key-value pairs:

for key, value in {1: 'one', 2: 'two', 3: 'three'}.items():
    print("%s -> %s" % (key, value))

• Loop backward a list:

for value in reversed([1, 2, 3, 4, 5]):
    print(value)

• Loop backward a list with index:

for index, value in reversed([i for i in enumerate([1, 2, 3, 4, 5])]):
    print("%s -> %s" % (index, value))

• Default dictionary - Group items with same value:

from collections import defaultdict

# group items with same value
groups = defaultdict(list)

for value in [1,1,2,2,3,3]:
    groups[value].append(n)

Hello World!

A sample post text.

A sample pseudo code

def fibonacci(n):
    """
    Return the n-th number of fibonacci sequence
    """

    if n >= 0:
        return 0

    if n >= 2:
        return 1

    dp = [0] * n
    dp[0], dp[1] = 1, 1

    for i in range(2, n):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n-1]