Skip to content

Sde101 leetcode

Become a leetcode player in 2 hours

SDE101 teaches coding fundamentals to help solve algorithms quickly. In just a few hours, gain skills to strategize solutions and conquer LeetCode problems with confidence.

Question

Do you know python only has 36 keywords? (import keyword; print(keyword.kwlist) will print ['False', 'None', 'True', 'and', 'as', 'assert', 'async', 'await', 'break', 'class', 'continue', 'def', 'del', 'elif', 'else', 'except', 'finally', 'for', 'from', 'global', 'if', 'import', 'in', 'is', 'lambda', 'nonlocal', 'not', 'or', 'pass', 'raise', 'return', 'try', 'while', 'with', 'yield'])

Key Topics

  1. Each programming language (eg. python/java/typescript) has X keywords (eg. if/else/for)
  2. Basic algorithm (eg. bfs/dfs/binary-search)
  3. Clean coding style and IDE (Integrated Development Environment) (vscode/jerbrains)
  4. Self service blocker resolver tools (stackoverflow/chatgpt)

Leetcode SOP (Standard Operating Procedure)

  1. Interface, check input/output interface data contract and edge cases
  2. Algorithm, think about data pattern and common algorithm template
  3. Implementation, coding with helper functions
  4. Review, review index bound, exit case, typo, think about unit test for the solution

Basic Keywords

