LeetCode Core Problems: Python and Go Solutions

LeetCode Core Problems: Python and Go Solutions

Each problem includes a clear statement, tracked variables, a specific flowchart, complexity, example, and both Python and Go solutions.

PDF Version

Table of Contents

• 1. Arrays / Hashing
• 2. Sliding Window / Strings
• 3. Binary Search
• 4. Trees / Graphs
• 5. Linked List
• 6. Intervals / Greedy
• 7. Dynamic Programming
• 8. Backtracking

1. Arrays / Hashing

1) Two Sum

Problem Statement

Given integer array nums and integer target, return indices i and j where nums i plus nums j equals target and i is not j.

Variables To Track

i x need seen

Solution Flow

flowchart TD
    A[Input for problem 1] --> B[Initialize variables i x need seen]
    B --> C[need equals target minus x then check seen then store x index]
    C --> D{i less than len nums}
    D -- Yes --> C
    D -- No --> E[return pair of indices]

Complexity

Time O n. Space O n.

Example

nums 2 7 11 15 and target 9 returns 0 1

Python

from typing import List

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

Go

func twoSum(nums []int, target int) []int {
    seen := map[int]int{}
    for i, x := range nums {
        y := target - x
        if j, ok := seen[y]; ok {
            return []int{j, i}
        }
        seen[x] = i
    }
    return []int{}
}

49) Group Anagrams

Problem Statement

Given list of strings, group anagrams together and return all groups.

Variables To Track

s key groups

Solution Flow

flowchart TD
    A[Input for problem 49] --> B[Initialize variables s key groups]
    B --> C[build char count key then append s into groups key]
    C --> D{more strings}
    D -- Yes --> C
    D -- No --> E[return list of group values]

Complexity

Time O n times k. Space O n times k.

Example

eat tea tan ate nat bat returns groups eat tea ate and tan nat and bat

Python

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for s in strs:
            key = [0] * 26
            for c in s:
                key[ord(c) - ord("a")] += 1
            groups[tuple(key)].append(s)
        return list(groups.values())

Go

func groupAnagrams(strs []string) [][]string {
    m := map[[26]int][]string{}
    for _, s := range strs {
        var key [26]int
        for _, ch := range s {
            key[ch-'a']++
        }
        m[key] = append(m[key], s)
    }
    out := make([][]string, 0, len(m))
    for _, v := range m {
        out = append(out, v)
    }
    return out
}

238) Product of Array Except Self

Problem Statement

Given nums, return output where output i is product of all nums except nums i without division.

Variables To Track

i out prefix suffix

Solution Flow

flowchart TD
    A[Input for problem 238] --> B[Initialize variables i out prefix suffix]
    B --> C[left pass writes prefix then right pass multiplies suffix]
    C --> D{passes remain}
    D -- Yes --> C
    D -- No --> E[return out array]

Complexity

Time O n. Space O 1 extra excluding output.

Example

1 2 3 4 returns 24 12 8 6

Python

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        out = [1] * n
        p = 1
        for i in range(n):
            out[i] = p
            p *= nums[i]
        s = 1
        for i in range(n - 1, -1, -1):
            out[i] *= s
            s *= nums[i]
        return out

Go

func productExceptSelf(nums []int) []int {
    n := len(nums)
    out := make([]int, n)
    p := 1
    for i := 0; i < n; i++ {
        out[i] = p
        p *= nums[i]
    }
    s := 1
    for i := n - 1; i >= 0; i-- {
        out[i] *= s
        s *= nums[i]
    }
    return out
}

560) Subarray Sum Equals K

Problem Statement

Given nums and k, return count of contiguous subarrays with sum exactly k.

Variables To Track

cur cnt ans

Solution Flow

flowchart TD
    A[Input for problem 560] --> B[Initialize variables cur cnt ans]
    B --> C[cur plus equals x then ans plus equals cnt at cur minus k then increment cnt cur]
    C --> D{more elements}
    D -- Yes --> C
    D -- No --> E[return ans]

Complexity

Time O n. Space O n.

Example

1 1 1 and k 2 returns 2

Python

from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        cnt[0] = 1
        cur = 0
        ans = 0
        for x in nums:
            cur += x
            ans += cnt[cur - k]
            cnt[cur] += 1
        return ans

Go

func subarraySum(nums []int, k int) int {
    cnt := map[int]int{0: 1}
    cur, ans := 0, 0
    for _, x := range nums {
        cur += x
        ans += cnt[cur-k]
        cnt[cur]++
    }
    return ans
}

347) Top K Frequent Elements

Problem Statement

Given nums and k, return the k most frequent elements.

Variables To Track

freq buckets out

Solution Flow

flowchart TD
    A[Input for problem 347] --> B[Initialize variables freq buckets out]
    B --> C[count freq then place values by count then scan high to low]
    C --> D{buckets left to scan}
    D -- Yes --> C
    D -- No --> E[return first k in out]

Complexity

Time O n. Space O n.

Example

1 1 1 2 2 3 with k 2 returns 1 and 2

Python

