General

Patterns

  • Arrays & Hashing
  • Sliding Window & 2 pointers
  • Subset level by level (BFS)
  • Modified Binary Search (O(log(n))) / O(log(m * n))
  • Top K elements (Heap)
  • Linked List

Sliding Window and Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Input: s = "zxyzxyz" #Output: 3
        # Approach Sliding Window
        char_set = set()
        l = 0
        res = 0
        for r in range(len(s)):
            while s[r] in char_set:
                char_set.remove(s[l])
                l += 1
            char_set.add(s[r])
            res = max(res, r - l + 1)
        return res

Tree

  • Recursive Solutions are often used.
  • Usually be aware of pivot = low + 1 to check do you really need to move the pivot + 1 or - 1.

Usage

Try to use range all the time, less confusion

1
2
3
4
5
prices = [1,2,3,4]
for i in range(0, len(prices)):
  print(prices[i]) # [1,2,3,4]
for i in range(0, len(prices), -1):
  print(prices[i]) # [4,3,2,1]

Playing with strings

Sort and Reverse string

  • You cannot sort a string or reverse a string using default functions (e.g. reversed(), .sort()).
  • You can use s[::-1] to reverse the string.

Checking a char is not special character, we can use this .isalnum() (built-in function). Otherwise you can leverage ascii code ord() and char().

1
2
3
4
5
6
def isPalindrome(self, s: str) -> bool:
    new_str = ""
    for c in s:
        if c.isalnum():
            new_str += c.lower()
    return new_str == new_str[::-1]

Sets

Sets cannot contain duplicate. Therefore we can simply check the length of list.

  • Useful to check duplicates

List

enumerate allows you to get the index and the item easily.

1
for i, n in enumerate(nums):

Dropping list in-place can do

1
2
3
your_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
del your_list[5:] # Removes elements starting from index 5 (inclusive) till the end. 
your_list # now its [1, 2, 3, 4, 5, 6]

Linked List

  • Most questions are swapping questions.

Stack

List can be acted as a stack, using .pop() to throw away the last value

Dict

  • your_dict.get(item, 0) the 0 marks the default value if item is not found.

loop through dict is also easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    count = {}
    freq = [[] for i in range(len(nums) + 1)]

    for n in nums:
        count[n] = 1 + count.get(n, 0)
    for n, c in count.items():
        freq[c].append(n)

    res = []
    for i in range(len(freq)-1, 0, -1):
        for n in freq[i]:
            res.append(n)
            if len(res) == k:
                return res # O(n)

defaultdict

defaultdict streamline handling of missing keys by avoiding repetitive checks or KeyError handling.

1
2
d = defaultdict(list)
d['fruits'].append('apple')  # Automatically creates a list and adds 'apple'

Moreover it can handle tuples, unlike dict()

1
2
3
4
5
6
7
8
9
10
11
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    res = defaultdict(list) # mapping charCount to list of Anagrams

    for s in strs:
        count = [0] * 26
        for c in s:
            # ord make ascii value 
            # ord("a") - ord("a") = 0
            count[ord(c) - ord("a")] += 1 
        res[tuple(count)].append(s) # List would cause errors because unhashable type
    return res.values()

English

  • Anagram: means two strings contain same number of characters. Can be solved by comparing two dicts, or even single defaultdict (using the difference properties)
  • Palindrome: means the inverted string would be the same. Can be solved by s[::-1]