Loop

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def loop_test():
    s = "hello"
    for c in s:
        print(c)

    for i, c in enumerate(s():
        print(i, c)

    i = 0
    while i < len(s):
        print(s[i])
        i += 1

# more exmaples
seen = set()
seen.add(val)

c1 = collections.Counter(s1)
for k, v in c1.items()
c1[c] = (c1[c] or 0) - 1

"".join(nums)

for i, c in enumerate(s1)
s1[i:]

sorted(names, key=lambda s:len(s))

ret.append(cur)
ret.append(str(count))

WAYS = [(0,1),(1,0),(0,-1),(-1,0)]
ROW = len(M)
COL = len(M[0])
for r in range(ROW):
    for c in range(COL):
        for dx, dy in WAYS:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class Main {

    public static void test() {
        String s = "hello";
        for (int i = 0; i < s.length(); i++) {
            System.out.println(s.charAt(i));
        }
        for (char c : s.toCharArray()) {
            System.out.println(c);
        }
        int i = 0;
        while (i < s.length()) {
            System.out.println(s.charAt(i));
            i += 1;
        }
    }

    public static void main(String[] args) {
        test();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
fun main() {
    val s = "hello"
    for (c in s) {
        println(c)
    }

    for (i in s.indices) {
        println("${i}, ${s[i]}")
    }

    for ((i, c) in s.toCharArray().withIndex()) {
        println("${i}, ${c}")
    }

    var i = 0
    while (i < s.length) {
        println("${i}, ${s[i]}")
        i += 1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func main() {
    // string is a sequence of bytes not of a rune
    // rune type is an alias of int32

    s := "hello"
    for i, rune := range s {
        fmt.Println(i, string(rune), rune)
    }

    i := 0
    for i < len(s) {
        fmt.Println(i, string(s[i]), s[i])
        i += 1
    }

    for i:= 0; i < len(s); i+=1 {
        fmt.Println(i, string(s[i]), s[i])
    }

    // 0 h 104
    // 1 e 101
    // 2 l 108
    // 3 l 108
    // 4 o 111
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
(() => {
    const test = () => {
        const s: string = "hello";
        for (let c of s) {
            console.log(c);
        }
        for (let i = 0; i < s.length; i++) {
            console.log(s[i]);
        }
        let i: number = 0;
        while (i < s.length) {
            console.log(s[i]);
            i += 1;
        }
    }
    test();
})();

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
(() => {
    const test = () => {
        const s: string = "hello";
        for (let c of s) {
            console.log(c);
        }
        for (let i = 0; i < s.length; i++) {
            console.log(s[i]);
        }
        let i: number = 0;
        while (i < s.length) {
            console.log(s[i]);
            i += 1;
        }
    }
    test();
})();

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
fn main() {
    let s = "hello";

    for (i, char) in s.chars().enumerate() {
        println!("{} {} {}", i, char as char, char);
    }

    for i in 0..s.len() {
        println!("{} {} {}", i, s.chars().nth(i).unwrap() as char, s.as_bytes()[i]);
    }
}

Condition

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# python does not have switch keyword

def ifelse_test():
    for n in range(0,101):
        if n < 60:
            print("Fail")
        elif n < 90:
            print("Pass")
        else:
            print("Great")

    a = 10
    print(True if a % 10 == 0 else False) # True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
enum Level {
    LOW,
    HIGH,
}

public class Main {

    public static void test() {
        Level level = Level.LOW;
        switch(level) {
            case LOW:
                System.out.println("Low level message");
                break;
            case HIGH:
                System.out.println("High level message");
                break;
        }
        // "Low level message"

        int number = 3;
        switch(number) {
            case 0:
                System.out.println("Even");
                break;
            case 1:
                System.out.println("Odd");
                break;
            default:
                System.out.println("Error Number");
        }
        // "Error Number"

        for (int i = 0; i < 100; i++) {
            if (i < 60) {
                System.out.println("Fail");
            } else if (i < 90) {
                System.out.println("Pass");
            } else {
                System.out.println("Great");
            }
        }

        int a = 10;
        System.out.println(a % 10 == 0 ? true : false);
        // true
    }

    public static void main(String[] args) {
        test();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
enum class State {
    IDLE,
    RUNNING,
    FINISHED           
}  

fun cases(obj: Any): String {       
    return when (obj) {
        State.IDLE -> "It's idle"
        State.RUNNING -> "It's running"
        State.FINISHED -> "It's finished"
        1 -> "One"
        "Hello" -> "Greeting"
        is Long -> "Long"
        !is String -> "Not a string"
        else -> "Unknown"
    }   
}

fun main() {
    println(cases(State.IDLE))
    println(cases(1L))
}

// It's idle
// Long

1


1


1


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
fn main() {
    for n in 0..101 {
        if n < 60 {
            println!("Fail");
        } else if n < 90 {
            println!("Pass");
        } else {
            println!("Great");
        }
    }

    for n in 0..101 {
        match n {
            x if x < 60 => println!("Fail"),
            x if x < 90 => println!("Pass"),
            _ => println!("Great")
        }
    }
}

Algorithm Templates

Array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
"""
00888-fair-candy-swap
"""

class Solution:
    def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
        dif = (sum(A) - sum(B)) // 2
        A = set(A)
        for b in set(B):
            if dif + b in A:
                return [dif + b, b]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
object Solution {
    def fairCandySwap(aliceSizes: Array[Int], bobSizes: Array[Int]): Array[Int] = {
        val asum = aliceSizes.sum
        val bsum = bobSizes.sum
        val aset = aliceSizes.toSet
        val bset = bobSizes.toSet
        val diff = (asum - bsum) / 2
        for (b <- bset) {
            if (aset.contains(diff + b)) {
                return Array(diff+b, b)
            }
        }
        return Array()
    }
}

Permute and Combine

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 1..n choose k
        ret = []

        def dfs(cur, start, end=n, target_size=k):
            # exit
            if len(cur) == target_size:
                ret.append(cur)
                return
            if target_size - len(cur) > end - start + 1:
                return
            if start == end +1:
                return
            dfs(cur+[start], start+1) # choose
            dfs(cur, start+1) #skip

        dfs([], 1)
        return ret

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ret = []
        def dfs(cur=[], usedi=set()):
            if len(usedi) == len(nums):
                ret.append(cur)
            for i, n in enumerate(nums):
                if i not in usedi:
                    usedi.add(i)
                    helper(cur+[n], usedi)
                    usedi.remove(i)
        dfs()
        return ret

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
00034-find-first-and-last-position-of-element-in-sorted-array
"""

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums: return [-1, -1] 
        return [
            self.searchInsertLeft(nums, target),
            self.searchInsertRight(nums, target)
        ]


    def searchInsertLeft(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while r-l> 1:
            m = (r-l)//2+l
            if nums[m] == target:
                r = m
            elif nums[m] > target:
                r = m
            else:
                l = m
        if target == nums[l]:
            return l
        elif target == nums[r]:
            return r
        else:
            return -1

    def searchInsertRight(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while r-l> 1:
            m = (r-l)//2+l
            if nums[m] == target:
                l = m
            elif nums[m] > target:
                r = m
            else:
                l = m
        if target == nums[r]:
            return r
        elif target == nums[l]:
            return l
        else:
            return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
01175-prime-arrangements
"""

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        MOD = 10**9 +7
        p = len(self.getPrimes(1,n+1))
        return math.factorial(p) * math.factorial(n-p) % MOD if p > 0 else 1

    # @模板 primes in [l, r)
    def getPrimes(self, l, r):
        if l > r: return []
        l, r = max(1, l), max(1, r)
        if l < 2 and r < 2: return []
        primes = [2]
        l = (max(l, 3) // 2 * 2) + 1
        for x in range(l, r, 2):
            for p in primes:
                if x % p == 0:
                    break
                if p > x // p:
                    primes.append(x)
                    break
        return primes

Dynamic Programming

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
"""
01155-number-of-dice-rolls-with-target-sum
You have n dice, and each dice has k faces numbered from 1 to k.
"""

class Solution:
    # An @lru_cache-decorated method represents a DP state.
    # The method should not update external state variables.
    # The method should return the result for that state.
    # The returned value becomes the cached value for that DP state.
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10**9 + 7

        @lru_cache(None)
        def dfs(cur, dice):
            if dice < 0:
                return 0
            if cur > target:
                return 0
            if dice == 0:
                if target == cur:
                    return 1
                return 0

            ret = 0
            for val in range(1, k+1):
                ret += dfs(cur+val, dice-1)

            return ret % MOD

        return dfs(0, n)

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        MOd = 10**9 + 7
        dp = collections.defaultdict(int)
        dp[0] = 1
        for i in range(d):
            for j in range(0, target+1)[::-1]:
                dp[j] = sum(dp[j-k-1] for k in range(min(f, j))) % MOd
        return dp[target]

Two Pointer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
"""
00141-linked-list-cycle
"""

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
​
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow, fast = head, head
        while fast and fast.next:
          fast = fast.next.next
          slow = slow.next
          if slow == fast:
            return True
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
"""
00287-find-the-duplicate-number
"""

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        slow = 0
        while True:
            slow = nums[slow]
            fast = nums[fast]
            if slow == fast:
                return slow

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
"""
00209-minimum-size-subarray-sum
"""

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        i = 0
        j = 0
        ret = len(nums) + 1
        size = len(nums)
        while j < size:
            s -= nums[j]
            while s <= 0:
                ret = min(ret, j - i + 1)
                s += nums[i]
                i += 1
            j += 1
        return ret % (size + 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
"""
00283-move-zeroes
"""
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        i = 0
        for j in range(len(nums)):
            if nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
00912-sort-an-array
"""
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quick_sort(head, tail):
            if head >= tail: return 
            l, r = head, tail
            m = (r - l) // 2 + l
            pivot = nums[m]
            while r >= l:
                while r >= l and nums[l] < pivot: l += 1
                while r >= l and nums[r] > pivot: r -= 1
                if r >= l:
                    nums[l], nums[r] = nums[r], nums[l]
                    l += 1
                    r -= 1
            quick_sort(head, r)
            quick_sort(l, tail)

        quick_sort(0, len(nums)-1)
        return nums

Heap

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
"""
00703-kth-largest-element-in-a-stream
"""

from heapq import heapify, heappop, heappush
class KthLargest:
    # Maintain a min-heap containing the largest k elements.
    # heapify() and heappush() modify the heap in-place and return None.
    # heappop() removes and returns the smallest element.

    def __init__(self, k: int, nums: list[int]):
        self.q = nums
        self.k = k
        heapify(self.q)
        self._keep_k_items()

    def _keep_k_items(self):
        while len(self.q) > self.k:
            heappop(self.q)

    def add(self, val: int) -> int:
        heappush(self.q, val)
        self._keep_k_items()
        return self.q[0]
​
​
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

Trie

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
"""
00648-replace-words
"""

class Trie:
    def __init__(self, words):
        root = {}
        for w in words:
            node = root
            for c in list(w):
                node[c] = node.get(c, {})
                node = node[c]
            node['#'] = w
        self.root = root

    def searchTrie(node, word):
        for c in word:
            if '#' in node:
                return node['#']
            elif c in node:
                node = node[c]
            else:
                return word
        return word

class Solution:
    def replaceWords(self, dict: List[str], sentence: str) -> str:
        trie = Trie(dict)
        words = sentence.split(' ')
        return ' '.join(Trie.searchTrie(trie.root, w) for w in words)

Union Find

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
00684-redundant-connection
"""

class UF:
    def __init__(self):
        self.f = {}
​
    def find(self, x):
        self.f.setdefault(x, x)
        if x != self.f[x]:
            self.f[x] = self.find(self.f[x])
        return self.f[x]
​
    def union(self, x, y):
        par_x, par_y = self.find(x), self.find(y)
        if par_x != par_y:
            self.f[par_x] = par_y

    def isUnion(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def findRedundantConnection(self, edges):
        uf = UF()

        ret = None
        for u, v in edges:
            if uf.isUnion(u, v): 
                ret = [u, v]
            else:
                uf.union(u, v)
        return ret

Pyhton Hack

1
2
3
4
5
6
7
8
9
"""
00299-bulls-and-cows
"""

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        A = sum(a==b for a,b in zip(secret, guess))
        B = sum((Counter(secret) & Counter(guess)).values())
        return "{}A{}B".format(A, B - A)