from collections import Counter
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, c in freq.items():
            buckets[c].append(num)
        out = []
        for c in range(len(buckets) - 1, 0, -1):
            for num in buckets[c]:
                out.append(num)
                if len(out) == k:
                    return out
        return out

Go

func topKFrequent(nums []int, k int) []int {
    freq := map[int]int{}
    for _, x := range nums {
        freq[x]++
    }
    buckets := make([][]int, len(nums)+1)
    for x, c := range freq {
        buckets[c] = append(buckets[c], x)
    }
    out := []int{}
    for c := len(buckets) - 1; c > 0 && len(out) < k; c-- {
        out = append(out, buckets[c]...)
    }
    return out[:k]
}

2. Sliding Window / Strings

3) Longest Substring Without Repeating Characters

Problem Statement

Given string s, return length of longest substring with no repeating characters.

Variables To Track

l r last best

Solution Flow

flowchart TD
    A[Input for problem 3] --> B[Initialize variables l r last best]
    B --> C[if char seen in window move l then update last and best]
    C --> D{r less than len s}
    D -- Yes --> C
    D -- No --> E[return best length]

Complexity

Time O n. Space O charset.

Example

abcabcbb returns 3

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}
        l = 0
        best = 0
        for r, ch in enumerate(s):
            if ch in last and last[ch] >= l:
                l = last[ch] + 1
            last[ch] = r
            best = max(best, r - l + 1)
        return best

Go

func lengthOfLongestSubstring(s string) int {
    last := map[byte]int{}
    l, best := 0, 0
    for r := 0; r < len(s); r++ {
        ch := s[r]
        if i, ok := last[ch]; ok && i >= l {
            l = i + 1
        }
        last[ch] = r
        if r-l+1 > best {
            best = r - l + 1
        }
    }
    return best
}

76) Minimum Window Substring

Problem Statement

Given s and t, return minimum window in s containing all chars of t with multiplicity.

Variables To Track

l r need have formed best

Solution Flow

flowchart TD
    A[Input for problem 76] --> B[Initialize variables l r need have formed best]
    B --> C[expand right then while formed equals required shrink left and update best]
    C --> D{r less than len s}
    D -- Yes --> C
    D -- No --> E[return best window or empty]

Complexity

Time O n. Space O charset.

Example

adobecodebanc and abc returns banc

Python

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        have = {}
        required = len(need)
        formed = 0
        l = 0
        ans = (float("inf"), 0, 0)
        for r, ch in enumerate(s):
            have[ch] = have.get(ch, 0) + 1
            if ch in need and have[ch] == need[ch]:
                formed += 1
            while formed == required:
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)
                c = s[l]
                have[c] -= 1
                if c in need and have[c] < need[c]:
                    formed -= 1
                l += 1
        return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]

Go

func minWindow(s string, t string) string {
    need := map[byte]int{}
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }
    have := map[byte]int{}
    required := len(need)
    formed := 0
    l := 0
    bestLen, bestL := 1<<30, 0

    for r := 0; r < len(s); r++ {
        ch := s[r]
        have[ch]++
        if v, ok := need[ch]; ok && have[ch] == v {
            formed++
        }
        for formed == required {
            if r-l+1 < bestLen {
                bestLen = r - l + 1
                bestL = l
            }
            c := s[l]
            have[c]--
            if v, ok := need[c]; ok && have[c] < v {
                formed--
            }
            l++
        }
    }
    if bestLen == 1<<30 {
        return ""
    }
    return s[bestL : bestL+bestLen]
}

424) Longest Repeating Character Replacement

Problem Statement

Given s and k, return longest window that can become one repeated char after at most k replacements.

Variables To Track

l r cnt maxf best

Solution Flow

flowchart TD
    A[Input for problem 424] --> B[Initialize variables l r cnt maxf best]
    B --> C[expand right update maxf then shrink while window minus maxf greater than k]
    C --> D{r less than len s}
    D -- Yes --> C
    D -- No --> E[return best]

Complexity

Time O n. Space O charset.

Example

aababba with k 1 returns 4

Python

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        cnt = {}
        l = 0
        maxf = 0
        best = 0
        for r, ch in enumerate(s):
            cnt[ch] = cnt.get(ch, 0) + 1
            maxf = max(maxf, cnt[ch])
            while (r - l + 1) - maxf > k:
                cnt[s[l]] -= 1
                l += 1
            best = max(best, r - l + 1)
        return best

Go

func characterReplacement(s string, k int) int {
    cnt := [26]int{}
    l, maxf, best := 0, 0, 0
    for r := 0; r < len(s); r++ {
        idx := int(s[r] - 'A')
        cnt[idx]++
        if cnt[idx] > maxf {
            maxf = cnt[idx]
        }
        for (r-l+1)-maxf > k {
            cnt[int(s[l]-'A')]--
            l++
        }
        if r-l+1 > best {
            best = r - l + 1
        }
    }
    return best
}

567) Permutation in String

Problem Statement

Given s1 and s2, return true if permutation of s1 appears as contiguous substring in s2.

Variables To Track

