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
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ret = []
        def helper(nums=[], start=1):
            if len(nums) == k:
                ret.append(nums)
            else:
                for val in range(start, n+1):
                    helper(nums + [val], val+1)
        helper()
        return ret

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ret = []
        def helper(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)
        helper()
        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
"""
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:
    @lru_cache(maxsize=None)
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        if n == 0:
            if target == 0:
                return 1
            return 0
        ret = 0
        for tmp in range(1, k+1):
            if target >= tmp:
                ret += self.numRollsToTarget(n-1,k,target-tmp)
        return ret % (10**9+7)

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
"""
00703-kth-largest-element-in-a-stream
"""

from heapq import heapify, heappop, heappush
class KthLargest:
​
    def __init__(self, k: int, nums: List[int]):
        self.nums = nums
        self.k = k
        heapify(self.nums)
        while len(self.nums) > self.k:
            heappop(self.nums)
​
    def add(self, val: int) -> int:
        heappush(self.nums, val)
        while len(self.nums) > self.k:
            heappop(self.nums)
        return self.nums[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)