need win i m

Solution Flow

flowchart TD
    A[Input for problem 567] --> B[Initialize variables need win i m]
    B --> C[slide fixed window of size m updating win counts]
    C --> D{i less than len s2}
    D -- Yes --> C
    D -- No --> E[return true on match else false]

Complexity

Time O n. Space O charset.

Example

ab in eidbaooo returns true

Python

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        need = [0] * 26
        win = [0] * 26
        for c in s1:
            need[ord(c) - 97] += 1
        m = len(s1)
        for i, c in enumerate(s2):
            win[ord(c) - 97] += 1
            if i >= m:
                win[ord(s2[i - m]) - 97] -= 1
            if win == need:
                return True
        return False

Go

func checkInclusion(s1 string, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }
    var need, win [26]int
    for i := 0; i < len(s1); i++ {
        need[s1[i]-'a']++
    }
    m := len(s1)
    for i := 0; i < len(s2); i++ {
        win[s2[i]-'a']++
        if i >= m {
            win[s2[i-m]-'a']--
        }
        if win == need {
            return true
        }
    }
    return false
}

125) Valid Palindrome

Problem Statement

Given string s, return true if normalized alnum lowercase string is palindrome.

Variables To Track

l r

Solution Flow

flowchart TD
    A[Input for problem 125] --> B[Initialize variables l r]
    B --> C[skip non alnum then compare lowercase chars then move pointers]
    C --> D{l less than r}
    D -- Yes --> C
    D -- No --> E[return false on mismatch else true]

Complexity

Time O n. Space O 1.

Example

a man a plan a canal panama returns true

Python

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

Go

func isPalindrome(s string) bool {
    isAlnum := func(c byte) bool {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')
    }
    toLower := func(c byte) byte {
        if c >= 'A' && c <= 'Z' {
            return c - 'A' + 'a'
        }
        return c
    }
    l, r := 0, len(s)-1
    for l < r {
        for l < r && !isAlnum(s[l]) {
            l++
        }
        for l < r && !isAlnum(s[r]) {
            r--
        }
        if toLower(s[l]) != toLower(s[r]) {
            return false
        }
        l++
        r--
    }
    return true
}

3. Binary Search

33) Search in Rotated Sorted Array

Problem Statement

Given rotated sorted array nums and target, return target index or minus one.

Variables To Track

l r mid

Solution Flow

flowchart TD
    A[Input for problem 33] --> B[Initialize variables l r mid]
    B --> C[choose sorted half then keep side where target can exist]
    C --> D{l less or equal r}
    D -- Yes --> C
    D -- No --> E[return index or minus one]

Complexity

Time O log n. Space O 1.

Example

4 5 6 7 0 1 2 target 0 returns 4

Python

from typing import List

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

Go

func search(nums []int, target int) int {
    l, r := 0, len(nums)-1
    for l <= r {
        m := (l + r) / 2
        if nums[m] == target {
            return m
        }
        if nums[l] <= nums[m] {
            if nums[l] <= target && target < nums[m] {
                r = m - 1
            } else {
                l = m + 1
            }
        } else {
            if nums[m] < target && target <= nums[r] {
                l = m + 1
            } else {
                r = m - 1
            }
        }
    }
    return -1
}

153) Find Minimum in Rotated Sorted Array

Problem Statement

Given rotated sorted array with distinct values, return minimum value.

Variables To Track

l r mid

Solution Flow

flowchart TD
    A[Input for problem 153] --> B[Initialize variables l r mid]
    B --> C[if nums mid greater than nums r move l else move r]
    C --> D{l less than r}
    D -- Yes --> C
    D -- No --> E[return nums l]

Complexity

Time O log n. Space O 1.

Example

3 4 5 1 2 returns 1

Python

from typing import List

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            m = (l + r) // 2
            if nums[m] > nums[r]:
                l = m + 1
            else:
                r = m
        return nums[l]

Go

func findMin(nums []int) int {
    l, r := 0, len(nums)-1
    for l < r {
        m := (l + r) / 2
        if nums[m] > nums[r] {
            l = m + 1
        } else {
            r = m
        }
    }
    return nums[l]
}

875) Koko Eating Bananas

Problem Statement

Given banana piles and h hours, return minimum integer speed to finish in h.

Variables To Track

l r mid hours

Solution Flow

flowchart TD
    A[Input for problem 875] --> B[Initialize variables l r mid hours]
    B --> C[compute hours at mid then move bounds by feasibility]
    C --> D{l less than r}
    D -- Yes --> C
    D -- No --> E[return l speed]

Complexity

Time O n log m where m is max pile.

Example

3 6 7 11 with h 8 returns 4

Python

import math
from typing import List

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        while l < r:
            m = (l + r) // 2
            hours = sum(math.ceil(p / m) for p in piles)
            if hours <= h:
                r = m
            else:
                l = m + 1
        return l

Go

func minEatingSpeed(piles []int, h int) int {
    l, r := 1, 0
    for _, p := range piles {
        if p > r {
            r = p
        }
    }
    can := func(k int) bool {
        hours := 0
        for _, p := range piles {
            hours += (p + k - 1) / k
        }
        return hours <= h
    }
    for l < r {
        m := (l + r) / 2
        if can(m) {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

981) Time Based Key-Value Store

Problem Statement

Design time map with set key value timestamp and get key timestamp for latest value at or before timestamp.

Variables To Track

store arr l r mid

Solution Flow

flowchart TD
    A[Input for problem 981] --> B[Initialize variables store arr l r mid]
    B --> C[for get perform rightmost less or equal search]
    C --> D{binary search range valid}
    D -- Yes --> C
    D -- No --> E[return value or empty]

Complexity

Set O 1. Get O log n per key.

Example

set foo bar at 1 then get foo at 3 returns bar

Python

from collections import defaultdict
from bisect import bisect_right
from typing import List, Tuple

class TimeMap:
    def __init__(self):
        self.m = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.m[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        arr: List[Tuple[int, str]] = self.m.get(key, [])
        i = bisect_right(arr, (timestamp, chr(127))) - 1
        return arr[i][1] if i >= 0 else ""

Go

type pair struct {
    ts  int
    val string
}

type TimeMap struct {
    m map[string][]pair
}

func Constructor() TimeMap {
    return TimeMap{m: map[string][]pair{}}
}

func (tm *TimeMap) Set(key string, value string, timestamp int) {
    tm.m[key] = append(tm.m[key], pair{ts: timestamp, val: value})
}

func (tm *TimeMap) Get(key string, timestamp int) string {
    arr := tm.m[key]
    l, r := 0, len(arr)-1
    ans := -1
    for l <= r {
        mid := (l + r) / 2
        if arr[mid].ts <= timestamp {
            ans = mid
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    if ans == -1 {
        return ""
    }
    return arr[ans].val
}

4. Trees / Graphs

102) Binary Tree Level Order Traversal

Problem Statement

Given binary tree root, return values grouped by level from top to bottom.

Variables To Track

queue level

Solution Flow

flowchart TD
    A[Input for problem 102] --> B[Initialize variables queue level]
    B --> C[process current queue size and push children]
    C --> D{queue not empty}
    D -- Yes --> C
    D -- No --> E[return level list]

Complexity

Time O n. Space O width.

Example

3 9 20 null null 15 7 returns 3 then 9 20 then 15 7

Python

from collections import deque
from typing import List, Optional

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        q = deque([root])
        out = []
        while q:
            level = []
            for _ in range(len(q)):
                n = q.popleft()
                level.append(n.val)
                if n.left:
                    q.append(n.left)
                if n.right:
                    q.append(n.right)
            out.append(level)
        return out

Go

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    q := []*TreeNode{root}
    out := [][]int{}
    for len(q) > 0 {
        sz := len(q)
        level := make([]int, 0, sz)
        for i := 0; i < sz; i++ {
            n := q[0]
            q = q[1:]
            level = append(level, n.Val)
            if n.Left != nil {
                q = append(q, n.Left)
            }
            if n.Right != nil {
                q = append(q, n.Right)
            }
        }
        out = append(out, level)
    }
    return out
}

199) Binary Tree Right Side View

Problem Statement

Given binary tree root, return right side view values.

Variables To Track

queue level last

Solution Flow

flowchart TD
    A[Input for problem 199] --> B[Initialize variables queue level last]
    B --> C[process each level and keep last node value]
    C --> D{queue not empty}
    D -- Yes --> C
    D -- No --> E[return right view list]

Complexity

Time O n. Space O width.

Example

1 2 3 null 5 null 4 returns 1 3 4

Python

from collections import deque
from typing import List, Optional

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        q = deque([root])
        out = []
        while q:
            sz = len(q)
            for i in range(sz):
                n = q.popleft()
                if n.left:
                    q.append(n.left)
                if n.right:
                    q.append(n.right)
                if i == sz - 1:
                    out.append(n.val)
        return out

Go

func rightSideView(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    q := []*TreeNode{root}
    out := []int{}
    for len(q) > 0 {
        sz := len(q)
        for i := 0; i < sz; i++ {
            n := q[0]
            q = q[1:]
            if n.Left != nil {
                q = append(q, n.Left)
            }
            if n.Right != nil {
                q = append(q, n.Right)
            }
            if i == sz-1 {
                out = append(out, n.Val)
            }
        }
    }
    return out
}

236) Lowest Common Ancestor of a Binary Tree

Problem Statement

Given binary tree root and nodes p q, return lowest common ancestor.

Variables To Track

node left right

Solution Flow

flowchart TD
    A[Input for problem 236] --> B[Initialize variables node left right]
    B --> C[return node on match then combine left right results]
    C --> D{recursive traversal}
    D -- Yes --> C
    D -- No --> E[return lca node]

Complexity

Time O n. Space O height.

Example

p 5 q 1 in sample tree returns 3

Python

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left or right

Go

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}

200) Number of Islands

Problem Statement

Given grid of ones and zeros, return number of islands.

Variables To Track

r c grid

Solution Flow

flowchart TD
    A[Input for problem 200] --> B[Initialize variables r c grid]
    B --> C[on land increment count then flood fill connected land]
    C --> D{cells remain}
    D -- Yes --> C
    D -- No --> E[return island count]

Complexity

Time O m n. Space O m n worst case.

Example

sample grid with one big land mass returns 1

Python

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(r: int, c: int) -> None:
            if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] != "1":
                return
            grid[r][c] = "0"
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    ans += 1
                    dfs(i, j)
        return ans

Go

func numIslands(grid [][]byte) int {
    m, n := len(grid), len(grid[0])
    var dfs func(int, int)
    dfs = func(r, c int) {
        if r < 0 || c < 0 || r >= m || c >= n || grid[r][c] != '1' {
            return
        }
        grid[r][c] = '0'
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    }
    ans := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '1' {
                ans++
                dfs(i, j)
            }
        }
    }
    return ans
}

133) Clone Graph

Problem Statement

Given node of connected undirected graph, return deep clone.

Variables To Track

oldToNew

Solution Flow

flowchart TD
    A[Input for problem 133] --> B[Initialize variables oldToNew]
    B --> C[clone node once and recursively clone neighbors]
    C --> D{neighbors remain}
    D -- Yes --> C
    D -- No --> E[return cloned start node]

Complexity

Time O v plus e. Space O v.

Example

square graph clone preserves structure

Python

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        mp = {}
        def dfs(n):
            if n in mp:
                return mp[n]
            copy = Node(n.val)
            mp[n] = copy
            for nei in n.neighbors:
                copy.neighbors.append(dfs(nei))
            return copy
        return dfs(node)

Go

func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }
    mp := map[*Node]*Node{}
    var dfs func(*Node) *Node
    dfs = func(n *Node) *Node {
        if v, ok := mp[n]; ok {
            return v
        }
        copy := &Node{Val: n.Val}
        mp[n] = copy
        for _, nei := range n.Neighbors {
            copy.Neighbors = append(copy.Neighbors, dfs(nei))
        }
        return copy
    }
    return dfs(node)
}

5. Linked List

206) Reverse Linked List

Problem Statement

Given linked list head, reverse the list and return new head.

Variables To Track

prev cur nxt

Solution Flow

flowchart TD
    A[Input for problem 206] --> B[Initialize variables prev cur nxt]
    B --> C[save nxt then point cur next to prev then advance]
    C --> D{cur not nil}
    D -- Yes --> C
    D -- No --> E[return prev]

Complexity

Time O n. Space O 1.

Example

1 2 3 returns 3 2 1

Python

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev

Go

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    cur := head
    for cur != nil {
        nxt := cur.Next
        cur.Next = prev
        prev = cur
        cur = nxt
    }
    return prev
}

21) Merge Two Sorted Lists

Problem Statement

Given two sorted linked lists, merge into one sorted list.

Variables To Track

l1 l2 tail

Solution Flow

flowchart TD
    A[Input for problem 21] --> B[Initialize variables l1 l2 tail]
    B --> C[attach smaller node and advance that list]
    C --> D{both lists non empty}
    D -- Yes --> C
    D -- No --> E[attach remainder and return]

Complexity

Time O n plus m. Space O 1.

Example

1 2 4 and 1 3 4 returns 1 1 2 3 4 4

Python

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = ListNode(0)
        cur = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 or list2
        return dummy.next

Go

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            cur.Next = list1
            list1 = list1.Next
        } else {
            cur.Next = list2
            list2 = list2.Next
        }
        cur = cur.Next
    }
    if list1 != nil {
        cur.Next = list1
    } else {
        cur.Next = list2
    }
    return dummy.Next
}

143) Reorder List

Problem Statement

Given linked list, reorder as first last second second last pattern.

Variables To Track

slow fast second

Solution Flow

flowchart TD
    A[Input for problem 143] --> B[Initialize variables slow fast second]
    B --> C[find mid reverse second half then weave alternating]
    C --> D{weaving nodes remain}
    D -- Yes --> C
    D -- No --> E[return modified list]

Complexity

Time O n. Space O 1.

Example

1 2 3 4 becomes 1 4 2 3

Python

class Solution:
    def reorderList(self, head: ListNode) -> None:
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        second = slow.next
        slow.next = None
        prev = None
        while second:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        first, second = head, prev
        while second:
            t1, t2 = first.next, second.next
            first.next = second
            second.next = t1
            first, second = t1, t2

Go

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    second := slow.Next
    slow.Next = nil

    var prev *ListNode
    for second != nil {
        nxt := second.Next
        second.Next = prev
        prev = second
        second = nxt
    }
    first, second := head, prev
    for second != nil {
        t1, t2 := first.Next, second.Next
        first.Next = second
        second.Next = t1
        first = t1
        second = t2
    }
}

141) Linked List Cycle

Problem Statement

Given linked list head, detect cycle and return true or false.

Variables To Track

slow fast

Solution Flow

flowchart TD
    A[Input for problem 141] --> B[Initialize variables slow fast]
    B --> C[move slow one step and fast two steps]
    C --> D{fast and fast next exist}
    D -- Yes --> C
    D -- No --> E[return true on meet else false]

Complexity

Time O n. Space O 1.

Example

3 2 0 minus 4 with cycle returns true

Python

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

Go

func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

2) Add Two Numbers

Problem Statement

Given two reversed linked list numbers, return reversed linked list sum.

Variables To Track

l1 l2 carry

Solution Flow

flowchart TD
    A[Input for problem 2] --> B[Initialize variables l1 l2 carry]
    B --> C[sum digits and carry then append ones digit]
    C --> D{nodes remain or carry non zero}
    D -- Yes --> C
    D -- No --> E[return dummy next]

Complexity

Time O max n m. Space O 1 extra.

Example

2 4 3 plus 5 6 4 returns 7 0 8

Python

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        cur = dummy
        carry = 0
        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            s = v1 + v2 + carry
            carry = s // 10
            cur.next = ListNode(s % 10)
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next

Go

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    carry := 0
    for l1 != nil || l2 != nil || carry > 0 {
        v1, v2 := 0, 0
        if l1 != nil {
            v1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            v2 = l2.Val
            l2 = l2.Next
        }
        s := v1 + v2 + carry
        carry = s / 10
        cur.Next = &ListNode{Val: s % 10}
        cur = cur.Next
    }
    return dummy.Next
}

6. Intervals / Greedy

56) Merge Intervals

Problem Statement

Given intervals, merge overlaps and return merged list.

Variables To Track

intervals out

Solution Flow

flowchart TD
    A[Input for problem 56] --> B[Initialize variables intervals out]
    B --> C[sort by start then merge with last out interval]
    C --> D{more intervals}
    D -- Yes --> C
    D -- No --> E[return out]

Complexity

Time O n log n. Space O n output.

Example

1 3 and 2 6 merge into 1 6

Python

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        out = []
        for s, e in intervals:
            if not out or s > out[-1][1]:
                out.append([s, e])
            else:
                out[-1][1] = max(out[-1][1], e)
        return out

Go

import "sort"

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
    out := [][]int{}
    for _, in := range intervals {
        if len(out) == 0 || in[0] > out[len(out)-1][1] {
            out = append(out, []int{in[0], in[1]})
        } else if in[1] > out[len(out)-1][1] {
            out[len(out)-1][1] = in[1]
        }
    }
    return out
}

57) Insert Interval

Problem Statement

Given sorted non-overlap intervals and new interval, insert and merge.

Variables To Track

intervals newInterval out

Solution Flow

flowchart TD
    A[Input for problem 57] --> B[Initialize variables intervals newInterval out]
    B --> C[append left non overlap then merge overlaps then append right]
    C --> D{intervals remain}
    D -- Yes --> C
    D -- No --> E[return out]

Complexity

Time O n. Space O n output.

Example

1 3 and 6 9 with new 2 5 returns 1 5 and 6 9

Python

from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        out = []
        i, n = 0, len(intervals)
        while i < n and intervals[i][1] < newInterval[0]:
            out.append(intervals[i])
            i += 1
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        out.append(newInterval)
        out.extend(intervals[i:])
        return out

Go

func insert(intervals [][]int, newInterval []int) [][]int {
    out := [][]int{}
    i, n := 0, len(intervals)
    for i < n && intervals[i][1] < newInterval[0] {
        out = append(out, intervals[i])
        i++
    }
    for i < n && intervals[i][0] <= newInterval[1] {
        if intervals[i][0] < newInterval[0] {
            newInterval[0] = intervals[i][0]
        }
        if intervals[i][1] > newInterval[1] {
            newInterval[1] = intervals[i][1]
        }
        i++
    }
    out = append(out, newInterval)
    out = append(out, intervals[i:]...)
    return out
}

435) Non-overlapping Intervals

Problem Statement

Given intervals, return minimum removals for non-overlap.

Variables To Track

lastEnd removed

Solution Flow

flowchart TD
    A[Input for problem 435] --> B[Initialize variables lastEnd removed]
    B --> C[sort by end and keep interval if start at least lastEnd else remove]
    C --> D{more intervals}
    D -- Yes --> C
    D -- No --> E[return removed]

Complexity

Time O n log n. Space O 1 extra.

Example

1 2 2 3 3 4 1 3 returns 1

Python

from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        end = float("-inf")
        keep = 0
        for s, e in intervals:
            if s >= end:
                keep += 1
                end = e
        return len(intervals) - keep

Go

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
    end := -1 << 31
    keep := 0
    for _, in := range intervals {
        if in[0] >= end {
            keep++
            end = in[1]
        }
    }
    return len(intervals) - keep
}

452) Minimum Number of Arrows to Burst Balloons

Problem Statement

Given balloon intervals, return minimum arrows to burst all.

Variables To Track

end arrows

Solution Flow

flowchart TD
    A[Input for problem 452] --> B[Initialize variables end arrows]
    B --> C[sort by end and shoot new arrow when start greater than end]
    C --> D{more balloons}
    D -- Yes --> C
    D -- No --> E[return arrows]

Complexity

Time O n log n. Space O 1 extra.

Example

10 16 2 8 1 6 7 12 returns 2

Python

from typing import List

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[1])
        arrows = 0
        end = float("-inf")
        for s, e in points:
            if s > end:
                arrows += 1
                end = e
        return arrows

Go

import "sort"

func findMinArrowShots(points [][]int) int {
    sort.Slice(points, func(i, j int) bool { return points[i][1] < points[j][1] })
    arrows := 0
    end := -(1 << 62)
    for _, p := range points {
        if p[0] > end {
            arrows++
            end = p[1]
        }
    }
    return arrows
}

7. Dynamic Programming

70) Climbing Stairs

Problem Statement

Given n, return count of ways to climb to top with one or two step moves.

Variables To Track

a b

Solution Flow

flowchart TD
    A[Input for problem 70] --> B[Initialize variables a b]
    B --> C[iterate fibonacci transition]
    C --> D{remaining steps}
    D -- Yes --> C
    D -- No --> E[return b]

Complexity

Time O n. Space O 1.

Example

n 5 returns 8

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a

Go

func climbStairs(n int) int {
    a, b := 1, 1
    for i := 0; i < n; i++ {
        a, b = b, a+b
    }
    return a
}

198) House Robber

Problem Statement

Given house values, return max rob amount without adjacent houses.

Variables To Track

rob skip

Solution Flow

flowchart TD
    A[Input for problem 198] --> B[Initialize variables rob skip]
    B --> C[newRob equals skip plus x and newSkip equals max rob skip]
    C --> D{houses remain}
    D -- Yes --> C
    D -- No --> E[return max rob skip]

Complexity

Time O n. Space O 1.

Example

2 7 9 3 1 returns 12

Python

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2, prev1 = 0, 0
        for x in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + x)
        return prev1

Go

func rob(nums []int) int {
    prev2, prev1 := 0, 0
    for _, x := range nums {
        cur := prev1
        if prev2+x > cur {
            cur = prev2 + x
        }
        prev2, prev1 = prev1, cur
    }
    return prev1
}

322) Coin Change

Problem Statement

Given coins and amount, return minimum coins needed or minus one.

Variables To Track

dp a coin

Solution Flow

flowchart TD
    A[Input for problem 322] --> B[Initialize variables dp a coin]
    B --> C[for each amount relax with each coin]
    C --> D{amount states remain}
    D -- Yes --> C
    D -- No --> E[return dp amount or minus one]

Complexity

Time O amount times coins. Space O amount.

Example

coins 1 2 5 amount 11 returns 3

Python

from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        INF = amount + 1
        dp = [INF] * (amount + 1)
        dp[0] = 0
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a:
                    dp[a] = min(dp[a], dp[a - c] + 1)
        return -1 if dp[amount] == INF else dp[amount]

Go

func coinChange(coins []int, amount int) int {
    inf := amount + 1
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = inf
        for _, c := range coins {
            if c <= i && dp[i-c]+1 < dp[i] {
                dp[i] = dp[i-c] + 1
            }
        }
    }
    if dp[amount] == inf {
        return -1
    }
    return dp[amount]
}

139) Word Break

Problem Statement

Given string and dictionary, return true if string can be segmented into words.

Variables To Track

dp i j

Solution Flow

flowchart TD
    A[Input for problem 139] --> B[Initialize variables dp i j]
    B --> C[set dp i true when dp j true and slice j i in dict]
    C --> D{positions remain}
    D -- Yes --> C
    D -- No --> E[return dp n]

Complexity

Time O n squared typical. Space O n.

Example

leetcode with leet code returns true

Python

from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break
        return dp[n]

Go

func wordBreak(s string, wordDict []string) bool {
    words := map[string]bool{}
    for _, w := range wordDict {
        words[w] = true
    }
    n := len(s)
    dp := make([]bool, n+1)
    dp[0] = true
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            if dp[j] && words[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

300) Longest Increasing Subsequence

Problem Statement

Given nums, return length of longest strictly increasing subsequence.

Variables To Track

tails x

Solution Flow

flowchart TD
    A[Input for problem 300] --> B[Initialize variables tails x]
    B --> C[binary search position in tails and replace or append]
    C --> D{elements remain}
    D -- Yes --> C
    D -- No --> E[return len tails]

Complexity

Time O n log n. Space O n.

Example

10 9 2 5 3 7 101 18 returns 4

Python

from bisect import bisect_left
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for x in nums:
            i = bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)

Go

import "sort"

func lengthOfLIS(nums []int) int {
    tails := []int{}
    for _, x := range nums {
        i := sort.SearchInts(tails, x)
        if i == len(tails) {
            tails = append(tails, x)
        } else {
            tails[i] = x
        }
    }
    return len(tails)
}

8. Backtracking

39) Combination Sum

Problem Statement

Given candidates and target, return unique combinations summing to target with reuse allowed.

Variables To Track

path remain idx

Solution Flow

flowchart TD
    A[Input for problem 39] --> B[Initialize variables path remain idx]
    B --> C[choose current again or move to next index]
    C --> D{dfs states remain}
    D -- Yes --> C
    D -- No --> E[return all recorded paths]

Complexity

Time exponential. Space recursion plus output.

Example

2 3 6 7 target 7 returns 2 2 3 and 7

Python

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        out = []
        path = []
        candidates.sort()
        def dfs(i: int, rem: int) -> None:
            if rem == 0:
                out.append(path[:])
                return
            if i == len(candidates) or candidates[i] > rem:
                return
            path.append(candidates[i])
            dfs(i, rem - candidates[i])
            path.pop()
            dfs(i + 1, rem)
        dfs(0, target)
        return out

Go

func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    out := [][]int{}
    path := []int{}
    var dfs func(int, int)
    dfs = func(i, rem int) {
        if rem == 0 {
            cp := append([]int{}, path...)
            out = append(out, cp)
            return
        }
        if i == len(candidates) || candidates[i] > rem {
            return
        }
        path = append(path, candidates[i])
        dfs(i, rem-candidates[i])
        path = path[:len(path)-1]
        dfs(i+1, rem)
    }
    dfs(0, target)
    return out
}

46) Permutations

Problem Statement

Given distinct nums, return all permutations.

Variables To Track

path used

Solution Flow

flowchart TD
    A[Input for problem 46] --> B[Initialize variables path used]
    B --> C[pick unused value recurse then unmark]
    C --> D{path length less than n}
    D -- Yes --> C
    D -- No --> E[return all permutations]

Complexity

Time O n times n factorial. Space O n.

Example

1 2 3 returns six permutations

Python

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        out = []
        def backtrack(i: int) -> None:
            if i == len(nums):
                out.append(nums[:])
                return
            for j in range(i, len(nums)):
                nums[i], nums[j] = nums[j], nums[i]
                backtrack(i + 1)
                nums[i], nums[j] = nums[j], nums[i]
        backtrack(0)
        return out

Go

func permute(nums []int) [][]int {
    out := [][]int{}
    var dfs func(int)
    dfs = func(i int) {
        if i == len(nums) {
            cp := append([]int{}, nums...)
            out = append(out, cp)
            return
        }
        for j := i; j < len(nums); j++ {
            nums[i], nums[j] = nums[j], nums[i]
            dfs(i + 1)
            nums[i], nums[j] = nums[j], nums[i]
        }
    }
    dfs(0)
    return out
}

78) Subsets

Problem Statement

Given unique nums, return all subsets.

Variables To Track

idx path

Solution Flow

flowchart TD
    A[Input for problem 78] --> B[Initialize variables idx path]
    B --> C[branch include and exclude current value]
    C --> D{idx less than n}
    D -- Yes --> C
    D -- No --> E[return all subsets]

Complexity

Time O n times two power n. Space O n recursion.

Example

1 2 returns empty 1 2 and 1 2

Python

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        out = []
        path = []
        def dfs(i: int) -> None:
            if i == len(nums):
                out.append(path[:])
                return
            path.append(nums[i])
            dfs(i + 1)
            path.pop()
            dfs(i + 1)
        dfs(0)
        return out

Go

func subsets(nums []int) [][]int {
    out := [][]int{}
    path := []int{}
    var dfs func(int)
    dfs = func(i int) {
        if i == len(nums) {
            cp := append([]int{}, path...)
            out = append(out, cp)
            return
        }
        path = append(path, nums[i])
        dfs(i + 1)
        path = path[:len(path)-1]
        dfs(i + 1)
    }
    dfs(0)
    return out
}

79) Word Search

Problem Statement

Given board and word, return true if word exists by adjacent traversal without cell reuse.

Variables To Track

idx r c

Solution Flow

flowchart TD
    A[Input for problem 79] --> B[Initialize variables idx r c]
    B --> C[match char mark visited recurse four directions then unmark]
    C --> D{dfs path valid}
    D -- Yes --> C
    D -- No --> E[return true if any path reaches end]

Complexity

Time O m n times four power l. Space O l recursion.

Example

board with abcced returns true for word abcced

Python

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        def dfs(r: int, c: int, i: int) -> bool:
            if i == len(word):
                return True
            if r < 0 or c < 0 or r >= m or c >= n or board[r][c] != word[i]:
                return False
            tmp = board[r][c]
            board[r][c] = "#"
            ok = dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1)
            board[r][c] = tmp
            return ok
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

Go

func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    var dfs func(int, int, int) bool
    dfs = func(r, c, i int) bool {
        if i == len(word) {
            return true
        }
        if r < 0 || c < 0 || r >= m || c >= n || board[r][c] != word[i] {
            return false
        }
        ch := board[r][c]
        board[r][c] = '#'
        ok := dfs(r+1, c, i+1) || dfs(r-1, c, i+1) || dfs(r, c+1, i+1) || dfs(r, c-1, i+1)
        board[r][c] = ch
        return ok
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dfs(i, j, 0) {
                return true
            }
        }
    }
    return false
}