Skip to content

AmazonLeetcode

Table of Contents

1. Two Sum

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Hash Map: O(n) time, O(n) space.
        Store seen values so each number can find its complement in one pass.
        """
        hashmap = {}  # val: idx

        for idx, val in enumerate(nums):
            comp = target - val
            if comp in hashmap:
                return [hashmap[comp], idx]

            hashmap[val] = idx

        return []


def test_two_sum():
    s = Solution()
    assert s.twoSum([2, 7, 11, 15], 9) == [0, 1]
    assert s.twoSum([3, 2, 4], 6) == [1, 2]
    assert s.twoSum([3, 3], 6) == [0, 1]
    assert s.twoSum([1, 2, 3, 4, 5], 10) == []
    assert s.twoSum([-1, -2, -3, -4, -5], -8) == [2, 4]

#include <cassert>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
   public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;

        for (size_t i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            if (map.find(diff) != map.end()) {
                return {map[diff], (int)i};
            }
            map[nums[i]] = (int)i;
        }
        return {-1, -1};
    }
};

int main() {
    Solution solution;
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = solution.twoSum(nums, target);
    assert((result == vector<int>{0, 1}));
    return 0;
}

146. LRU Cache

  • LeetCode | 力扣

  • Tags: Hash Table, Linked List, Design, Doubly Linked List

from collections import OrderedDict


class DoublyListNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:
    """
    Design and implement a data structure for Least Recently Used (LRU) cache.
    It should support the following operations: get and put.
    """

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}
        self.head = DoublyListNode()
        self.tail = DoublyListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def add_to_last(self, node):
        self.tail.prev.next = node
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.remove(node)
        self.add_to_last(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self.remove(node)
            self.add_to_last(node)
        else:
            node = DoublyListNode(key=key, val=value)
            self.cache[key] = node
            self.add_to_last(node)

        if len(self.cache) > self.cap:
            lru = self.head.next
            del self.cache[lru.key]
            self.remove(lru)


class LRUCacheOrderedDict:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.cap = capacity

    def get(self, key: int):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key, last=True)
        return self.cache[key]

    def put(self, key: int, value: int):
        if key in self.cache:
            self.cache.move_to_end(key, last=True)
        elif len(self.cache) >= self.cap:
            self.cache.popitem(last=False)

        self.cache[key] = value


def test_lru_cache():
    cache = LRUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    assert cache.get(1) == 1
    cache.put(3, 3)
    assert cache.get(2) == -1
    cache.put(4, 4)
    assert cache.get(1) == -1
    assert cache.get(3) == 3
    assert cache.get(4) == 4

    updated = LRUCache(2)
    updated.put(1, 1)
    updated.put(2, 2)
    updated.put(1, 10)
    updated.put(3, 3)
    assert updated.get(1) == 10
    assert updated.get(2) == -1

    single = LRUCache(1)
    single.put(1, 1)
    single.put(2, 2)
    assert single.get(1) == -1
    assert single.get(2) == 2


def test_lru_cache_ordered_dict():
    cache = LRUCacheOrderedDict(2)
    cache.put(1, 1)
    cache.put(2, 2)
    assert cache.get(1) == 1
    cache.put(3, 3)
    assert cache.get(2) == -1
    cache.put(4, 4)
    assert cache.get(1) == -1
    assert cache.get(3) == 3
    assert cache.get(4) == 4

#include <cassert>
#include <iostream>
#include <unordered_map>
using namespace std;

class Node {
   public:
    int key;
    int val;
    Node *prev;
    Node *next;

    Node(int k = 0, int v = 0) : key(k), val(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
   private:
    int cap;
    unordered_map<int, Node *> cache;
    Node *head;
    Node *tail;

    void remove(Node *node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void insert_to_last(Node *node) {
        tail->prev->next = node;
        node->prev = tail->prev;
        tail->prev = node;
        node->next = tail;
    }

    void move_to_last(Node *node) {
        remove(node);
        insert_to_last(node);
    }

   public:
    LRUCache(int capacity) {
        this->cap = capacity;
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (cache.find(key) != cache.end()) {
            Node *node = cache[key];
            move_to_last(node);
            return node->val;
        }
        return -1;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            Node *node = cache[key];
            node->val = value;
            move_to_last(node);
        } else {
            Node *newNode = new Node(key, value);
            cache[key] = newNode;
            insert_to_last(newNode);

            if ((int)cache.size() > cap) {
                Node *removed = head->next;
                remove(removed);
                cache.erase(removed->key);
                delete removed;
            }
        }
    }
};

int main() {
    LRUCache lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    assert(lru.get(1) == 1);   // returns 1
    lru.put(3, 3);             // evicts key 2
    assert(lru.get(2) == -1);  // returns -1 (not found)
    lru.put(4, 4);             // evicts key 1
    assert(lru.get(1) == -1);  // returns -1 (not found)
    assert(lru.get(3) == 3);   // returns 3
    assert(lru.get(4) == 4);   // returns 4
    return 0;
}

42. Trapping Rain Water

  • LeetCode | 力扣

  • Tags: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack

from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        """Two Pointers: O(n) time, O(1) space.
        Track max from each side; shorter side determines water level.
        """
        left, right = 0, len(height) - 1
        max_l = max_r = res = 0
        while left < right:
            if height[left] < height[right]:
                max_l = max(max_l, height[left])
                res += max_l - height[left]
                left += 1
            else:
                max_r = max(max_r, height[right])
                res += max_r - height[right]
                right -= 1
        return res

    def trapDP(self, height: List[int]) -> int:
        """DP Prefix Max: O(n) time, O(n) space.
        Precompute max heights from left and right.
        """
        n = len(height)
        max_left = [0] * n
        max_right = [0] * n
        for i in range(1, n):
            max_left[i] = max(max_left[i - 1], height[i - 1])
        for i in range(n - 2, -1, -1):
            max_right[i] = max(max_right[i + 1], height[i + 1])
        return sum(max(0, min(max_left[i], max_right[i]) - height[i]) for i in range(n))

    def trapStack(self, height: List[int]) -> int:
        """Monotonic Stack: O(n) time, O(n) space.
        Pop shorter bars and accumulate trapped water by layer.
        """
        stack = []
        res = 0
        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()
                if not stack:
                    break
                w = i - stack[-1] - 1
                h = min(height[i], height[stack[-1]]) - height[top]
                res += w * h
            stack.append(i)
        return res


def test_trap():
    s = Solution()
    for fn in (s.trap, s.trapDP, s.trapStack):
        assert fn([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
        assert fn([4, 2, 0, 3, 2, 5]) == 9
        assert fn([1, 0, 1]) == 1
        assert fn([]) == 0

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution
{
public:
    int trap(vector<int> &height)
    {
        if (height.empty())
            return 0;

        int res = 0;
        int left = 0, right = height.size() - 1;
        int maxL = height[left], maxR = height[right];

        while (left < right)
        {
            if (maxL < maxR)
            {
                left++;
                maxL = max(maxL, height[left]);
                res += maxL - height[left];
            }
            else
            {
                right--;
                maxR = max(maxR, height[right]);
                res += maxR - height[right];
            }
        }
        return res;
    }
};

int main()
{
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    Solution solution;
    cout << solution.trap(height) << endl;
    return 0;
}

121. Best Time to Buy and Sell Stock

"""
-   Return the maximum profit that can be achieved from buying on one day and selling on another day.
"""

from typing import List


# Brute Force
def maxProfitBF(prices: List[int]) -> int:
    max_profit = 0
    n = len(prices)
    for i in range(n):
        for j in range(i + 1, n):
            max_profit = max(max_profit, prices[j] - prices[i])

    return max_profit


# DP
def maxProfitDP(prices: List[int]) -> int:
    dp = [[0] * 2 for _ in range(len(prices))]
    dp[0][0] = -prices[0]  # buy
    dp[0][1] = 0  # sell

    for i in range(1, len(prices)):
        dp[i][0] = max(dp[i - 1][0], -prices[i])  # the lowest price to buy
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])

    return dp[-1][1]


# Greedy
def maxProfitGreedy(prices: List[int]) -> int:
    max_profit = 0
    seen_min = prices[0]

    for i in range(1, len(prices)):
        max_profit = max(max_profit, prices[i] - seen_min)
        seen_min = min(seen_min, prices[i])

    return max_profit


# Fast Slow Pointers
def maxProfitFS(prices: List[int]) -> int:
    max_profit = 0
    slow, fast = 0, 1

    while fast < len(prices):
        if prices[fast] > prices[slow]:
            max_profit = max(max_profit, prices[fast] - prices[slow])
        else:
            slow = fast
        fast += 1

    return max_profit


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# | Brute Force|  O(n^2)|  O(1)   |
# | DP         |  O(n)  |  O(n)   |
# | Greedy     |  O(n)  |  O(1)   |
# | Fast Slow  |  O(n)  |  O(1)   |
# |------------|--------|---------|


prices = [7, 1, 5, 3, 6, 4]
print(maxProfitBF(prices))  # 5
print(maxProfitDP(prices))  # 5
print(maxProfitGreedy(prices))  # 5
print(maxProfitFS(prices))  # 5

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

class Solution {
   public:
    int maxProfitMemo(vector<int> &prices) {
        if (prices.size() <= 1) return 0;

        int seen_min = prices[0];
        int res = 0;

        for (int &price : prices) {
            res = max(res, price - seen_min);
            seen_min = min(seen_min, price);
        }
        return res;
    }
};

int main() {
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    Solution obj;
    cout << obj.maxProfitMemo(prices) << endl;
    return 0;
}

2. Add Two Numbers

from typing import Optional

from leetpattern.utils import LinkedList, ListNode


class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        """Digit Carry Simulation: O(max(m, n)) time, O(max(m, n)) space.
        Walk both reversed lists while carrying overflow into the next digit.
        """
        dummy = ListNode()
        cur = dummy
        carry = 0

        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0

            carry, val = divmod(v1 + v2 + carry, 10)
            cur.next = ListNode(val)
            cur = cur.next

            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        return dummy.next


def test_add_two_numbers():
    s = Solution()

    l1 = LinkedList([2, 4, 3]).head
    l2 = LinkedList([5, 6, 4]).head
    assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [7, 0, 8]

    l1 = LinkedList([0]).head
    l2 = LinkedList([0]).head
    assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [0]

    l1 = LinkedList([9, 9, 9, 9, 9, 9, 9]).head
    l2 = LinkedList([9, 9, 9, 9]).head
    assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [
        8,
        9,
        9,
        9,
        0,
        0,
        0,
        1,
    ]

#include <cassert>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
   public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy;
        ListNode* cur = &dummy;
        int carry = 0;

        while (l1 || l2 || carry) {
            if (l1) {
                carry += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                carry += l2->val;
                l2 = l2->next;
            }
            cur->next = new ListNode(carry % 10);
            cur = cur->next;
            carry /= 10;
        }
        return dummy.next;
    }
};

int main() {
    Solution sol;

    ListNode* l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
    ListNode* l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
    ListNode* result = sol.addTwoNumbers(l1, l2);

    vector<int> expected = {7, 0, 8};
    for (int val : expected) {
        assert(result != nullptr && result->val == val);
        result = result->next;
    }
    assert(result == nullptr);  // End of list

    return 0;
}

200. Number of Islands

  • LeetCode | 力扣

  • Tags: Array, Depth First Search, Breadth First Search, Union Find, Matrix

"""
-   Count the number of islands in a 2D grid.
-   Method 1: DFS
-   Method 2: BFS (use a queue to traverse the grid)

-   How to keep track of visited cells?

    1. Mark the visited cell as `0` (or any other value) to avoid revisiting it.
    2. Use a set to store the visited cells.

-   Steps:
    1. Init: variables
    2. DFS/BFS: starting from the cell with `1`, turn all the connected `1`s to `0`.
    3. Traverse the grid, and if the cell is `1`, increment the count and call DFS/BFS.

![0200](../../assets/0200.jpg)
"""

from collections import deque
from copy import deepcopy
from typing import List


# DFS
def numIslandsDFS(grid: List[List[str]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    res = 0

    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != "1":
            return

        grid[r][c] = "2"

        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == "1":
                dfs(r, c)
                res += 1

    return res


# BFS + Set
def numIslandsBFS1(grid: List[List[str]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    visited = set()
    res = 0

    def bfs(r, c):
        q = deque([(r, c)])

        while q:
            row, col = q.popleft()

            for dr, dc in dirs:
                nr, nc = row + dr, col + dc
                if (
                    nr < 0
                    or nr >= m
                    or nc < 0
                    or nc >= n
                    or grid[nr][nc] == "0"
                    or (nr, nc) in visited
                ):
                    continue

                visited.add((nr, nc))
                q.append((nr, nc))

    for r in range(m):
        for c in range(n):
            if grid[r][c] == "1" and (r, c) not in visited:
                visited.add((r, c))
                bfs(r, c)
                res += 1

    return res


# BFS + Grid
def numIslandsBFS2(grid: List[List[str]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    res = 0

    def bfs(r, c):
        q = deque([(r, c)])

        while q:
            row, col = q.popleft()

            for dr, dc in dirs:
                nr, nc = dr + row, dc + col
                if nr < 0 or nr >= m or nc < 0 or nc >= n or grid[nr][nc] != "1":
                    continue
                grid[nr][nc] = "2"
                q.append((nr, nc))

    for i in range(m):
        for j in range(n):
            if grid[i][j] == "1":
                grid[i][j] = "2"
                bfs(i, j)
                res += 1

    return res


grid = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"],
]

print(numIslandsDFS(deepcopy(grid)))  # 1
print(numIslandsBFS1(deepcopy(grid)))  # 1
print(numIslandsBFS2(deepcopy(grid)))  # 1

#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class Solution {
   public:
    // dfs
    int num_islands_dfs(vector<vector<char>> &grid) {
        int m = grid.size(), n = grid[0].size();
        int res = 0;

        // c++23 lambda recursion
        auto dfs = [&](this auto &&dfs, int r, int c) -> void {
            if (r < 0 || r >= m || c < 0 || 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);
        };

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(i, j);
                }
            }
        }
        return res;
    }

    // bfs
    int num_islands_bfs(vector<vector<char>> &grid) {
        int m = grid.size(), n = grid[0].size();
        int res = 0;
        vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        auto bfs = [&](int r, int c) {
            queue<pair<int, int>> q;
            q.push({r, c});
            grid[r][c] = '0';
            while (!q.empty()) {
                auto [cr, cc] = q.front();
                q.pop();
                for (auto &[dr, dc] : dirs) {
                    int nr = cr + dr, nc = cc + dc;
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                        grid[nr][nc] == '1') {
                        grid[nr][nc] = '0';
                        q.push({nr, nc});
                    }
                }
            }
        };

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    bfs(i, j);
                }
            }
        }
        return res;
    }
};

int main() {
    Solution solution;
    vector<vector<char>> grid = {{'1', '1', '0', '0', '0'},
                                 {'1', '1', '0', '0', '0'},
                                 {'0', '0', '1', '0', '0'},
                                 {'0', '0', '0', '1', '1'}};
    assert(solution.num_islands_dfs(grid) == 3);
    grid = {{'1', '1', '0', '0', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '1', '0', '0'},
            {'0', '0', '0', '1', '1'}};
    assert(solution.num_islands_bfs(grid) == 3);
    return 0;
}

207. Course Schedule

  • LeetCode | 力扣

  • Tags: Depth First Search, Breadth First Search, Graph, Topological Sort

from collections import defaultdict, deque
from typing import List


# BFS (Kahn's Algorithm)
def canFinishBFS(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = defaultdict(list)
    indegree = defaultdict(int)

    for crs, pre in prerequisites:
        graph[pre].append(crs)
        indegree[crs] += 1

    q = deque([i for i in range(numCourses) if indegree[i] == 0])
    count = 0

    while q:
        crs = q.popleft()
        count += 1

        for nxt in graph[crs]:
            indegree[nxt] -= 1

            if indegree[nxt] == 0:
                q.append(nxt)

    return count == numCourses


# DFS + Set
def canFinishDFS1(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = defaultdict(list)
    for crs, pre in prerequisites:
        graph[crs].append(pre)

    visiting = set()

    def dfs(crs):
        if crs in visiting:  # cycle detected
            return False
        if graph[crs] == []:
            return True

        visiting.add(crs)

        for pre in graph[crs]:
            if not dfs(pre):
                return False

        visiting.remove(crs)
        graph[crs] = []

        return True

    for crs in range(numCourses):
        if not dfs(crs):
            return False
    return True


# DFS + List
def canFinishDFS2(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = defaultdict(list)
    for pre, crs in prerequisites:
        graph[crs].append(pre)

    # 0: init, 1: visiting, 2: visited
    status = [0] * numCourses

    def dfs(crs):
        if status[crs] == 1:  # cycle detected
            return False
        if status[crs] == 2:
            return True

        status[crs] = 1

        for pre in graph[crs]:
            if not dfs(pre):
                return False

        status[crs] = 2
        return True

    for crs in range(numCourses):
        if not dfs(crs):
            return False
    return True


prerequisites = [[0, 1], [0, 2], [1, 3], [1, 4], [3, 4]]
print(canFinishBFS(5, prerequisites))  # True
print(canFinishDFS1(5, prerequisites))  # True
print(canFinishDFS2(5, prerequisites))  # True

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class Solution {
   public:
    // BFS
    bool canFinishBFS(int numCourses, vector<vector<int>> &prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses, 0);
        for (auto &pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
            indegree[pre[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        int cnt = 0;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            cnt++;

            for (int nxt : graph[cur]) {
                indegree[nxt]--;
                if (indegree[nxt] == 0) {
                    q.push(nxt);
                }
            }
        }
        return cnt == numCourses;
    }

    // DFS
    bool canFinishDFS(int numCourses, vector<vector<int>> &prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto &pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
        }
        // 0: not visited, 1: visiting, 2: visited
        vector<int> state(numCourses, 0);

        function<bool(int)> dfs = [&](int pre) -> bool {
            state[pre] = 1;  // visiting
            for (int crs : graph[pre]) {
                if (state[crs] == 1 || (state[crs] == 0 && dfs(crs))) {
                    return true;
                }
            }
            state[pre] = 2;  // visited
            return false;
        };

        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0 && dfs(i)) {
                return false;
            }
        }
        return true;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> prerequisites = {{1, 0}, {2, 1}, {3, 2}, {4, 3},
                                         {5, 4}, {6, 5}, {7, 6}, {8, 7},
                                         {9, 8}, {10, 9}};
    int numCourses = 11;
    cout << sol.canFinishBFS(numCourses, prerequisites) << endl;
    cout << sol.canFinishDFS(numCourses, prerequisites) << endl;
    return 0;
}

3. Longest Substring Without Repeating Characters

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """Sliding Window: O(n) time, O(min(n, charset)) space.
        Jump the left edge past each repeated character's previous index.
        """
        left = 0
        res = 0
        seen = {}

        for right, ch in enumerate(s):
            if ch in seen and seen[ch] >= left:
                left = seen[ch] + 1
            seen[ch] = right
            res = max(res, right - left + 1)

        return res

    def lengthOfLongestSubstringSet(self, s: str) -> int:
        """Sliding Window Set: O(n) time, O(min(n, charset)) space.
        Shrink until the current character is unique in the window.
        """
        left = 0
        res = 0
        window = set()

        for right, ch in enumerate(s):
            while ch in window:
                window.remove(s[left])
                left += 1
            window.add(ch)
            res = max(res, right - left + 1)

        return res


def test_length_of_longest_substring():
    s = Solution()
    cases = [
        ("abcabcbb", 3),
        ("bbbbb", 1),
        ("pwwkew", 3),
        ("", 0),
        (" ", 1),
        ("abba", 2),
        ("dvdf", 3),
    ]

    for text, expected in cases:
        assert s.lengthOfLongestSubstring(text) == expected
        assert s.lengthOfLongestSubstringSet(text) == expected

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int lengthOfLongestSubstring(string s) {
    int n = s.length();
    int res = 0;
    int left = 0;
    unordered_set<char> window;

    for (int right = 0; right < n; right++) {
        char ch = s[right];

        while (window.find(ch) != window.end()) {
            window.erase(s[left]);
            left++;
        }

        window.insert(ch);
        res = max(res, right - left + 1);
    }
    return (int)res;
}

int main() {
    string s = "abcabcbb";
    cout << lengthOfLongestSubstring(s) << endl;  // 3
    s = "bbbbb";
    cout << lengthOfLongestSubstring(s) << endl;  // 1
    s = "pwwkew";
    cout << lengthOfLongestSubstring(s) << endl;  // 3
    return 0;
}

15. 3Sum

from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """Two Pointers: O(n^2) time, O(1) space.
        Sort, fix one element, then two-pointer scan for complement.
        """
        n = len(nums)
        if n <= 2:
            return []

        res = []
        nums.sort()

        for k in range(n - 2):
            if k > 0 and nums[k] == nums[k - 1]:
                continue

            i, j = k + 1, n - 1

            while i < j:
                total = nums[k] + nums[i] + nums[j]

                if total > 0:
                    j -= 1
                elif total < 0:
                    i += 1
                else:
                    res.append([nums[k], nums[i], nums[j]])

                    while i < j and nums[i] == nums[i + 1]:
                        i += 1
                    while i < j and nums[j] == nums[j - 1]:
                        j -= 1

                    i += 1
                    j -= 1

        return res


def test_three_sum():
    s = Solution()
    for fn in (s.threeSum,):
        assert fn([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
        assert fn([0, 1, 1]) == []
        assert fn([0, 0, 0]) == [[0, 0, 0]]
        assert fn([]) == []

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();

    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        int left = i + 1, right = n - 1;

        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];

            if (total > 0)
                right--;
            else if (total < 0)
                left++;
            else {
                res.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return res;
}

int main() {
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> res = threeSum(nums);
    for (auto& v : res) {
        for (int i : v) {
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}

4. Median of Two Sorted Arrays

from typing import List


# Brute Force
def findMedianSortedArraysBF(nums1: List[int], nums2: List[int]) -> float:
    nums = sorted(nums1 + nums2)
    n = len(nums)
    if n % 2 == 0:
        return (nums[n // 2 - 1] + nums[n // 2]) / 2
    else:
        return nums[n // 2]


# Binary Search
def findMedianSortedArraysBS(nums1: List[int], nums2: List[int]) -> float:
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    imin, imax, half_len = 0, m, (m + n + 1) // 2

    while imin <= imax:
        i = (imin + imax) // 2
        j = half_len - i

        if i < m and nums2[j - 1] > nums1[i]:
            imin = i + 1
        elif i > 0 and nums1[i - 1] > nums2[j]:
            imax = i - 1
        else:
            if i == 0:
                max_of_left = nums2[j - 1]
            elif j == 0:
                max_of_left = nums1[i - 1]
            else:
                max_of_left = max(nums1[i - 1], nums2[j - 1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m:
                min_of_right = nums2[j]
            elif j == n:
                min_of_right = nums1[i]
            else:
                min_of_right = min(nums1[i], nums2[j])

            return (max_of_left + min_of_right) / 2


# |--------------|-----------------|--------------|
# | Approach     | Time            | Space        |
# |--------------|-----------------|--------------|
# | Brute Force  | O((n+m)log(n+m))| O(n+m)       |
# | Binary Search| O(log(min(n,m)))| O(1)         |
# |--------------|-----------------|--------------|


nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArraysBF(nums1, nums2))  # 2.0
print(findMedianSortedArraysBS(nums1, nums2))  # 2.0

5. Longest Palindromic Substring

class longestPalindrome:
    """Return the longest palindromic substring in s."""

    @staticmethod
    def dp(s: str) -> str:
        n = len(s)
        if n <= 1:
            return s

        start, maxLen = 0, 1

        # Init
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1

        # update
        for j in range(1, n):
            for i in range(j):
                if s[i] == s[j]:
                    if j - i <= 2:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

                    if dp[i][j] and j - i + 1 > maxLen:
                        maxLen = j - i + 1
                        start = i

        return s[start : start + maxLen]

    @staticmethod
    def expand_around_center(s: str) -> str:
        def expand(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1

        if len(s) <= 1:
            return s

        start, end = 0, 0
        for i in range(len(s)):
            odd = expand(i, i)
            even = expand(i, i + 1)

            maxLen = max(odd, even)
            if maxLen > end - start:
                start = i - (maxLen - 1) // 2
                end = i + maxLen // 2

        return s[start : end + 1]


if __name__ == "__main__":
    s = "babad"
    assert longestPalindrome.dp(s) in ["bab", "aba"]
    assert longestPalindrome.expand_around_center(s) in ["bab", "aba"]

767. Reorganize String

  • LeetCode | 力扣

  • Tags: Hash Table, String, Greedy, Sorting, Heap Priority Queue, Counting

import heapq
from collections import Counter


def reorganizeString(s: str) -> str:
    if not s:
        return ""

    heap = [(-freq, char) for char, freq in Counter(s).items()]  # max heap
    heapq.heapify(heap)

    result = []
    prev_count, prev_char = 0, ""

    while heap:
        count, char = heapq.heappop(heap)  # pop the most frequent character
        result.append(char)  # append the character to the result

        if prev_count < 0:  # if the previous character still has remaining count
            heapq.heappush(heap, (prev_count, prev_char))

        prev_count = count + 1  # update the current character's remaining count
        prev_char = char  # update the current character

    # check if there is any invalid result
    if len(result) != len(s):
        return ""

    return "".join(result)


print(reorganizeString("aab"))

56. Merge Intervals

def merge(intervals: list[list[int]]) -> list[list[int]]:
    """
    Merge all overlapping intervals.

    |                    G----H
    |                  E===========F
    |     C--------D
    |  A========B
    |
    |-----------------------------------
    Draw the above to explain the process to the interviewer.
    Time complexity: O(nlogn) due to sorting.
    Space complexity: O(n) for the result list.
    """
    n = len(intervals)
    if n <= 1:
        return intervals

    intervals.sort(key=lambda x: x[0])
    res = [intervals[0]]

    for i in range(1, n):
        if intervals[i][0] <= res[-1][1]:
            res[-1][1] = max(res[-1][1], intervals[i][1])
        else:
            res.append(intervals[i])

    return res


print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Interval
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> res;

    for (auto& range : intervals) {
        if (!res.empty() && range[0] <= res.back()[1]) {
            res.back()[1] = max(res.back()[1], range[1]);
        } else {
            res.emplace_back(range);
        }
    }
    return res;
}

int main() {
    vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    vector<vector<int>> res = merge(intervals);
    for (auto& range : res) {
        cout << range[0] << ", " << range[1] << endl;
    }
    return 0;
}

875. Koko Eating Bananas

from typing import List


class minEatingSpeed:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def canEat(piles, k, h):
            hours = 0
            for pile in piles:
                hours += (pile + k - 1) // k
            return hours <= h

        left, right = 1, max(piles) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if canEat(piles, mid, h):
                right = mid - 1
            else:
                left = mid + 1

        return left


if __name__ == "__main__":
    piles = [3, 6, 7, 11]
    h = 8
    sol = minEatingSpeed()
    assert sol.minEatingSpeed(piles, h) == 4

33. Search in Rotated Sorted Array

from typing import List


# Binary Search
def search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1


nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
print(search(nums, target))  # 4

49. Group Anagrams

from collections import defaultdict
from typing import List


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        """Counting Hash Map: O(n * k) time, O(n) space.
        Words with the same 26-letter frequency tuple are anagrams.
        """
        groups = defaultdict(list)

        for word in strs:
            counts = [0] * 26
            for ch in word:
                counts[ord(ch) - ord("a")] += 1
            groups[tuple(counts)].append(word)

        return list(groups.values())


def test_group_anagrams():
    def normalized(groups):
        return sorted(sorted(group) for group in groups)

    s = Solution()
    result = s.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
    assert normalized(result) == [
        ["ate", "eat", "tea"],
        ["bat"],
        ["nat", "tan"],
    ]
    assert normalized(s.groupAnagrams([""])) == [[""]]
    assert normalized(s.groupAnagrams(["a"])) == [["a"]]

#include <algorithm>
#include <cassert>
#include <ranges>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
   public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;

        for (string& s : strs) {
            string sorted = s;
            ranges::sort(sorted);
            map[sorted].push_back(s);
        }

        vector<vector<string>> res;

        for (auto& kv : map) {
            res.push_back(kv.second);
        }
        return res;
    }
};

int main() {
    Solution solution;
    vector<string> strs = {"eat", "tea", "tan"};
    vector<vector<string>> res = solution.groupAnagrams(strs);
    assert((res == vector<vector<string>>{{"eat", "tea"}, {"tan"}} ||
            res == vector<vector<string>>{{"tan"}, {"eat", "tea"}}));

    return 0;
}

994. Rotting Oranges

"""
-   Return the minimum number of minutes that must elapse until no cell has a fresh orange.
-   Hint: Multi-source BFS to count the level.

![994](https://assets.leetcode.com/uploads/2019/02/16/oranges.png)
"""

from collections import deque
from typing import List


# BFS
def orangesRotting(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    fresh = 0
    q = deque()
    dirs = [[1, 0], [0, 1], [0, -1], [-1, 0]]

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                q.append([i, j])
            elif grid[i][j] == 1:
                fresh += 1
    res = 0

    while q and fresh > 0:
        size = len(q)
        for _ in range(size):
            r, c = q.popleft()
            for dr, dc in dirs:
                nr, nc = dr + r, dc + c
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                    q.append([nr, nc])
                    grid[nr][nc] = 2
                    fresh -= 1
        res += 1

    return res if fresh == 0 else -1


grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
assert orangesRotting(grid) == 4

23. Merge k Sorted Lists

  • LeetCode | 力扣

  • Tags: Linked List, Divide And Conquer, Heap Priority Queue, Merge Sort

"""
-   Prerequisite: 21. Merge Two Sorted Lists
-   Video explanation: [23. Merge K Sorted Lists - NeetCode](https://youtu.be/q5a5OiGbT6Q?si=SQ2dCvsYQ3LQctPh)
"""

import copy
import heapq
from typing import List, Optional

from leetpattern.utils import ListNode, list_from_array, list_to_array


def merge_k_lists_divide_conquer(
    lists: List[Optional[ListNode]],
) -> Optional[ListNode]:
    if not lists or len(lists) == 0:
        return None

    def mergeTwo(l1, l2):
        dummy = ListNode()
        cur = dummy

        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next

            cur = cur.next

        cur.next = l1 if l1 else l2

        return dummy.next

    while len(lists) > 1:
        merged = []

        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(mergeTwo(l1, l2))

        lists = merged

    return lists[0]


def merge_k_lists_heap(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    dummy = ListNode()
    cur = dummy

    min_heap = []  # (val, idx, node)

    for idx, head in enumerate(lists):
        if head:
            heapq.heappush(min_heap, (head.val, idx, head))

    while min_heap:
        _, idx, node = heapq.heappop(min_heap)
        cur.next = node
        cur = cur.next

        node = node.next
        if node:
            heapq.heappush(min_heap, (node.val, idx, node))

    return dummy.next


def test_merge_k_lists() -> None:
    n1 = list_from_array([1, 4])
    n2 = list_from_array([1, 3])
    n3 = list_from_array([2, 6])
    lists = [n1, n2, n3]
    lists1 = copy.deepcopy(lists)
    lists2 = copy.deepcopy(lists)
    assert (list_to_array(merge_k_lists_divide_conquer(lists1))) == [
        1,
        1,
        2,
        3,
        4,
        6,
    ]
    assert (list_to_array(merge_k_lists_heap(lists2))) == [1, 1, 2, 3, 4, 6]

11. Container With Most Water

from typing import List


class Solution:
    def maxArea(self, height: List[int]) -> int:
        """Two Pointers: O(n) time, O(1) space.
        Move the shorter side inward to potentially find a taller line.
        """
        left, right = 0, len(height) - 1
        res = 0

        while left < right:
            w = right - left
            h = min(height[left], height[right])
            res = max(res, w * h)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return res

    def maxAreaBF(self, height: List[int]) -> int:
        """Brute Force: O(n^2) time, O(1) space.
        Check every pair of lines.
        """
        res = 0
        for i in range(len(height)):
            for j in range(i + 1, len(height)):
                res = max(res, min(height[i], height[j]) * (j - i))
        return res


def test_max_area():
    s = Solution()
    for fn in (s.maxArea, s.maxAreaBF):
        assert fn([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
        assert fn([1, 1]) == 1
        assert fn([4, 3, 2, 1, 4]) == 16
        assert fn([1, 2, 1]) == 2

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int res = 0;

    while (left < right) {
        int h = min(height[left], height[right]);
        int w = right - left;
        res = max(res, h * w);

        if (height[left] < height[right])
            left++;
        else
            right--;
    }
    return res;
}

int main() {
    vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    cout << maxArea(height) << endl;  // 49
    return 0;
}

128. Longest Consecutive Sequence

from typing import List


# Set
def longestConsecutiveSet(nums: List[int]) -> int:
    num_set = set(nums)  # O(n)
    longest = 0

    for n in nums:
        if (n - 1) not in num_set:  # left boundary
            length = 1

            while (n + length) in num_set:
                length += 1

            longest = max(longest, length)

    return longest


# Union Find
def longestConsecutiveUF(nums: List[int]) -> int:
    if not nums:
        return 0

    par = {num: num for num in nums}
    rank = {num: 1 for num in nums}

    def find(num):
        p = par[num]
        while p != par[p]:
            p = par[p]
        return p

    def union(num1, num2):
        p1, p2 = find(num1), find(num2)
        if p1 == p2:
            return

        if rank[p1] < rank[p2]:
            par[p1] = p2
            rank[p2] += rank[p1]
        else:
            par[p2] = p1
            rank[p1] += rank[p2]

    for num in nums:
        if num - 1 in par:
            union(num, num - 1)

    return max(rank.values())


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# |  Set       |  O(N)  |  O(N)   |
# | Union Find |  O(N)  |  O(N)   |
# |------------|--------|---------|


nums = [100, 4, 200, 1, 3, 2]
print(longestConsecutiveSet(nums))  # 4
print(longestConsecutiveUF(nums))  # 4

138. Copy List with Random Pointer

from typing import Optional


class Node:
    def __init__(self, x: int, next: "Node" = None, random: "Node" = None):
        self.val = int(x)
        self.next = next
        self.random = random


def copyRandomList(head: "Optional[Node]") -> "Optional[Node]":
    if not head:
        return None

    # Copy nodes and link them together
    cur = head
    while cur:
        new_node = Node(cur.val)
        new_node.next = cur.next
        cur.next = new_node
        cur = new_node.next

    # Copy random pointers
    cur = head
    while cur:
        cur.next.random = cur.random.next if cur.random else None
        cur = cur.next.next

    # Separate the original and copied lists
    cur = head
    new_head = head.next
    while cur:
        new_node = cur.next
        cur.next = new_node.next
        new_node.next = new_node.next.next if new_node.next else None
        cur = cur.next

    return new_head

236. Lowest Common Ancestor of a Binary Tree

from typing import List, Optional

from binarytree import build


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class LowestCommonAncestor:
    def lowestCommonAncestor(
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
    ) -> "TreeNode":
        if not root or q == root or p == root:
            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


if __name__ == "__main__":
    root = build([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
    print(root)
    #     ______3__
    #    /         \
    #   5__         1
    #  /   \       / \
    # 6     2     0   8
    #      / \
    #     7   4
    p = root.left  # 5
    q = root.right  # 1
    sol = LowestCommonAncestor()
    print(sol.lowestCommonAncestor(root, p, q))
    #     ______3__
    #    /         \
    #   5__         1
    #  /   \       / \
    # 6     2     0   8
    #      / \
    #     7   4

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right)
        : val(x), left(left), right(right) {}
};

class Solution {
   public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if (left && right) {
            return root;
        }

        return left ? left : right;
    }
};

int main() { return 0; }

347. Top K Frequent Elements

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Divide And Conquer, Sorting, Heap Priority Queue, Bucket Sort, Counting, Quickselect

import heapq
from collections import Counter
from typing import List


# Heap + Counter
def topKFrequent(nums: List[int], k: int) -> List[int]:
    minHeap = []

    for val, freq in Counter(nums).items():
        if len(minHeap) < k:
            heapq.heappush(minHeap, (freq, val))
        else:
            heapq.heappushpop(minHeap, (freq, val))

    return [i for _, i in minHeap]


# Counter (Most Common)
def topKFrequentCounter(nums: List[int], k: int) -> List[int]:
    commons = Counter(nums).most_common(k)
    return [i for i, _ in commons]


nums = [1, 1, 1, 2, 2, 3]
k = 2
print(topKFrequent(nums, k))  # [1, 2]
print(topKFrequentCounter(nums, k))  # [1, 2]

78. Subsets

from typing import List


# Iterative Inclusion Backtracking
def subsets_iterative_inclusion(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    res, path = [], []

    def dfs(i):
        res.append(path.copy())

        for j in range(i, n):
            path.append(nums[j])
            dfs(j + 1)
            path.pop()

    dfs(0)

    return res


# Binary Decision Backtracking
def subsets_binary_decision(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    res, path = [], []

    def dfs(i):
        if i == n:
            res.append(path.copy())
            return

        # Exclude
        dfs(i + 1)

        # Include
        path.append(nums[i])
        dfs(i + 1)
        path.pop()

    dfs(0)

    return res


print(subsets_iterative_inclusion([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
print(subsets_binary_decision([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

198. House Robber

from functools import cache
from typing import List


class Rob:
    """
    dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    """

    def incursive(self, nums: List[int]) -> int:
        """
        time complexity: O(n)
        space complexity: O(n)
        """
        n = len(nums)
        if n <= 2:
            return max(nums)

        # init
        dp = [0 for _ in range(n)]
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])

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

        return dp[-1]

    def incursive_optimized(self, nums: List[int]) -> int:
        """
        time complexity: O(n)
        space complexity: O(1)
        """
        f0, f1 = 0, 0

        for num in nums:
            f0, f1 = f1, max(f1, f0 + num)

        return f1

    def memoization(self, nums: List[int]) -> int:
        """
        time complexity: O(n)
        space complexity: O(n)
        """
        n = len(nums)

        @cache
        def dp(i: int) -> int:
            if i < 0:
                return 0
            return max(dp(i - 1), dp(i - 2) + nums[i])

        return dp(n - 1)


if __name__ == "__main__":
    nums = [2, 7, 9, 3, 1]
    rob = Rob()
    assert rob.incursive(nums) == 12
    assert rob.incursive_optimized(nums) == 12
    assert rob.memoization(nums) == 12

#include <iostream>
#include <vector>
using namespace std;

int rob(vector<int> &nums) {
    int prev = 0, cur = 0, temp = 0;

    for (int num : nums) {
        temp = cur;
        cur = max(cur, prev + num);
        prev = temp;
    }
    return cur;
}

int main() {
    vector<int> nums = {2, 7, 9, 3, 1};
    cout << rob(nums) << endl;  // 12
    return 0;
}

253. Meeting Rooms II 👑

  • LeetCode | 力扣

  • Tags: Array, Two Pointers, Greedy, Sorting, Heap Priority Queue, Prefix Sum

from heapq import heappop, heappush
from typing import List


class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        """Min Heap: O(n log n) time, O(n) space.
        Track active meeting end times; the peak heap size is the minimum
        number of rooms required.

        Timeline (letters mark meeting endpoints):
            |                          G----H
            |                     E-----------F
            |   C--------------D
            | A----------B
            +----------------------------------

        Heap simulation (earliest end first):
            A: push B                   -> [B]
            C: C < B, push D            -> [B, D]
            E: pop B and D, push F      -> [F]
            G: G < F, push H            -> [H, F]

        The peak heap size is 2, so two rooms are required.
        """
        ends = []
        res = 0

        for start, end in sorted(intervals):
            while ends and ends[0] <= start:
                heappop(ends)
            heappush(ends, end)
            res = max(res, len(ends))

        return res


def test_min_meeting_rooms():
    s = Solution()
    for fn in (s.minMeetingRooms,):
        assert fn([]) == 0
        assert fn([[0, 30], [5, 10], [15, 20]]) == 2
        assert fn([[7, 10], [2, 4]]) == 1
        assert fn([[1, 5], [5, 10], [5, 8]]) == 2

424. Longest Repeating Character Replacement

from collections import defaultdict


# Sliding Window - Variable
def characterReplacement(s: str, k: int) -> int:
    left = 0
    maxCount = 0
    counts = defaultdict(int)
    maxLen = 0

    for right in range(len(s)):
        counts[s[right]] += 1
        maxCount = max(maxCount, counts[s[right]])

        while right - left + 1 - maxCount > k:
            counts[s[left]] -= 1
            left += 1

        maxLen = max(maxLen, right - left + 1)

    return maxLen


s = "ABAB"
k = 2
print(characterReplacement(s, k))  # 4

560. Subarray Sum Equals K

from collections import defaultdict
from typing import List


# Prefix Sum
def subarraySum(nums: List[int], k: int) -> int:
    preSums = defaultdict(int)
    preSums[0] = 1
    curSum = 0
    res = 0

    for num in nums:
        curSum += num
        res += preSums[curSum - k]
        preSums[curSum] += 1

    return res


nums = [1, 1, 1]
k = 2
print(subarraySum(nums, k))  # 2

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int subarraySum(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> prefixSum(n + 1);
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    int res = 0;
    unordered_map<int, int> cnt;

    for (int ps : prefixSum) {
        if (cnt.find(ps - k) != cnt.end()) res += cnt[ps - k];
        cnt[ps]++;
    }
    return res;
}

int main() {
    vector<int> nums = {1, 1, 1};
    int k = 2;
    cout << subarraySum(nums, k) << endl;  // 2
    return 0;
}

31. Next Permutation

from typing import List


def nextPermutation(nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    n = len(nums)
    i = n - 1
    while i > 0 and nums[i - 1] >= nums[i]:
        i -= 1
    if i != 0:
        j = n - 1
        while nums[j] <= nums[i - 1]:
            j -= 1
        nums[i - 1], nums[j] = nums[j], nums[i - 1]

    left, right = i, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1


nums = [1, 2, 3]
nextPermutation(nums)
print(nums)  # [1, 3, 2]
nums = [1, 2, 3, 4, 6, 5]
nextPermutation(nums)
print(nums)  # [1, 2, 3, 5, 4, 6]

55. Jump Game

"""
- Return `True` if you can reach the last index, otherwise `False`.
"""

from typing import List


# Greedy - Interval
def canJump(nums: List[int]) -> bool:
    n = len(nums)
    reach = 0
    i = 0

    while reach >= i:
        if reach >= n - 1:
            return True
        reach = max(reach, i + nums[i])
        i += 1

    return False


if __name__ == "__main__":
    assert canJump([2, 3, 1, 1, 4]) is True
    assert canJump([3, 2, 1, 0, 4]) is False

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

class Solution {
   public:
    bool canJump(vector<int>& nums) {
        int canReach = 0;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            if (i > canReach) return false;
            canReach = max(canReach, i + nums[i]);
        }
        return true;
    }
};

int main() {
    Solution obj;
    vector<int> nums = {2, 3, 1, 1, 4};
    cout << obj.canJump(nums) << endl;
    return 0;
}

3413. Maximum Coins From K Consecutive Bags

  • LeetCode | 力扣

  • Tags: Array, Binary Search, Greedy, Sliding Window, Sorting, Prefix Sum

9. Palindrome Number

"""
-   Return true if the given number is a palindrome. Otherwise, return false.
"""


# Reverse
def isPalindromeReverse(x: int) -> bool:
    if x < 0:
        return False

    return str(x) == str(x)[::-1]


# Left Right Pointers
def isPalindromeLR(x: int) -> bool:
    if x < 0:
        return False

    x = list(str(x))  # 121 -> ['1', '2', '1']

    left, right = 0, len(x) - 1

    while left < right:
        if x[left] != x[right]:
            return False
        left += 1
        right -= 1

    return True


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# |  Reverse   |  O(N)  |   O(N)  |
# | Left Right |  O(N)  |   O(1)  |
# |------------|--------|---------|


x = 121
print(isPalindromeReverse(x))  # True
print(isPalindromeLR(x))  # True

18. 4Sum

from typing import List


# Left Right Pointers
def fourSum(nums: List[int], target: int) -> List[List[int]]:
    """Returns all unique quadruplets that sum up to the target."""
    nums.sort()
    result = []

    for i in range(len(nums) - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        for j in range(i + 1, len(nums) - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue

            left = j + 1
            right = len(nums) - 1

            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]

                if total > target:
                    right -= 1
                elif total < target:
                    left += 1
                else:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1

    return result


nums = [1, 0, -1, 0, -2, 2]
target = 0
print(fourSum(nums, target))
# [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

48. Rotate Image

from copy import deepcopy
from typing import List


# Math
def rotate1(matrix: List[List[int]]) -> None:
    """
    Do not return anything, modify matrix in-place instead.
    """
    n = len(matrix)

    for i in range(n // 2):
        for j in range(i, n - i - 1):
            temp = matrix[i][j]
            matrix[i][j] = matrix[n - j - 1][i]
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
            matrix[j][n - i - 1] = temp


def rotate2(matrix: List[List[int]]) -> None:
    """
    Do not return anything, modify matrix in-place instead.
    """
    n = len(matrix)
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    for i in range(n):
        matrix[i].reverse()


matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(matrix)
# [[1, 2, 3],
#  [4, 5, 6],
#  [7, 8, 9]]
matrix1 = deepcopy(matrix)
rotate1(matrix1)
print(matrix1)
# [[7, 4, 1],
#  [8, 5, 2],
#  [9, 6, 3]]
matrix2 = deepcopy(matrix)
rotate2(matrix2)
print(matrix2)
# [[7, 4, 1],
#  [8, 5, 2],
#  [9, 6, 3]]

53. Maximum Subarray

  • LeetCode | 力扣

  • Tags: Array, Divide And Conquer, Dynamic Programming

from typing import List


# DP Kadane
def maxSubArrayDP(nums: List[int]) -> int:
    n = len(nums)
    dp = [0 for _ in range(n)]

    dp[0] = nums[0]
    res = nums[0]

    for i in range(1, n):
        dp[i] = max(
            dp[i - 1] + nums[i],  # continue the previous subarray
            nums[i],  # start a new subarray
        )
        res = max(res, dp[i])

    return res


# Greedy
def maxSubArrayGreedy(nums: List[int]) -> int:
    max_sum = nums[0]
    cur_sum = 0

    for num in nums:
        cur_sum = max(cur_sum + num, num)
        max_sum = max(max_sum, cur_sum)

    return max_sum


# Prefix Sum
def maxSubArrayPrefixSum(nums: List[int]) -> int:
    prefix_sum = 0
    prefix_sum_min = 0
    res = float("-inf")

    for num in nums:
        prefix_sum += num
        res = max(res, prefix_sum - prefix_sum_min)
        prefix_sum_min = min(prefix_sum_min, prefix_sum)

    return res


nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArrayDP(nums))  # 6
print(maxSubArrayGreedy(nums))  # 6
print(maxSubArrayPrefixSum(nums))  # 6

169. Majority Element

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Divide And Conquer, Sorting, Counting

"""
-   Return the majority element in an array. The majority element is the element that appears more than `n // 2` times.

<iframe width="560" height="315" src="https://www.youtube.com/embed/7pnhv842keE?si=fBYlNfKzdkiLgkF1" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>

| `num` | `count` | `res` |
| ----- | ------- | ----- |
| 2     | 1       | 2     |
| 2     | 2       | 2     |
| 1     | 1       | 2     |
| 1     | 0       | 2     |
| 1     | 1       | 1     |
| 2     | 0       | 1     |
| 2     | 1       | 2     |
"""

from collections import defaultdict
from typing import List


# Hash Map
def majorityElementHashMap(nums: List[int]) -> int:
    n = len(nums)
    freq = defaultdict(int)

    for num in nums:
        freq[num] += 1
        if freq[num] > n // 2:
            return num


# Array - Boyer-Moore Voting Algorithm
def majorityElementArray(nums: List[int]) -> int:
    res = None
    count = 0

    for num in nums:
        if count == 0:
            res = num
        count += 1 if num == res else -1

    return res


# | Algorithm | Time Complexity | Space Complexity |
# |-----------|-----------------|------------------|
# | HashMap   | O(N)            | O(N)             |
# | Array     | O(N)            | O(1)             |
# |-----------|-----------------|------------------|


nums = [2, 2, 1, 1, 1, 2, 2]
print(majorityElementArray(nums))  # 2
print(majorityElementHashMap(nums))  # 2

904. Fruit Into Baskets

from collections import defaultdict
from typing import List


# Sliding Window Variable Size
def totalFruit(fruits: List[int]) -> int:
    n = len(fruits)
    if n <= 2:
        return n

    baskets = defaultdict(int)
    res, left = 0, 0

    for right in range(n):
        baskets[fruits[right]] += 1

        while len(baskets) > 2:
            baskets[fruits[left]] -= 1
            if baskets[fruits[left]] == 0:
                del baskets[fruits[left]]
            left += 1

        res = max(res, right - left + 1)

    return res


fruits = [1, 2, 3, 2, 2]
print(totalFruit(fruits))  # 4

75. Sort Colors

from copy import deepcopy
from typing import List


# Left Right Pointers
def sort_colors_lr_pointers(nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    n = len(nums)
    left = 0
    for right in range(n):
        if nums[right] == 0:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1

    for right in range(left, n):
        if nums[right] == 1:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1


# Three Pointers
def sort_colors_three_pointers(nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    left, right = 0, len(nums) - 1
    cur = 0

    while cur <= right:
        if nums[cur] == 0:
            nums[left], nums[cur] = nums[cur], nums[left]
            left += 1
            cur += 1
        elif nums[cur] == 2:
            nums[right], nums[cur] = nums[cur], nums[right]
            right -= 1
        else:
            cur += 1


nums = [2, 0, 2, 1, 1, 0]
nums1, nums2 = deepcopy(nums), deepcopy(nums)
sort_colors_lr_pointers(nums1)
print(nums1)  # [0, 0, 1, 1, 2, 2]
sort_colors_three_pointers(nums2)
print(nums2)  # [0, 0, 1, 1, 2, 2]

14. Longest Common Prefix

from typing import List


class longestCommonPrefix:
    def horizontal_scan(self, strs: List[str]) -> str:
        if not strs:
            return ""

        prefix = strs[0]
        for i in range(1, len(strs)):
            while not strs[i].startswith(prefix):
                prefix = prefix[:-1]
                if not prefix:
                    return ""

        return prefix

    def vertical_scan(self, strs: List[str]) -> str:
        if not strs:
            return ""

        for i in range(len(strs[0])):
            char = strs[0][i]
            for j in range(1, len(strs)):
                if i >= len(strs[j]) or strs[j][i] != char:
                    return strs[0][:i]

        return strs[0]

    def divide_conquer(self, strs: List[str]) -> str:
        if not strs:
            return ""

        def merge(left, right):
            n = min(len(left), len(right))
            for i in range(n):
                if left[i] != right[i]:
                    return left[:i]
            return left[:n]

        def find(strs, start, end):
            if start == end:
                return strs[start]
            mid = start + (end - start) // 2
            left = find(strs, start, mid)
            right = find(strs, mid + 1, end)
            return merge(left, right)

        return find(strs, 0, len(strs) - 1)

    def binary_search(self, strs: List[str]) -> str:
        if not strs:
            return ""

        def isCommonPrefix(strs, length):
            prefix = strs[0][:length]
            return all(s.startswith(prefix) for s in strs)

        minLen = min(len(s) for s in strs)
        low, high = 0, minLen
        while low < high:
            mid = low + (high - low) // 2
            if isCommonPrefix(strs, mid + 1):
                low = mid + 1
            else:
                high = mid

        return strs[0][:low]


if __name__ == "__main__":
    solution = longestCommonPrefix()
    strs = ["flower", "flow", "flight"]
    assert solution.horizontal_scan(strs) == "fl"
    assert solution.vertical_scan(strs) == "fl"
    assert solution.divide_conquer(strs) == "fl"
    assert solution.binary_search(strs) == "fl"

26. Remove Duplicates from Sorted Array

from typing import List


class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        """Two Pointers: O(n) time, O(1) space.
        Keep `left` at the last unique value and overwrite the next position
        whenever `right` finds a different value.

        Example: nums = [0, 0, 1, 1, 2]
            start:   left = 0, unique prefix = [0]
            right 0: 0 == 0 -> unchanged
            right 1: 0 == 0 -> unchanged
            right 2: 1 != 0 -> left = 1, prefix = [0, 1]
            right 3: 1 == 1 -> unchanged
            right 4: 2 != 1 -> left = 2, prefix = [0, 1, 2]
        Return 3; the first three values are [0, 1, 2].
        """
        if not nums:
            return 0

        n = len(nums)
        left = 0

        for right in range(n):
            if nums[right] != nums[left]:
                left += 1
                nums[left] = nums[right]

        return left + 1


def test_remove_duplicates():
    s = Solution()
    for fn in (s.removeDuplicates,):
        cases = [
            ([], []),
            ([1], [1]),
            ([1, 1, 2], [1, 2]),
            ([0, 0, 1, 1, 1, 2, 2, 3, 3, 4], [0, 1, 2, 3, 4]),
        ]
        for nums, expected in cases:
            k = fn(nums)
            assert k == len(expected)
            assert nums[:k] == expected

#include <cassert>
#include <vector>
using namespace std;

class Solution {
   public:
    int removeDuplicates(vector<int>& nums) {
        int fast = 1, slow = 1;
        int n = nums.size();

        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    assert(solution.removeDuplicates(nums) == 5);
    return 0;
}

735. Asteroid Collision

20. Valid Parentheses

# Stack
def is_valid(s: str) -> bool:
    if len(s) % 2:
        return False

    pairs = {
        "(": ")",
        "{": "}",
        "[": "]",
    }
    stack = []
    for ch in s:
        if ch in pairs:
            stack.append(ch)
        elif not stack or ch != pairs[stack.pop()]:
            return False

    return True if not stack else False


def test_is_valid():
    assert is_valid("()[]{}")
    assert not is_valid("(]")
    assert not is_valid("([)]")
    assert is_valid("{[]}")

#include <cassert>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
   public:
    bool isValid(string s) {
        unordered_map<char, char> map{{')', '('}, {'}', '{'}, {']', '['}};
        stack<char> stack;
        if (s.length() % 2 == 1) return false;

        for (char& ch : s) {
            if (stack.empty() || map.find(ch) == map.end()) {
                stack.push(ch);
            } else {
                if (map[ch] != stack.top()) {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.empty();
    }
};

int main() {
    Solution s;
    assert(s.isValid("()") == true);
    assert(s.isValid("()[]{}") == true);
    assert(s.isValid("(]") == false);
    assert(s.isValid("([)]") == false);
    assert(s.isValid("{[]}") == true);
    return 0;
}

62. Unique Paths

"""
-   Count the number of unique paths to reach the bottom-right corner of a `m x n` grid.

![62](https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png)
"""


# DP - 2D
def uniquePaths(m: int, n: int) -> int:
    if m == 1 or n == 1:
        return 1

    dp = [[1] * n for _ in range(m)]

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

    return dp[-1][-1]


print(uniquePaths(m=3, n=7))  # 28
# [[1, 1, 1,  1,  1,  1,  1],
#  [1, 2, 3,  4,  5,  6,  7],
#  [1, 3, 6, 10, 15, 21, 28]]

#include <iostream>
#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    vector dp(m, vector<int>(n, 1));

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

int main() {
    int m = 3, n = 7;
    cout << uniquePaths(m, n) << endl;  // 28
    return 0;
}

70. Climbing Stairs

from functools import cache


class Solution:
    def climbStairs(self, n: int) -> int:
        """Optimized DP: O(n) time, O(1) space.
        Only the previous two counts are needed to compute the next stair.
        """
        if n <= 2:
            return n

        first, second = 1, 2
        for _ in range(3, n + 1):
            first, second = second, first + second
        return second

    def climbStairsDP(self, n: int) -> int:
        """Tabulation DP: O(n) time, O(n) space.
        Each stair count is the sum of the ways to reach the previous two stairs.
        """
        if n <= 2:
            return n

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

    def climbStairsGreedy(self, n: int) -> int:
        """Greedy Rolling Counts: O(n) time, O(1) space.
        The next answer is always determined by the two latest reachable counts.
        """
        if n <= 2:
            return n

        prev, cur = 1, 2
        for _ in range(3, n + 1):
            prev, cur = cur, prev + cur
        return cur

    def climbStairsDFS(self, n: int) -> int:
        """Memoized DFS: O(n) time, O(n) space.
        Caching prevents recomputing the same remaining-stair subproblems.
        """

        @cache
        def dfs(i: int) -> int:
            if i <= 2:
                return i
            return dfs(i - 1) + dfs(i - 2)

        return dfs(n)


def test_climb_stairs():
    s = Solution()
    for fn in (
        s.climbStairs,
        s.climbStairsDP,
        s.climbStairsGreedy,
        s.climbStairsDFS,
    ):
        assert fn(1) == 1
        assert fn(2) == 2
        assert fn(3) == 3
        assert fn(10) == 89

#include <cassert>
#include <iostream>
using namespace std;

int climbStairs(int n) {
    if (n <= 2) return n;
    int f1 = 1, f2 = 2;
    int res;

    int i = 3;
    while (i <= n) {
        res = f1 + f2;
        f1 = f2;
        f2 = res;
        i++;
    }
    return res;
}

int main() {
    assert(climbStairs(2) == 2);
    assert(climbStairs(5) == 8);
    assert(climbStairs(10) == 89);
    return 0;
}

239. Sliding Window Maximum

  • LeetCode | 力扣

  • Tags: Array, Queue, Sliding Window, Heap Priority Queue, Monotonic Queue

from collections import deque
from typing import List


# Monotonic Queue
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    q = deque()
    res = []

    for i, num in enumerate(nums):
        if q and q[0] < i - k + 1:
            q.popleft()

        while q and nums[q[-1]] < num:
            q.pop()

        q.append(i)

        if i >= k - 1:
            res.append(nums[q[0]])

    return res


nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(maxSlidingWindow(nums, k))  # [3, 3, 5, 5, 6, 7]

739. Daily Temperatures

"""
-   Return an array `res` such that `res[i]` is the number of days you have to wait after the `ith` day to get a warmer temperature.

| Index | Temp | > stack last | stack                           | result    |
| ----- | ---- | ------------ | ------------------------------- | --------- |
| 0     | 73   | False        | `[ [73, 0] ]`                   | 1 - 0 = 1 |
| 1     | 74   | True         | `[ [74, 1] ]`                   | 2 - 1 = 1 |
| 2     | 75   | True         | `[ [75, 2] ]`                   | 6 - 2 = 4 |
| 3     | 71   | False        | `[ [75, 2], [71, 3] ]`          | 5 - 3 = 2 |
| 4     | 69   | False        | `[ [75, 2], [71, 3], [69, 4] ]` | 5 - 4 = 1 |
| 5     | 72   | True         | `[ [75, 2], [72, 5] ]`          | 6 - 5 = 1 |
| 6     | 76   | True         | `[ [76, 6] ]`                   | 0         |
| 7     | 73   | False        | `[[76, 6], [73, 7]]`            | 0         |
"""

from typing import List


# Monotonic Stack
def dailyTemperatures(temperatures: List[int]) -> List[int]:
    res = [0 for _ in range(len(temperatures))]
    stack = []  # [temp, index]

    for i, temp in enumerate(temperatures):
        while stack and temp > stack[-1][0]:
            _, idx = stack.pop()
            res[idx] = i - idx

        stack.append([temp, i])

    return res


print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

76. Minimum Window Substring

from collections import Counter


def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""

    counts = Counter(t)
    required = len(counts)

    left, right = 0, 0
    formed = 0
    window_counts = dict()

    result = float("inf"), None, None

    while right < len(s):
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        if char in counts and window_counts[char] == counts[char]:
            formed += 1

        while left <= right and formed == required:
            char = s[left]
            if right - left + 1 < result[0]:
                result = (right - left + 1, left, right)
            window_counts[char] -= 1
            if char in counts and window_counts[char] < counts[char]:
                formed -= 1
            left += 1

        right += 1

    return "" if result[0] == float("inf") else s[result[1] : result[2] + 1]


s = "ADOBECODEBANC"
t = "ABC"
print(minWindow(s, t))  # BANC

1752. Check if Array Is Sorted and Rotated

322. Coin Change

  • LeetCode | 力扣

  • Tags: Array, Dynamic Programming, Breadth First Search

from typing import List


def coinChange(coins: List[int], amount: int) -> int:
    dp = [float("inf") for _ in range(amount + 1)]

    dp[0] = 0

    for i in range(1, amount + 1):
        for c in coins:
            if i - c >= 0:
                dp[i] = min(dp[i], 1 + dp[i - c])

    return dp[amount] if dp[amount] != float("inf") else -1


coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount))  # 3

84. Largest Rectangle in Histogram

from typing import List


class LargestRectangleArea:
    def monotonic_stack(self, heights: List[int]) -> int:
        stack = []
        res = 0
        n = len(heights)

        for i in range(n + 1):
            h = heights[i] if i < n else 0

            while stack and h < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                res = max(res, height * width)

            stack.append(i)

        return res


if __name__ == "__main__":
    sol = LargestRectangleArea()
    assert sol.monotonic_stack([2, 1, 5, 6, 2, 3]) == 10
    assert sol.monotonic_stack([2, 4]) == 4

238. Product of Array Except Self

"""
-   Classic **Prefix Sum** problem
-   Return an array `output` such that `output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.

| Approach           | Time | Space |
| ------------------ | ---- | ----- |
| Prefix             | O(n) | O(n)  |
| Prefix (Optimized) | O(n) | O(1)  |
"""

from typing import List


# Prefix
def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    prefix = [1 for _ in range(n)]
    suffix = [1 for _ in range(n)]

    for i in range(1, n):
        prefix[i] = nums[i - 1] * prefix[i - 1]

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

    result = [i * j for i, j in zip(prefix, suffix)]

    return result


# Prefix (Optimized)
def productExceptSelfOptimized(nums: List[int]) -> List[int]:
    n = len(nums)
    result = [1 for _ in range(n)]

    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result


print(productExceptSelf([1, 2, 3, 4]))
# [24, 12, 8, 6]
print(productExceptSelfOptimized([1, 2, 3, 4]))
# [24, 12, 8, 6]

#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

class Solution {
   public:
    vector<int> productExceptSelf(vector<int> &nums) {
        int n = nums.size();
        vector<int> prefix(n, 1);
        vector<int> suffix(n, 1);
        vector<int> res(n, 1);

        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }

        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < n; i++) {
            res[i] = prefix[i] * suffix[i];
        }
        return res;
    }
};

int main() {
    vector<int> nums = {1, 2, 3, 4};
    Solution obj;
    vector<int> result = obj.productExceptSelf(nums);
    assert(result == vector<int>({24, 12, 8, 6}));
    return 0;
}

34. Find First and Last Position of Element in Sorted Array

from bisect import bisect_left
from typing import List


class searchRange:
    """
    找 lower bound 和 upper bound
    看灵神对这道题的题解，分类讨论区间的写法
    target 的 upper bound 是 target + 1 的 lower bound - 1
    这样就能统一用 lower bound 的写法
    """

    # [left, right]
    def bisect_left_closed(self, nums, target):
        """
        闭区间写法
        """
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

    # [left, right)
    def bisect_left_right_open(self, nums, target):
        """
        左闭右开区间写法
        """
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid
            else:
                left = mid + 1
        return left

    # (left, right)
    def bisect_left_open(self, nums, target):
        """
        推荐开区间写法
        """
        left, right = -1, len(nums)
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid
            else:
                right = mid
        return right

    def search_range(self, nums: List[int], target: int) -> List[int]:
        # edge case
        if not nums:
            return [-1, -1]

        lower = self.bisect_left_closed(nums, target)
        upper = self.bisect_left_closed(nums, target + 1) - 1

        return [lower, upper] if lower <= upper else [-1, -1]

    def search_range_bisect(self, nums: List[int], target: int) -> List[int]:
        """用 python bisect 库函数"""
        # edge case
        if not nums:
            return [-1, -1]

        lower = bisect_left(nums, target)
        upper = bisect_left(nums, target + 1) - 1

        return [lower, upper] if lower <= upper else [-1, -1]


if __name__ == "__main__":
    nums = [5, 7, 7, 8, 8, 10]
    target = 8
    sol = searchRange()
    assert sol.search_range(nums, target) == [3, 4]
    assert sol.search_range_bisect(nums, target) == [3, 4]

#include <vector>
#include <iostream>
using namespace std;

class Solution
{
  int bisect_left(vector<int> &nums, int target)
  {
    int left = 0, right = (int)nums.size() - 1;

    while (left <= right)
    {
      int mid = left + (right - left) / 2;
      if (nums[mid] < target)
      {
        left = mid + 1;
      }
      else
      {
        right = mid - 1;
      }
    }
    return left;
  }

public:
  vector<int> searchRange(vector<int> &nums, int target)
  {
    int left = bisect_left(nums, target);
    if (left == (int)nums.size() || nums[left] != target)
    {
      return {-1, -1};
    }
    int right = bisect_left(nums, target + 1) - 1;
    return {left, right};
  }
};

int main()
{
  vector<int> nums = {5, 7, 7, 8, 8, 10};
  int target = 8;
  Solution s;
  vector<int> res = s.searchRange(nums, target);
  cout << res[0] << ", " << res[1] << endl;
  return 0;
}

981. Time Based Key-Value Store

from collections import defaultdict


# Binary Search
class TimeMap:

    def __init__(self):
        self.keys = defaultdict(list)
        self.times = dict()

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

    def get(self, key: str, timestamp: int) -> str:
        tmp = self.keys[key]

        left, right = 0, len(tmp) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if tmp[mid] > timestamp:
                right = mid - 1
            else:
                left = mid + 1

        return self.times[tmp[right]] if right >= 0 else ""


obj = TimeMap()
obj.set("foo", "bar", 1)
print(obj.get("foo", 1))  # bar
print(obj.get("foo", 3))  # bar
obj.set("foo", "bar2", 4)
print(obj.get("foo", 4))  # bar2
print(obj.get("foo", 5))  # bar2

155. Min Stack

"""
-   Implement a stack that supports push, pop, top, and retrieving the minimum element in constant time.
"""


# Stack
class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        if self.stack:
            self.stack.append((val, min(val, self.getMin())))
        else:
            self.stack.append((val, val))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]


obj = MinStack()
obj.push(3)
obj.push(2)
obj.pop()
print(obj.top())  # 3
print(obj.getMin())  # 3

#include <algorithm>
#include <climits>
#include <iostream>
#include <stack>
#include <utility>
using namespace std;

class MinStack {
    stack<pair<int, int>> st;

   public:
    MinStack() { st.emplace(0, INT_MAX); }

    void push(int val) { st.emplace(val, min(getMin(), val)); }

    void pop() { st.pop(); }

    int top() { return st.top().first; }

    int getMin() { return st.top().second; }
};

int main() {
    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    cout << minStack.getMin() << endl;  // -3
    minStack.pop();
    cout << minStack.top() << endl;     // 0
    cout << minStack.getMin() << endl;  // -2
    return 0;
}

35. Search Insert Position

"""
-   Return the index of the target if it is found. If not, return the index where it would be if it were inserted in order.
"""

from typing import List


# Binary Search
def searchInsert(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            return mid

    return left


nums = [1, 3, 5, 6]
target = 5
print(searchInsert(nums, target))  # 2

#include <cassert>
#include <vector>
using namespace std;

class Solution {
   public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {1, 3, 5, 6};
    assert(solution.searchInsert(nums, 5) == 2);
    assert(solution.searchInsert(nums, 2) == 1);
    assert(solution.searchInsert(nums, 7) == 4);
    assert(solution.searchInsert(nums, 0) == 0);
    return 0;
}

19. Remove Nth Node From End of List

"""
-   Given the `head` of a linked list, remove the `n-th` node from the end of the list and return its head.
"""

from typing import Optional

from leetpattern.utils import ListNode, list_from_array, list_to_array


# Linked List
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    fast, slow = dummy, dummy

    for _ in range(n):
        fast = fast.next

    while fast.next:
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next

    return dummy.next


def test_removeNthFromEnd() -> None:
    head = list_from_array([1, 2, 3, 4, 5])
    assert (list_to_array(removeNthFromEnd(head, 2))) == [1, 2, 3, 5]

242. Valid Anagram

"""
-   Return true if an input string is an anagram of another string.
-   An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once, e.g., `listen` is an anagram of `silent`.
"""

from collections import Counter


# Hashmap
def isAnagramHash(s: str, t: str) -> bool:
    """Return True if t is an anagram of s, False otherwise."""
    if len(s) != len(t):
        return False

    count = dict()

    for i in s:
        if i in count:
            count[i] += 1
        else:
            count[i] = 1

    for j in t:
        if j in count:
            count[j] -= 1
        else:
            return False

    for count in count.values():
        if count != 0:
            return False

    return True


# Array
def isAnagramArray(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    count = [0 for _ in range(26)]

    for i in s:
        count[ord(i) - ord("a")] += 1

    for j in t:
        count[ord(j) - ord("a")] -= 1

    for i in count:
        if i != 0:
            return False

    return True


# Counter
def isAnagramCounter(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)


# |-------------|-----------------|--------------|
# |  Approach   |      Time       |    Space     |
# |-------------|-----------------|--------------|
# |   Hashmap   |       O(n)      |     O(1)     |
# |    Array    |       O(n)      |     O(1)     |
# |   Counter   |       O(n)      |     O(1)     |
# |-------------|-----------------|--------------|


s = "anagram"
t = "nagaram"
print(isAnagramHash(s, t))  # True
print(isAnagramArray(s, t))  # True
print(isAnagramCounter(s, t))  # True

#include <cassert>
#include <string>
#include <vector>
using namespace std;

class Solution {
   public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;

        vector<int> count(26, 0);

        for (char ch : s) count[ch - 'a']++;
        for (char ch : t) count[ch - 'a']--;
        for (int c : count) {
            if (c != 0) return false;
        }

        return true;
    }
};

int main() {
    Solution solution;
    assert(solution.isAnagram("anagram", "nagaram") == true);
    assert(solution.isAnagram("rat", "car") == false);
    assert(solution.isAnagram("a", "ab") == false);
    assert(solution.isAnagram("a", "a") == true);
    return 0;
}

234. Palindrome Linked List

from typing import Optional

from leetpattern.utils import ListNode


# Linked List
def isPalindrome(head: Optional[ListNode]) -> bool:
    if not head or not head.next:
        return True

    def middle(node):
        fast, slow = node, node
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse(node):
        cur, pre = node, None
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    mid1 = head
    mid2 = reverse(middle(head))

    while mid2:
        if mid1.val != mid2.val:
            return False
        mid1 = mid1.next
        mid2 = mid2.next

    return True


head = ListNode().create([1, 2, 2, 1])
print(isPalindrome(head))  # True

621. Task Scheduler

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Greedy, Sorting, Heap Priority Queue, Counting

import heapq
from collections import Counter, deque
from typing import List


def least_interval_heap(tasks: List[str], n: int) -> int:
    count = Counter(tasks)
    heap = [-c for c in count.values()]
    heapq.heapify(heap)

    res = 0

    q = deque()

    while heap or q:
        res += 1

        if heap:
            cnt = 1 + heapq.heappop(heap)
            if cnt:
                q.append((cnt, res + n))

        if q and q[0][1] == res:
            heapq.heappush(heap, q.popleft()[0])

    return res


def least_interval_math(tasks: List[str], n: int) -> int:
    freq = Counter(tasks)

    max_exec = max(freq.values())
    max_count = sum(1 for v in freq.values() if v == max_exec)

    return max((max_exec - 1) * (n + 1) + max_count, len(tasks))


def test_least_interval_heap():
    assert least_interval_heap(["A", "A", "A", "B", "B", "B"], 2) == 8
    assert least_interval_heap(["A"], 0) == 1
    assert least_interval_heap(["A", "A", "A", "B", "B", "B"], 0) == 6
    assert least_interval_heap(["A", "A", "A", "A", "B", "B", "B", "C", "C"], 2) == 10


def test_least_interval_math():
    assert least_interval_math(["A", "A", "A", "B", "B", "B"], 2) == 8
    assert least_interval_math(["A"], 0) == 1
    assert least_interval_math(["A", "A", "A", "B", "B", "B"], 0) == 6
    assert least_interval_math(["A", "A", "A", "A", "B", "B", "B", "C", "C"], 2) == 10

125. Valid Palindrome

# List Comprehension
def isPalindrome(s: str) -> bool:
    s = [char.lower() for char in s if char.isalnum()]
    return s == s[::-1]


# Left Right Pointers
def isPalindromeLR(s: str) -> bool:
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True


s = "A man, a plan, a canal: Panama"
print(isPalindrome(s))  # True
print(isPalindromeLR(s))  # True

443. String Compression

94. Binary Tree Inorder Traversal

  • LeetCode | 力扣

  • Tags: Stack, Tree, Depth First Search, Binary Tree

from typing import List, Optional

from binarytree import Node as TreeNode
from binarytree import build


# Recursive
def inorderTraversalRecursive(root: TreeNode) -> List[int]:
    res = []

    def dfs(node):
        if not node:
            return

        dfs(node.left)
        res.append(node.val)  # <--
        dfs(node.right)

    dfs(root)

    return res


# Iterative
def inorderTraversalIterative(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []

    stack = []
    res = []
    cur = root

    while cur or stack:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right

    return res


tree = build([0, 1, 2, 3, 4, 5, 6])
print(tree)
#     __0__
#    /     \
#   1       2
#  / \     / \
# 3   4   5   6
print(inorderTraversalRecursive(tree))  # [3, 1, 4, 0, 5, 2, 6]
print(inorderTraversalIterative(tree))  # [3, 1, 4, 0, 5, 2, 6]

124. Binary Tree Maximum Path Sum

  • LeetCode | 力扣

  • Tags: Dynamic Programming, Tree, Depth First Search, Binary Tree

from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


def maxPathSum(root: Optional[TreeNode]) -> int:
    res = float("-inf")

    def dfs(node):
        if not node:
            return 0

        leftMax = max(dfs(node.left), 0)
        rightMax = max(dfs(node.right), 0)

        cur = node.val + leftMax + rightMax
        nonlocal res
        res = max(res, cur)

        return node.val + max(leftMax, rightMax)

    dfs(root)

    return res


root = build([-10, 9, 20, None, None, 15, 7])
print(root)
#   -10___
#  /      \
# 9       _20
#        /   \
#       15    7
print(maxPathSum(root))  # 42

1344. Angle Between Hands of a Clock

17. Letter Combinations of a Phone Number

"""
-   Return all possible letter combinations that the number could represent.

![17](https://assets.leetcode.com/uploads/2022/03/15/1200px-telephone-keypad2svg.png)
"""

from typing import List


# Backtracking
def letterCombinations(digits: str) -> List[str]:
    letter_map = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }

    n = len(digits)
    if n == 0:
        return []

    res = []

    def dfs(idx, path):
        if idx == n:
            res.append(path)
            return None

        letters = letter_map[digits[idx]]

        for i in range(len(letters)):
            dfs(idx + 1, path + letters[i])

    dfs(0, "")

    return res


if __name__ == "__main__":
    assert letterCombinations("23") == [
        "ad",
        "ae",
        "af",
        "bd",
        "be",
        "bf",
        "cd",
        "ce",
        "cf",
    ]

54. Spiral Matrix

"""
-   Return all elements of the matrix in spiral order.
"""

from typing import List


# Array
def spiralOrder(matrix: List[List[int]]) -> List[int]:
    if not matrix or not matrix[0]:
        return []

    res = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:

        for i in range(left, right + 1):
            res.append(matrix[top][i])
        top += 1

        for i in range(top, bottom + 1):
            res.append(matrix[i][right])
        right -= 1

        if top <= bottom:

            for i in range(right, left - 1, -1):
                res.append(matrix[bottom][i])
            bottom -= 1

        if left <= right:

            for i in range(bottom, top - 1, -1):
                res.append(matrix[i][left])
            left += 1

    return res


# Math
def spiralOrderMath(matrix: List[List[int]]) -> List[int]:
    dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]  # Right Down Left Up
    m, n = len(matrix), len(matrix[0])
    size = m * n
    res = []
    i, j, di = 0, -1, 0

    while len(res) < size:
        dx, dy = dirs[di]
        for _ in range(n):
            i += dx
            j += dy
            res.append(matrix[i][j])
        di = (di + 1) % 4
        n, m = m - 1, n

    return res


print(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
# [1, 2, 3, 6, 9, 8, 7, 4, 5]
print(spiralOrderMath([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]))
# [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

162. Find Peak Element

27. Remove Element

"""
-   Remove all instances of a given value in-place.
"""

from typing import List


# Fast Slow Pointers
def removeElement(nums: List[int], val: int) -> int:
    fast, slow = 0, 0

    while fast < len(nums):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
        fast += 1

    return slow


nums = [0, 1, 2, 2, 3, 0, 4, 2]
val = 2
print(removeElement(nums, val))  # 5

#include <iostream>
#include <vector>
using namespace std;

// Fast Slow Pointers
int removeElement(vector<int>& nums, int val) {
    size_t n = nums.size();
    size_t slow = 0, fast = 0;

    while (fast < n) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return (int)slow;
}

int main() {
    vector<int> nums = {3, 2, 2, 3};
    int val = 3;
    cout << removeElement(nums, val) << endl;  // 2
    return 0;
}

175. Combine Two Tables

16. 3Sum Closest

from typing import List


# Left Right Pointers
def threeSumClosest(nums: List[int], target: int) -> int:
    nums.sort()
    n = len(nums)
    res = 0
    minDiff = float("inf")

    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, n - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total > target:
                if total - target < minDiff:
                    minDiff = total - target
                    res = total
                right -= 1

            elif total < target:
                if target - total < minDiff:
                    minDiff = target - total
                    res = total
                left += 1

            else:
                return total

    return res


nums = [-1, 2, 1, -4]
target = 1
assert threeSumClosest(nums, target) == 2

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

using namespace std;

int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int res = 0;
    int minDiff = INT_MAX;

    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = n - 1;
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];

            int diff = abs(total - target);
            if (diff < minDiff) {
                minDiff = diff;
                res = total;
            }

            if (total > target)
                right--;
            else if (total < target)
                left++;
            else
                return total;
        }
    }
    return res;
}

int main() {
    vector<int> nums = {-1, 2, 1, -4};
    int target = 1;
    cout << threeSumClosest(nums, target) << endl;
    return 0;
}

46. Permutations

from typing import List


# Backtracking
def permute(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    path, res = [], []
    used = [False for _ in range(n)]

    def dfs(x: int):
        if x == n:
            res.append(path[:])
            return

        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            dfs(x + 1)
            path.pop()
            used[i] = False

    dfs(0)

    return res


print(permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3],
#  [2, 3, 1], [3, 1, 2], [3, 2, 1]]

1929. Concatenation of Array

8. String to Integer (atoi)

907. Sum of Subarray Minimums

  • LeetCode | 力扣

  • Tags: Array, Dynamic Programming, Stack, Monotonic Stack

796. Rotate String

# String
def rotateString(s: str, goal: str) -> bool:
    n = len(s)
    s += s

    for i in range(n):
        if s[i : i + n] == goal:
            return True

    return False


s = "abcde"
goal = "cdeab"
print(rotateString(s, goal))  # True

142. Linked List Cycle II

from typing import Optional

from leetpattern.utils import LinkedList, ListNode


def detectCycle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow, fast = head, head

    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next

        if slow == fast:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow

    return None


def test_detectCycle():
    l1 = LinkedList([3, 2, 0, -4])
    l1.make_cycle(1)
    assert detectCycle(l1.head).val == 2
    l2 = LinkedList([3, 2, 0, -4])
    assert not detectCycle(l2.head)

#include <cassert>
#include <iostream>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
   public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (fast == slow) {
                slow = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

int main() {
    Solution sol;

    ListNode* head = new ListNode(3);
    head->next = new ListNode(2);
    head->next->next = new ListNode(0);
    head->next->next->next = new ListNode(-4);
    head->next->next->next->next = head->next;  // Create a cycle
    assert(sol.detectCycle(head) == head->next);

    ListNode* head2 = new ListNode(1);
    head2->next = new ListNode(2);
    head2->next->next = head2;  // Create a cycle
    assert(sol.detectCycle(head2) == head2);

    ListNode* head3 = new ListNode(1);
    assert(sol.detectCycle(head3) == nullptr);

    ListNode* head4 = nullptr;
    assert(sol.detectCycle(head4) == nullptr);

    return 0;
}

349. Intersection of Two Arrays

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Two Pointers, Binary Search, Sorting

from typing import List


# Set
def intersectionSet(nums1: List[int], nums2: List[int]) -> List[int]:
    set1 = set(nums1)
    set2 = set(nums2)
    return list(set1 & set2)


# Hash
def intersectionHash(nums1: List[int], nums2: List[int]) -> List[int]:
    set1 = set(nums1)
    result = set()

    for num in nums2:
        if num in set1:
            result.add(num)

    return list(result)


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# |     Set    | O(n+m) |  O(n+m) |
# |    Hash    | O(n+m) |   O(n)  |
# |------------|--------|---------|


nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersectionSet(nums1, nums2))  # [2]
print(intersectionHash(nums1, nums2))  # [2]

21. Merge Two Sorted Lists

"""
-   Task: Merge the two linked lists into one sorted list.
"""

from typing import Optional

from leetpattern.utils import ListNode


# Linked List
def merge_two_lists(
    list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
    dummy = ListNode()
    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

    if list1:
        cur.next = list1
    elif list2:
        cur.next = list2

    return dummy.next

#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
   public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy;
        ListNode* cur = &dummy;

        while (list1 && 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 ? list1 : list2;

        return dummy.next;
    }
};

int main() {
    Solution sol;
    ListNode* list1 = new ListNode(1, new ListNode(2, new ListNode(4)));
    ListNode* list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
    ListNode* merged = sol.mergeTwoLists(list1, list2);
    vector<int> res;
    while (merged) {
        res.push_back(merged->val);
        merged = merged->next;
    }
    assert(res == std::vector<int>({1, 1, 2, 3, 4, 4}));
    return 0;
}

22. Generate Parentheses

from typing import List


# Backtracking
def generateParenthesis1(n: int) -> List[str]:
    path, res = [], []

    def dfs(openN, closeN):
        if openN == closeN == n:
            res.append("".join(path))
            return

        if openN < n:
            path.append("(")
            dfs(openN + 1, closeN)
            path.pop()

        if closeN < openN:
            path.append(")")
            dfs(openN, closeN + 1)
            path.pop()

    dfs(0, 0)

    return res


# Backtracking
def generateParenthesis2(n: int) -> List[str]:
    m = n * 2
    res, path = [], [""] * m

    def dfs(i, left):
        if i == m:
            res.append("".join(path))
            return

        if left < n:
            path[i] = "("
            dfs(i + 1, left + 1)
        if i - left < left:
            path[i] = ")"
            dfs(i + 1, left)

    dfs(0, 0)
    return res


if __name__ == "__main__":
    print(generateParenthesis1(3))
    # ['((()))', '(()())', '(())()', '()(())', '()()()']
    print(generateParenthesis2(3))
    # ['((()))', '(()())', '(())()', '()(())', '()()()']

215. Kth Largest Element in an Array

  • LeetCode | 力扣

  • Tags: Array, Divide And Conquer, Sorting, Heap Priority Queue, Quickselect

import heapq
import random
from typing import List


class Solution:
    @staticmethod
    def _partition(nums: List[int], left: int, right: int) -> tuple[int, int]:
        """Split a range into values smaller than, equal to, and greater than pivot."""
        pivot = nums[(left + right) // 2]
        smaller = current = left
        greater = right

        while current <= greater:
            if nums[current] < pivot:
                nums[smaller], nums[current] = nums[current], nums[smaller]
                smaller += 1
                current += 1
            elif nums[current] > pivot:
                nums[current], nums[greater] = nums[greater], nums[current]
                greater -= 1
            else:
                current += 1

        return smaller, greater

    def sort(self, nums: List[int], k: int) -> int:
        """Built-in sort: O(n log n) time, O(n) space in Python."""
        nums.sort(reverse=True)
        return nums[k - 1]

    def findKthLargest(self, nums: List[int], k: int) -> int:
        """LeetCode entry point using randomized in-place quickselect."""
        return self.quick_select_in_place(nums, k)

    def min_heap(self, nums: List[int], k: int) -> int:
        """Min-heap: O(n log k) time, O(k) space."""
        min_heap = []

        for num in nums:
            heapq.heappush(min_heap, num)
            if len(min_heap) > k:
                heapq.heappop(min_heap)

        return min_heap[0]

    def quick_sort(self, nums: List[int], k: int) -> int:
        """In-place quicksort: O(n log n) average time, O(log n) average space."""
        ranges = [(0, len(nums) - 1)]

        while ranges:
            left, right = ranges.pop()
            if left >= right:
                continue

            equal_start, equal_end = self._partition(nums, left, right)
            left_range = (left, equal_start - 1)
            right_range = (equal_end + 1, right)

            # Process the smaller range first to keep the stack small.
            if left_range[1] - left_range[0] > right_range[1] - right_range[0]:
                left_range, right_range = right_range, left_range
            ranges.append(right_range)
            ranges.append(left_range)

        return nums[-k]

    def quick_select_recursive(self, nums: List[int], k: int) -> int:
        """
        Find the kth largest using recursive list partitions.

        k largest
        3, 2, 1, 5, 6, 4
        0  1  2  3  4  5

        Time: O(n) average, O(n^2) worst case.
        Space: O(n) average for partitions and recursion.
        """
        pivot = random.choice(nums)

        left = [number for number in nums if number > pivot]
        mid = [number for number in nums if number == pivot]
        right = [number for number in nums if number < pivot]

        if len(left) >= k:
            return self.quick_select_recursive(left, k)
        if len(left) + len(mid) >= k:
            return pivot
        return self.quick_select_recursive(right, k - len(left) - len(mid))

    def quick_select_in_place(self, nums: List[int], k: int) -> int:
        """
        Find the kth largest using randomized in-place quickselect.

        The kth largest is the (n - k)th smallest using a zero-based index.
        Time: O(n) average, O(n^2) worst case.
        Space: O(1), because partitioning is iterative and in place.
        """
        target = len(nums) - k

        def partition(left: int, right: int) -> int:
            pivot = random.randint(left, right)
            nums[pivot], nums[right] = nums[right], nums[pivot]
            pivot = nums[right]

            store = left
            for index in range(left, right):
                if nums[index] < pivot:
                    nums[index], nums[store] = nums[store], nums[index]
                    store += 1

            nums[store], nums[right] = nums[right], nums[store]
            return store

        left, right = 0, len(nums) - 1

        while left <= right:
            pivot_index = partition(left, right)
            if pivot_index == target:
                return nums[pivot_index]
            if pivot_index < target:
                left = pivot_index + 1
            else:
                right = pivot_index - 1

        raise RuntimeError("quickselect failed to find the target")


if __name__ == "__main__":
    solution = Solution()
    methods = (
        solution.findKthLargest,
        solution.sort,
        solution.min_heap,
        solution.quick_sort,
        solution.quick_select_recursive,
        solution.quick_select_in_place,
    )
    cases = (
        ([3, 2, 1, 5, 6, 4], 2, 5),
        ([3, 2, 3, 1, 2, 4, 5, 5, 6], 4, 4),
        ([-1, -1], 2, -1),
        ([1], 1, 1),
    )

    for method in methods:
        for nums, k, expected in cases:
            assert method(nums.copy(), k) == expected

283. Move Zeroes

from typing import List


class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """Two Pointers: O(n) time, O(1) space.
        Swap non-zero elements to the front, zeroes drift to end.
        """
        slow = 0
        n = len(nums)

        for fast in range(n):
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1


def test_move_zeroes():
    s = Solution()
    for fn in (s.moveZeroes,):
        nums = [0, 1, 0, 3, 12]
        fn(nums)
        assert nums == [1, 3, 12, 0, 0]

        nums = [0]
        fn(nums)
        assert nums == [0]

        nums = [1, 2, 3]
        fn(nums)
        assert nums == [1, 2, 3]

        nums = [0, 0, 0, 0, 1]
        fn(nums)
        assert nums == [1, 0, 0, 0, 0]

#include <iostream>
#include <vector>
using namespace std;

void moveZeroes(vector<int>& nums) {
    size_t n = nums.size();
    size_t fast = 0, slow = 0;

    while (fast < n) {
        if (nums[fast] != 0) {
            swap(nums[slow], nums[fast]);
            slow++;
        }
        fast++;
    }
}

int main() {
    vector<int> nums = {0, 1, 0, 3, 12};
    moveZeroes(nums);
    // [1, 3, 12, 0, 0]
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}

1757. Recyclable and Low Fat Products

SELECT product_id
FROM
    products
WHERE
    low_fats = 'Y'
    AND recyclable = 'Y';

Input:
Products table:
+-------------+----------+------------+
| product_id  | low_fats | recyclable |
+-------------+----------+------------+
| 0           | Y        | N          |
| 1           | Y        | Y          |
| 2           | N        | Y          |
| 3           | Y        | Y          |
| 4           | N        | N          |
+-------------+----------+------------+
Output:
+-------------+
| product_id  |
+-------------+
| 1           |
| 3           |
+-------------+

287. Find the Duplicate Number

  • LeetCode | 力扣

  • Tags: Array, Two Pointers, Binary Search, Bit Manipulation

"""
-   Find the duplicate number in an array containing `n + 1` integers where each integer is between `1` and `n` inclusive.
-   Floyd's Tortoise and Hare (Cycle Detection)
    -   141. Linked List Cycle
    -   142. Linked List Cycle II
-   Time Complexity: O(n)
-   Space Complexity: O(1)

Example: `nums = [1, 3, 4, 2, 2]`

|  0   |  1   |  2   |  3   |  4   |
| :--: | :--: | :--: | :--: | :--: |
|  1   |  3   |  4   |  2   |  2   |


"""

from typing import List


# Floyd Cycle Detection Algorithm
def findDuplicate(nums: List[int]) -> int:
    fast, slow = nums[0], nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow


nums = [1, 3, 4, 2, 2]
print(findDuplicate(nums))  # 2

6. Zigzag Conversion

485. Max Consecutive Ones

28. Find the Index of the First Occurrence in a String

from leetpattern.utils import LPS


# Brute Force
def strStrBF(haystack: str, needle: str) -> int:
    m, n = len(haystack), len(needle)
    for i in range(m - n + 1):
        if haystack[i : i + n] == needle:
            return i
    return -1


# KMP
def strStrKMP(haystack: str, needle: str) -> int:
    lps = LPS(needle)
    m, n = len(haystack), len(needle)
    j = 0

    for i in range(m):
        while j > 0 and haystack[i] != needle[j]:
            j = lps[j - 1]
        if haystack[i] == needle[j]:
            j += 1
        if j == n:
            return i - n + 1
    return -1


# |------------|------------------|---------|
# |  Approach  |       Time       |  Space  |
# |------------|------------------|---------|
# | Brute Force| O((m - n) * n)   | O(1)    |
# | KMP        | O(m + n)         | O(n)    |
# |------------|------------------|---------|


haystack = "hello"
needle = "ll"
print(strStrBF(haystack, needle))  # 2
print(strStrKMP(haystack, needle))  # 2

496. Next Greater Element I

from typing import List


# Monotonic Stack
def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
    next_greater = {}
    stack = []
    result = []

    for num in nums2:
        while stack and num > stack[-1]:
            next_greater[stack.pop()] = num
        stack.append(num)

    for num in nums1:
        result.append(next_greater.get(num, -1))

    return result


nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
print(nextGreaterElement(nums1, nums2))  # [3, -1, -1]

240. Search a 2D Matrix II

  • LeetCode | 力扣

  • Tags: Array, Binary Search, Divide And Conquer, Matrix

from typing import List


# Matrix
def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
    i, j = 0, n - 1

    while i < m and j >= 0:
        if matrix[i][j] == target:
            return True
        elif matrix[i][j] < target:
            i += 1
        else:
            j -= 1

    return False


matrix = [
    [1, 4, 7, 11, 15],
    [2, 5, 8, 12, 19],
    [3, 6, 9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30],
]
target = 20
print(searchMatrix(matrix, target))  # False

1004. Max Consecutive Ones III

  • LeetCode | 力扣

  • Tags: Array, Binary Search, Sliding Window, Prefix Sum

from typing import List


# Sliding Window - Variable
def longestOnes(nums: List[int], k: int) -> int:
    left = 0
    maxLen = 0
    zero_count = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1

        while zero_count > k:
            if nums[left] == 0:
                zero_count -= 1
            left += 1

        maxLen = max(maxLen, right - left + 1)

    return maxLen


nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]
k = 2
print(longestOnes(nums, k))  # 6

1011. Capacity To Ship Packages Within D Days

"""
-   A conveyor belt has packages that must be shipped from one port to another within `D` days. The `i-th` package has a weight of `weights[i]`. Each day, we load the ship with packages on the conveyor belt. The ship will be loaded with packages up to its capacity. The ship will not be loaded beyond its capacity. Return the least weight capacity of the ship.
"""

from typing import List


# Binary Search
def shipWithinDays(weights: List[int], days: int) -> int:

    def canShip(weights, D, capacity):
        days = 1
        current_weight = 0

        for weight in weights:
            if current_weight + weight > capacity:
                days += 1
                current_weight = 0
            current_weight += weight

        return days <= D

    left, right = max(weights), sum(weights)

    while left <= right:
        mid = left + (right - left) // 2

        if canShip(weights, days, mid):
            right = mid - 1
        else:
            left = mid + 1

    return left


weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
days = 5
print(shipWithinDays(weights, days))  # 15

394. Decode String

# Stack
def decodeString(s: str) -> str:
    stack = []  # (str, int)
    num = 0
    res = ""

    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c == "[":
            stack.append((res, num))
            res, num = "", 0
        elif c == "]":
            top = stack.pop()
            res = top[0] + res * top[1]
        else:
            res += c

    return res


s = "3[a2[c]]"
print(decodeString(s))  # accaccacc

977. Squares of a Sorted Array

from typing import List


# Left Right Pointers
def sortedSquares(nums: List[int]) -> List[int]:
    """Returns the squares of the sorted array."""
    n = len(nums)
    result = [0 for _ in range(n)]

    left, right, tail = 0, n - 1, n - 1

    while left <= right:
        if abs(nums[left]) >= abs(nums[right]):
            result[tail] = nums[left] ** 2
            left += 1
        else:
            result[tail] = nums[right] ** 2
            right -= 1
        tail -= 1

    return result


# |---------------------|------|-------|
# | Approach            | Time | Space |
# |---------------------|------|-------|
# | Left Right Pointers | O(n) | O(n)  |
# |---------------------|------|-------|


nums = [-4, -1, 0, 3, 10]
print(sortedSquares(nums))  # [0, 1, 9, 16, 100]

210. Course Schedule II

  • LeetCode | 力扣

  • Tags: Depth First Search, Breadth First Search, Graph, Topological Sort

"""
- Return the ordering of courses you should take to finish all courses. If there are multiple valid answers, return any of them.

![0207](../../assets/0207.png)
"""

from collections import defaultdict, deque
from typing import List


# 1. BFS - Kahn's Algorithm
def findOrderBFS(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    graph = defaultdict(list)
    indegree = defaultdict(int)

    for crs, pre in prerequisites:
        graph[pre].append(crs)
        indegree[crs] += 1

    q = deque([i for i in range(numCourses) if indegree[i] == 0])
    order = []

    while q:
        pre = q.popleft()
        order.append(pre)

        for crs in graph[pre]:
            indegree[crs] -= 1
            if indegree[crs] == 0:
                q.append(crs)

    return order if len(order) == numCourses else []


# 2. DFS + Set
def findOrderDFS1(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    adj = defaultdict(list)
    for crs, pre in prerequisites:
        adj[crs].append(pre)

    visit, cycle = set(), set()
    order = []

    def dfs(crs):
        if crs in cycle:
            return False
        if crs in visit:
            return True

        cycle.add(crs)
        for pre in adj[crs]:
            if not dfs(pre):
                return False

        cycle.remove(crs)
        visit.add(crs)
        order.append(crs)
        return True

    for crs in range(numCourses):
        if not dfs(crs):
            return []

    return order


# 3. DFS + List
def findOrderDFS2(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    adj = defaultdict(list)
    for pre, crs in prerequisites:
        adj[crs].append(pre)

    # 0: not visited, 1: visiting, 2: visited
    state = [0] * numCourses
    order = []

    def dfs(crs):
        if state[crs] == 1:
            return False
        if state[crs] == 2:
            return True

        state[crs] = 1

        for pre in adj[crs]:
            if not dfs(pre):
                return False

        state[crs] = 2
        order.append(crs)
        return True

    for crs in range(numCourses):
        if not dfs(crs):
            return []

    return order[::-1]


numCourses = 5
prerequisites = [[0, 1], [0, 2], [1, 3], [1, 4], [3, 4]]
print(findOrderBFS(numCourses, prerequisites))  # [2, 4, 3, 1, 0]
print(findOrderDFS1(numCourses, prerequisites))  # [4, 3, 1, 2, 0]
print(findOrderDFS2(numCourses, prerequisites))  # [4, 3, 2, 1, 0]

#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class Solution {
   public:
    // BFS
    vector<int> findOrderBFS(int numCourses,
                             vector<vector<int>> &prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> in_degree(numCourses, 0);
        vector<int> res;

        for (auto &pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
            in_degree[pre[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++)
            if (in_degree[i] == 0) q.push(i);

        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            res.push_back(cur);

            for (int next : graph[cur]) {
                in_degree[next]--;
                if (in_degree[next] == 0) q.push(next);
            }
        }

        return (int)res.size() == numCourses ? res : vector<int>{};
    }
};

int main() {
    Solution obj;
    vector<vector<int>> prerequisites{{1, 0}, {2, 0}, {3, 1}, {3, 2}};
    vector<int> res = obj.findOrderBFS(4, prerequisites);
    assert((res == vector<int>{0, 1, 2, 3} || res == vector<int>{0, 2, 1, 3}));
    return 0;
}

97. Interleaving String

# DP - 2D
def isInterleaveDP(s1: str, s2: str, s3: str) -> bool:
    m, n, k = len(s1), len(s2), len(s3)

    if m + n != k:
        return False

    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    for i in range(1, m + 1):
        dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]

    for j in range(1, n + 1):
        dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or (
                dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
            )

    return dp[m][n]


# DFS
def isInterleaveDFS(s1: str, s2: str, s3: str) -> bool:
    memo = {}

    def dfs(i, j, k):
        if i == len(s1) and j == len(s2) and k == len(s3):
            return True

        if (i, j) in memo:
            return memo[(i, j)]

        res = False

        if i < len(s1) and k < len(s3) and s1[i] == s3[k]:
            res |= dfs(i + 1, j, k + 1)

        if j < len(s2) and k < len(s3) and s2[j] == s3[k]:
            res |= dfs(i, j + 1, k + 1)

        memo[(i, j)] = res

        return res

    return dfs(0, 0, 0)


s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"
print(isInterleaveDP(s1, s2, s3))  # False
print(isInterleaveDFS(s1, s2, s3))  # False

10. Regular Expression Matching

205. Isomorphic Strings

#include <cassert>
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
   public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) return false;

        unordered_map<char, char> map_s2t;
        unordered_map<char, char> map_t2s;

        for (size_t i = 0; i < s.size(); i++) {
            char a = s[i];
            char b = t[i];

            if (map_s2t.count(a) && map_s2t[a] != b) return false;
            if (map_t2s.count(b) && map_t2s[b] != a) return false;

            map_s2t[a] = b;
            map_t2s[b] = a;
        }
        return true;
    }
};

int main() {
    Solution sol;
    assert(sol.isIsomorphic("egg", "add") == true);
    return 0;
}

152. Maximum Product Subarray

from typing import List


# DP - Kadane
def maxProduct(nums: List[int]) -> int:
    n = len(nums)
    dp_max = [0 for _ in range(n)]
    dp_min = [0 for _ in range(n)]

    dp_max[0] = nums[0]
    dp_min[0] = nums[0]
    max_product = nums[0]

    for i in range(1, n):
        dp_max[i] = max(
            nums[i],
            nums[i] * dp_max[i - 1],
            nums[i] * dp_min[i - 1],
        )
        dp_min[i] = min(
            nums[i],
            nums[i] * dp_max[i - 1],
            nums[i] * dp_min[i - 1],
        )

        max_product = max(max_product, dp_max[i])

    return max_product


nums = [2, 3, -2, 4]
print(maxProduct(nums))  # 6

153. Find Minimum in Rotated Sorted Array

from typing import List


# Binary Search
def findMin(nums: List[int]) -> int:
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    return nums[right]


nums = [4, 5, 6, 7, 0, 1, 2]
print(findMin(nums))  # 0

2196. Create Binary Tree From Descriptions

881. Boats to Save People

from typing import List


# Left Right Pointers
def numRescueBoats(people: List[int], limit: int) -> int:
    """Returns the minimum number of boats to rescue people."""
    people.sort()
    left, right = 0, len(people) - 1
    boats = 0

    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        boats += 1

    return boats


people = [3, 2, 2, 1]
limit = 3
print(numRescueBoats(people, limit))  # 3

45. Jump Game II

"""
- Return the minimum number of jumps to reach the last index.
"""

from typing import List


# Greedy - Interval
def jump(nums: List[int]) -> int:
    n = len(nums)
    if n == 1:
        return 0

    reach = 0
    left, right = 0, 0
    res = 0

    while right < n - 1:
        for i in range(left, right + 1):
            reach = max(reach, i + nums[i])

        left = right + 1
        right = reach
        res += 1

    return res


if __name__ == "__main__":
    assert jump([2, 3, 1, 1, 4]) == 2
    assert jump([2, 3, 0, 1, 4]) == 2

  • LeetCode | 力扣

  • Tags: Array, String, Backtracking, Depth First Search, Matrix

from typing import List


def exist(board: List[List[str]], word: str) -> bool:
    m, n = len(board), len(board[0])
    path = set()
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))

    def dfs(r, c, i):
        if i == len(word):
            return True

        if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[i] or (r, c) in path:
            return False

        path.add((r, c))

        for dr, dc in dirs:
            if dfs(r + dr, c + dc, i + 1):
                return True

        path.remove((r, c))
        return False

    for i in range(m):
        for j in range(n):
            if dfs(i, j, 0):
                return True

    return False


board = [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"],
]
word = "ABCCED"
print(exist(board, word))  # True

127. Word Ladder

"""
-   The most classic BFS problem.
-   Return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
-   Approach: BFS
-   Time Complexity: O(n * m^2)
-   Space Complexity: O(n * m)
"""

from collections import defaultdict, deque
from typing import List


# BFS
def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
    if endWord not in wordList:
        return 0

    n = len(beginWord)
    graph = defaultdict(list)  # pattern: words
    wordList.append(beginWord)

    for word in wordList:
        for i in range(n):
            pattern = word[:i] + "*" + word[i + 1 :]
            graph[pattern].append(word)

    visited = set([beginWord])
    q = deque([beginWord])
    res = 1

    while q:
        size = len(q)
        for _ in range(size):
            word = q.popleft()
            if word == endWord:
                return res

            for i in range(n):
                pattern = word[:i] + "*" + word[i + 1 :]
                for neighbor in graph[pattern]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        q.append(neighbor)
        res += 1

    return 0


beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
print(ladderLength(beginWord, endWord, wordList))  # 5

295. Find Median from Data Stream

  • LeetCode | 力扣

  • Tags: Two Pointers, Design, Sorting, Heap Priority Queue, Data Stream

from heapq import heappop, heappush


class MedianFinder:

    def __init__(self):
        self.minHeap = []
        self.maxHeap = []
        self.min_size = 0
        self.max_size = 0

    def addNum(self, num: int) -> None:
        heappush(self.maxHeap, -num)
        heappush(self.minHeap, -heappop(self.maxHeap))
        self.min_size += 1

        if self.min_size > self.max_size:
            heappush(self.maxHeap, -heappop(self.minHeap))
            self.min_size -= 1
            self.max_size += 1

    def findMedian(self) -> float:
        if self.min_size == self.max_size:
            return (-self.maxHeap[0] + self.minHeap[0]) / 2.0
        return float(-self.maxHeap[0])


def test_median_finder():
    obj = MedianFinder()
    obj.addNum(1)
    obj.addNum(2)
    assert obj.findMedian() == 1.5
    obj.addNum(3)
    assert obj.findMedian() == 2.0
    obj.addNum(4)
    assert obj.findMedian() == 2.5
    obj.addNum(5)
    assert obj.findMedian() == 3.0

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class MedianFinder {
   private:
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int max_size = 0;
    int min_size = 0;

   public:
    MedianFinder() {}

    void addNum(int num) {
        if (min_size == max_size) {
            minHeap.push(num);
            maxHeap.push(minHeap.top());
            minHeap.pop();
            max_size++;
        } else {
            maxHeap.push(num);
            minHeap.push(maxHeap.top());
            maxHeap.pop();
            min_size++;
        }
    }

    double findMedian() {
        if (min_size == max_size) {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        } else {
            return (double)maxHeap.top();
        }
    }
};

int main() {
    MedianFinder* obj = new MedianFinder();
    obj->addNum(1);
    obj->addNum(2);
    cout << obj->findMedian() << endl;  // 1.5
    obj->addNum(3);
    cout << obj->findMedian() << endl;  // 2
    return 0;
}

387. First Unique Character in a String

217. Contains Duplicate

from typing import List


class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        """Set: O(n) time, O(n) space.
        Track seen elements; return True on first repeat.
        """
        seen = set()
        for n in nums:
            if n in seen:
                return True
            seen.add(n)
        return False

    def containsDuplicateSort(self, nums: List[int]) -> bool:
        """Sort: O(n log n) time, O(1) space.
        Duplicates become adjacent after sorting.
        """
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

    def containsDuplicateBF(self, nums: List[int]) -> bool:
        """Brute Force: O(n^2) time, O(1) space.
        Compare every pair.
        """
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False


def test_contains_duplicate():
    s = Solution()
    for fn in (s.containsDuplicate, s.containsDuplicateSort, s.containsDuplicateBF):
        assert fn([1, 2, 3, 1]) is True
        assert fn([1, 2, 3, 4]) is False
        assert fn([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]) is True
        assert fn([]) is False

74. Search a 2D Matrix

from typing import List


# Binary Search
def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    if not matrix or not matrix[0]:
        return False

    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1

    while left <= right:
        mid = left + (right - left) // 2
        x = matrix[mid // n][mid % n]

        if x < target:
            left = mid + 1
        elif x > target:
            right = mid - 1
        else:
            return True

    return False


if __name__ == "__main__":
    matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
    target = 3
    print(searchMatrix(matrix, target))  # True

344. Reverse String

from typing import List


def reverseString(s: List[str]) -> None:
    """
    Do not return anything, modify s in-place instead.
    """
    left, right = 0, len(s) - 1

    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1


s = ["h", "e", "l", "l", "o"]
reverseString(s)
print(s)  # ['o', 'l', 'l', 'e', 'h']

#include <cassert>
#include <vector>
using namespace std;

class Solution {
   public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            swap(s[left], s[right]);

            left++;
            right--;
        }
    }
};

int main() {
    Solution solution;
    vector<char> s = {'h', 'e', 'l', 'l', 'o'};
    solution.reverseString(s);
    assert(s == vector<char>({'o', 'l', 'l', 'e', 'h'}));
    return 0;
}

300. Longest Increasing Subsequence

from functools import cache
from typing import List


# DP - LIS
def lengthOfLISMemo(nums: List[int]) -> int:
    n = len(nums)
    if n <= 1:
        return n

    @cache
    def dfs(i: int) -> int:
        res = 0
        for j in range(i):
            if nums[j] < nums[i]:
                res = max(res, dfs(j))
        return res + 1

    return max(dfs(i) for i in range(n))


# DP - LIS
def lengthOfLISTable(nums: List[int]) -> int:
    n = len(nums)
    if n <= 1:
        return n

    dp = [1 for _ in range(n)]

    for i in range(n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)


if __name__ == "__main__":
    assert lengthOfLISMemo([10, 9, 2, 5, 3, 7, 101, 18]) == 4
    assert lengthOfLISTable([10, 9, 2, 5, 3, 7, 101, 18]) == 4
    assert lengthOfLISMemo([0, 1, 0, 3, 2, 3]) == 4
    assert lengthOfLISTable([0, 1, 0, 3, 2, 3]) == 4
    assert lengthOfLISMemo([7, 7, 7, 7]) == 1
    assert lengthOfLISTable([7, 7, 7, 7]) == 1

435. Non-overlapping Intervals

from typing import List


def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    if len(intervals) <= 1:
        return 0

    intervals.sort(key=lambda x: x[0])
    result = 0

    for i in range(1, len(intervals)):
        if intervals[i][0] >= intervals[i - 1][1]:
            continue
        else:
            result += 1
            intervals[i][1] = min(intervals[i][1], intervals[i - 1][1])

    return result


print(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]))  # 1

100. Same Tree

  • LeetCode | 力扣

  • Tags: Tree, Depth First Search, Breadth First Search, Binary Tree

from collections import deque
from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


# 1. Recursive
def isSameTreeRecursive(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if not p and not q:
        return True
    elif not p or not q:
        return False
    elif p.val != q.val:
        return False

    return isSameTreeRecursive(p.left, q.left) and isSameTreeRecursive(p.right, q.right)


# 2. Iterative with queue
def isSameTreeIterativeQueue(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    queue = deque([(p, q)])

    while queue:
        p, q = queue.popleft()

        if not p and not q:
            continue
        if not p or not q:
            return False
        if p.val != q.val:
            return False

        queue.append((p.left, q.left))
        queue.append((p.right, q.right))

    return True


# 3. Iterative with stack
def isSameTreeIterativeStack(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    stack = [(p, q)]

    while stack:
        n1, n2 = stack.pop()

        if not n1 and not n2:
            continue
        if not n1 or not n2:
            return False
        if n1.val != n2.val:
            return False

        stack.append((n1.left, n2.left))
        stack.append((n1.right, n2.right))

    return True


if __name__ == "__main__":
    p1 = build([1, 2, 3])
    q1 = build([1, 2, 3])
    p2 = build([1, 2])
    q2 = build([1, None, 2])

    assert isSameTreeRecursive(p1, q1) is True
    assert isSameTreeRecursive(p2, q2) is False
    assert isSameTreeIterativeQueue(p1, q1) is True
    assert isSameTreeIterativeQueue(p2, q2) is False
    assert isSameTreeIterativeStack(p1, q1) is True
    assert isSameTreeIterativeStack(p2, q2) is False

212. Word Search II

from typing import List

from leetpattern.utils import Trie


# Backtracking + Trie
def findWords(board: List[List[str]], words: List[str]) -> List[str]:
    trie = Trie()
    for word in words:
        trie.add_word(word)

    m, n = len(board), len(board[0])
    result, visit = set(), set()

    def dfs(r, c, node, word):
        if (
            r < 0
            or r >= m
            or c < 0
            or c >= n
            or (r, c) in visit
            or board[r][c] not in node.children
        ):
            return None

        visit.add((r, c))

        node = node.children[board[r][c]]
        word += board[r][c]
        if node.is_word:
            result.add(word)

        dfs(r - 1, c, node, word)
        dfs(r + 1, c, node, word)
        dfs(r, c - 1, node, word)
        dfs(r, c + 1, node, word)

        visit.remove((r, c))

    for r in range(m):
        for c in range(n):
            dfs(r, c, trie.root, "")

    return list(result)


def test_find_words():
    board = [
        ["o", "a", "a", "n"],
        ["e", "t", "a", "e"],
        ["i", "h", "k", "r"],
        ["i", "f", "l", "v"],
    ]
    words = ["oath", "pea", "eat", "rain"]
    result = findWords(board, words)
    assert sorted(result) == ["eat", "oath"]

103. Binary Tree Zigzag Level Order Traversal

from collections import deque
from typing import List, Optional

from binarytree import Node as TreeNode
from binarytree import build


def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []

    q = deque([root])
    res = []

    while q:
        level = []
        size = len(q)

        for _ in range(size):
            cur = q.popleft()
            level.append(cur.val)

            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)

        res.append(level if not len(res) % 2 else level[::-1])

    return res


if __name__ == "__main__":
    tree = build([3, 9, 20, None, None, 15, 7])
    print(tree)
    #   3___
    #  /    \
    # 9     _20
    #      /   \
    #     15    7
    assert zigzagLevelOrder(tree) == [[3], [20, 9], [15, 7]]

"""
- Implement binary search algorithm.
"""

from typing import List


# Binary Search [left, right]
def search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            return mid

    return -1


# Binary Search [left, right)
def search_half_open(nums: List[int], target: int) -> int:
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid
        else:
            return mid

    return -1


# Binary Search (left, right)
def search_open_interval(nums: List[int], target: int) -> int:
    left, right = -1, len(nums)

    while left + 1 < right:
        mid = left + (right - left) // 2

        if nums[mid] < target:
            left = mid
        elif nums[mid] > target:
            right = mid
        else:
            return mid

    return -1


if __name__ == "__main__":
    nums = [-1, 0, 3, 5, 9, 12]
    target = 9
    assert search(nums, target) == 4
    assert search_half_open(nums, target) == 4
    assert search_open_interval(nums, target) == 4

25. Reverse Nodes in k-Group

from typing import Optional

from leetpattern.utils import ListNode, list_from_array, list_to_array


# Linked List
def reverse_k_group(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    n = 0
    cur = head
    while cur:
        n += 1
        cur = cur.next

    p0 = dummy = ListNode(next=head)
    pre = None
    cur = head

    while n >= k:
        n -= k
        for _ in range(k):
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt

        nxt = p0.next
        nxt.next = cur
        p0.next = pre
        p0 = nxt

    return dummy.next


def test_reverse_k_group():
    head = list_from_array([1, 2, 3, 4, 5])
    assert list_to_array(reverse_k_group(head, 2)) == [2, 1, 4, 3, 5]

1280. Students and Examinations

SELECT
    st.student_id,
    st.student_name,
    su.subject_name,
    COUNT(ex.student_id) AS attended_exams
FROM
    students AS st
CROSS JOIN subjects AS su
LEFT JOIN examinations AS ex
    ON
        st.student_id = ex.student_id
        AND su.subject_name = ex.subject_name
GROUP BY
    st.student_id,
    st.student_name,
    su.subject_name
ORDER BY
    st.student_id,
    su.subject_name;

396. Rotate Function

1665. Minimum Initial Energy to Finish Tasks

73. Set Matrix Zeroes

from copy import deepcopy
from typing import List


class setZeroes:
    @staticmethod
    def matrix(matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # prep
        m, n = len(matrix), len(matrix[0])
        rows, cols = set(), set()

        # collect rows and cols
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)

        # work on rows and cols
        for i in rows:
            for j in range(n):
                matrix[i][j] = 0

        for i in range(m):
            for j in cols:
                matrix[i][j] = 0


if __name__ == "__main__":
    matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
    setZeroes.matrix(matrix)
    assert matrix == [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

752. Open the Lock

  • LeetCode | 力扣

  • Tags: Array, Hash Table, String, Breadth First Search

1833. Maximum Ice Cream Bars

69. Sqrt(x)

# Left Right Pointers
def mySqrt(x: int) -> int:
    """Returns the square root of a number."""
    if x < 2:
        return x

    left, right = 0, x // 2

    while left <= right:
        mid = left + (right - left) // 2
        if mid * mid <= x < (mid + 1) * (mid + 1):
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid - 1


x = 8
print(mySqrt(x))  # 2

#include <cassert>
using namespace std;

class Solution {
   public:
    int mySqrt(int x) {
        if (x < 2) return x;
        int left = 0, right = x / 2;
        int mid = 0;

        while (left <= right) {
            mid = left + (right - left) / 2;
            long long a = 1LL * mid * mid;
            long long b = 1LL * (mid + 1) * (mid + 1);

            if (a <= x && x < b) {
                return mid;
            } else if (a < x)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return right;
    }
};

int main() {
    Solution solution;
    assert(solution.mySqrt(4) == 2);
    assert(solution.mySqrt(8) == 2);
    assert(solution.mySqrt(1999) == 44);
    return 0;
}

118. Pascal's Triangle

"""
-   Generate the first `numRows` of Pascal's triangle.

```plaintext
                 numRows
     1              1
    1 1             2
   1 2 1            3
  1 3 3 1           4
 1 4 6 4 1          5
"""

from typing import List

def generate(numRows: int) -> List[List[int]]: dp = [[1] * i for i in range(1, numRows + 1)]

if numRows <= 2:
    return dp

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

return dp

if name == "main": print(generate(numRows=5)) # [[1], # [1, 1], # [1, 2, 1], # [1, 3, 3, 1], # [1, 4, 6, 4, 1]]

```

503. Next Greater Element II

from typing import List


# Monotonic Stack
def nextGreaterElements(nums: List[int]) -> List[int]:
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(2 * n):
        while stack and nums[stack[-1]] < nums[i % n]:
            result[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)

    return result


nums = [1, 2, 1]
print(nextGreaterElements(nums))  # [2, -1, 2]

41. First Missing Positive

from typing import List


# In-place Hashing
def firstMissingPositive(nums: List[int]) -> int:
    n = len(nums)

    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    return n + 1


if __name__ == "__main__":
    nums = [3, 4, -1, 1]
    print(firstMissingPositive(nums))  # 2

328. Odd Even Linked List

51. N-Queens

"""
- Hard
- [N-Queens](https://leetcode.com/problems/n-queens/)
- [N 皇后](https://leetcode.cn/problems/n-queens/)
"""

from typing import List


# Backtracking
def solveNQueens(n: int) -> List[List[str]]:
    res = []
    board = ["." * n for _ in range(n)]

    def dfs(row):
        if row == n:
            res.append(board[:])
            return None
        for col in range(n):
            if is_valid(row, col, board):
                board[row] = board[row][:col] + "Q" + board[row][col + 1 :]
                dfs(row + 1)
                board[row] = board[row][:col] + "." + board[row][col + 1 :]

    def is_valid(row, col, chessboard):
        for i in range(row):
            if chessboard[i][col] == "Q":
                return False

        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if chessboard[i][j] == "Q":
                return False
            i -= 1
            j -= 1

        i, j = row - 1, col + 1
        while i >= 0 and j < len(chessboard):
            if chessboard[i][j] == "Q":
                return False
            i -= 1
            j += 1

        return True

    dfs(0)

    return [["".join(row) for row in i] for i in res]


# Backtracking
def solveNQueens2(n: int) -> List[List[str]]:
    res = []
    queens = [0] * n
    col = [False] * n
    diag1 = [False] * (n * 2 - 1)
    diag2 = [False] * (n * 2 - 1)

    def dfs(r: int) -> None:
        if r == n:
            res.append(["." * c + "Q" + "." * (n - 1 - c) for c in queens])
            return

        for c, ok in enumerate(col):
            if not ok and not diag1[r + c] and not diag2[r - c]:
                queens[r] = c
                col[c] = diag1[r + c] = diag2[r - c] = True
                dfs(r + 1)
                col[c] = diag1[r + c] = diag2[r - c] = False

    dfs(0)

    return res


if __name__ == "__main__":
    print(solveNQueens(4))
    # [['.Q..', '...Q', 'Q...', '..Q.'],
    #  ['..Q.', 'Q...', '...Q', '.Q..']]
    print(solveNQueens(1))
    # [['Q']]
    print(solveNQueens2(4))
    # [['.Q..', '...Q', 'Q...', '..Q.'],
    #  ['..Q.', 'Q...', '...Q', '.Q..']]
    print(solveNQueens2(1))
    # [['Q']]

540. Single Element in a Sorted Array

179. Largest Number

from functools import cmp_to_key
from typing import List


# Greedy
def largestNumber(nums: List[int]) -> str:
    strs = map(str, nums)

    def cmp(a, b):
        if a + b == b + a:
            return 0
        elif a + b > b + a:
            return 1
        else:
            return -1

    strs = sorted(strs, key=cmp_to_key(cmp), reverse=True)

    return "".join(strs) if strs[0] != "0" else "0"


nums = [3, 30, 34, 5, 9]
print(largestNumber(nums))  # 9534330

416. Partition Equal Subset Sum

from functools import cache
from typing import List

from leetpattern.utils import knapsack01


# Memoization
def canPartitionMemoization(nums: List[int]) -> bool:
    total = sum(nums)
    n = len(nums)

    if total % 2 == 1 or n <= 1:
        return False

    @cache
    def dfs(i, j):
        if i < 0:
            return j == 0
        return j >= nums[i] and dfs(i - 1, j - nums[i]) or dfs(i - 1, j)

    return dfs(n - 1, total // 2)


# DP - Knapsack 01
def canPartitionTemplate(nums: List[int]) -> bool:
    total = sum(nums)

    if total % 2 == 1 or len(nums) < 2:
        return False

    target = total // 2

    return knapsack01(nums, nums, target) == target


# DP - Knapsack 01
def canPartition(nums: List[int]) -> bool:
    total = sum(nums)

    if total % 2 == 1 or len(nums) < 2:
        return False

    target = total // 2

    dp = [0 for _ in range(target + 1)]

    for i in range(len(nums)):
        for j in range(target, nums[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

    return dp[target] == target


if __name__ == "__main__":
    nums = [1, 5, 11, 5]
    print(canPartitionTemplate(nums))  # True
    print(canPartition(nums))  # True
    print(canPartitionMemoization(nums))  # True

139. Word Break

  • LeetCode | 力扣

  • Tags: Array, Hash Table, String, Dynamic Programming, Trie, Memoization

from typing import List


# DP (Unbounded Knapsack)
def wordBreak(s: str, wordDict: List[str]) -> bool:
    n = len(s)
    dp = [False for _ in range(n + 1)]
    dp[0] = True

    for i in range(1, n + 1):
        for word in wordDict:
            m = len(word)
            if s[i - m : i] == word and dp[i - m]:
                dp[i] = True
    return dp[-1]


s = "leetcode"
wordDict = ["leet", "code"]
print(wordBreak(s, wordDict))  # True

#include <algorithm>
#include <cassert>
#include <ranges>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
   public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int max_len = ranges::max(wordDict, {}, &string::length).length();
        unordered_set<string> words(wordDict.begin(), wordDict.end());

        int n = s.length();
        vector<int> f(n + 1);
        f[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i - 1; j >= max(i - max_len, 0); j--) {
                if (f[j] && words.count(s.substr(j, i - j))) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n];
    }
};

int main() {
    Solution solution;
    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};
    assert(solution.wordBreak(s, wordDict) == true);
    return 0;
}

7. Reverse Integer

# Math
def reverse(x: int) -> int:
    INT_MAX = 2**31 - 1

    sign = -1 if x < 0 else 1
    x = abs(x)
    res = 0

    while x != 0:
        x, pop = divmod(x, 10)

        if res > (INT_MAX - pop) // 10:
            return 0

        res = res * 10 + pop

    return res * sign


print(reverse(123))  # 321
print(reverse(-123))  # -321

204. Count Primes

12. Integer to Roman

def intToRoman(num: int) -> str:
    mapping = {
        1000: "M",
        900: "CM",
        500: "D",
        400: "CD",
        100: "C",
        90: "XC",
        50: "L",
        40: "XL",
        10: "X",
        9: "IX",
        5: "V",
        4: "IV",
        1: "I",
    }

    res = ""
    for val, symbol in mapping.items():
        count = num // val
        if count:
            res += symbol * count
            num -= val * count

    return res

122. Best Time to Buy and Sell Stock II

"""
-   Return the maximum profit you can achieve.
"""

from typing import List


# DP
def maxProfitDP1(prices: List[int]) -> int:
    n = len(prices)
    if n <= 1:
        return 0

    dp = [[0] * 2 for _ in range(n)]
    dp[0][0] = -prices[0]
    dp[0][1] = 0

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

    return dp[-1][1]


# DP - Optimized
def maxProfitDP2(prices: List[int]) -> int:
    n = len(prices)
    if n <= 1:
        return 0

    hold = -prices[0]
    profit = 0

    for i in range(1, n):
        hold = max(hold, profit - prices[i])
        profit = max(profit, hold + prices[i])

    return profit


# Greedy
def maxProfitGreedy(prices: List[int]) -> int:
    profit = 0

    for i in range(1, len(prices)):
        profit += max(prices[i] - prices[i - 1], 0)

    return profit


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# |     DP1    |  O(n)  |   O(n)  |
# |     DP2    |  O(n)  |   O(1)  |
# |   Greedy   |  O(n)  |   O(1)  |
# |------------|--------|---------|


prices = [7, 1, 5, 3, 6, 4]
print(maxProfitDP1(prices))  # 7
print(maxProfitDP2(prices))  # 7
print(maxProfitGreedy(prices))  # 7

#include <array>
#include <cassert>
#include <climits>
#include <vector>
using namespace std;

class Solution {
   public:
    int maxProfitMemo(vector<int>& prices) {
        int n = prices.size();
        vector<array<int, 2>> memo(n, {-1, -1});

        auto dfs = [&](this auto&& dfs, int i, bool hold) -> int {
            if (i < 0) {
                return hold ? INT_MIN : 0;
            }
            int& res = memo[i][hold];
            if (res != -1) {
                return res;
            }
            if (hold) {
                return res = max(dfs(i - 1, true),                // skip
                                 dfs(i - 1, false) - prices[i]);  // buy
            } else {
                return res = max(dfs(i - 1, false),              // skip
                                 dfs(i - 1, true) + prices[i]);  // sell
            }
        };

        return dfs(n - 1, false);
    }

    int maxProfitIterative(vector<int>& prices) {
        int n = prices.size();
        vector<array<int, 2>> dp(n, {0, 0});
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);  // buy
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);  // sell
        }
        return dp[n - 1][1];
    }

    int maxProfitIterativeOptimized(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) return 0;

        int hold = -prices[0], res = 0;

        for (int i = 1; i < n; i++) {
            hold = max(hold, res - prices[i]);  // buy
            res = max(res, hold + prices[i]);   // sell
        }
        return res;
    }

    int maxProfitGreedy(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) return 0;

        int res = 0;

        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1]) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
};

int main() {
    Solution solution;
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    assert(solution.maxProfitMemo(prices) == 7);
    assert(solution.maxProfitIterative(prices) == 7);
    assert(solution.maxProfitIterativeOptimized(prices) == 7);
    assert(solution.maxProfitGreedy(prices) == 7);
    return 0;
}

199. Binary Tree Right Side View

  • LeetCode | 力扣

  • Tags: Tree, Depth First Search, Breadth First Search, Binary Tree

from collections import deque
from typing import List, Optional

from binarytree import Node as TreeNode
from binarytree import build


# Binary Tree BFS
def rightSideViewBFS(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []

    q = deque([root])
    res = []

    while q:
        n = len(q)
        for i in range(n):
            node = q.popleft()
            if i == n - 1:
                res.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

    return res


# Binary Tree DFS
def rightSideViewDFS(root: Optional[TreeNode]) -> List[int]:
    """后序遍历，先右后左，遇到的第一个节点就是该深度的最右侧节点"""
    ans = []

    def dfs(node, depth):
        if node is None:
            return
        if depth == len(ans):  # 这个深度首次遇到
            ans.append(node.val)

        dfs(node.right, depth + 1)
        dfs(node.left, depth + 1)

    dfs(root, 0)

    return ans


if __name__ == "__main__":
    root = [1, 2, 2, 3, 4, None, 3, None, None, 5]
    root = build(root)
    print(root)
    #     ____1
    #    /     \
    #   2__     2
    #  /   \     \
    # 3     4     3
    #      /
    #     5
    assert rightSideViewBFS(root) == [1, 2, 3, 5]
    assert rightSideViewDFS(root) == [1, 2, 3, 5]

176. Second Highest Salary

1539. Kth Missing Positive Number

43. Multiply Strings

# Math
def multiply(num1: str, num2: str) -> str:
    if num1 == "0" or num2 == "0":
        return "0"

    m, n = len(num1), len(num2)
    result = [0 for _ in range(m + n)]

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            mul = int(num1[i]) * int(num2[j])
            sum = mul + result[i + j + 1]

            result[i + j + 1] = sum % 10
            result[i + j] += sum // 10

    result_str = "".join(map(str, result)).lstrip("0")

    return result_str if result_str else "0"


num1 = "2"
num2 = "3"
print(multiply(num1, num2))  # "6"

50. Pow(x, n)

# Iterative
def myPowIterative(x: float, n: int) -> float:
    if n == 0:
        return 1
    if n < 0:
        x = 1 / x
        n = -n

    result = 1
    cur = x

    while n > 0:
        if n % 2 == 1:
            result *= cur

        cur *= cur
        n //= 2

    return result


# Recursive
def myPowRecursive(x: float, n: int) -> float:
    if n == 0:
        return 1
    if n < 0:
        x = 1 / x
        n = -n

    if n % 2 == 0:
        return myPowRecursive(x * x, n // 2)
    else:
        return x * myPowRecursive(x * x, n // 2)


x = 2.00000
n = 10
print(myPowIterative(x, n))  # 1024.0
print(myPowRecursive(x, n))  # 1024.0

32. Longest Valid Parentheses

# Stack
def longestValidParentheses(s: str) -> int:
    stack = [-1]
    res = 0

    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        elif ch == ")":
            stack.pop()
            if stack:
                res = max(res, i - stack[-1])
            else:
                stack.append(i)

    return res


if __name__ == "__main__":
    print(longestValidParentheses("(()"))  # 2
    print(longestValidParentheses(")()())"))  # 4

528. Random Pick with Weight

  • LeetCode | 力扣

  • Tags: Array, Math, Binary Search, Prefix Sum, Randomized

63. Unique Paths II

from functools import cache
from typing import List


class UniquePathsWithObstacles:
    def memoization(self, obstacleGrid: List[List[int]]) -> int:
        """
        Approach: DFS with Memoization
        Time complexity: O(mn).
        Space complexity: O(mn).
        """

        @cache
        def dfs(i: int, j: int) -> int:
            if i < 0 or j < 0 or obstacleGrid[i][j]:
                return 0
            if i == 0 and j == 0:
                return 1
            return dfs(i - 1, j) + dfs(i, j - 1)

        m, n = len(obstacleGrid), len(obstacleGrid[0])
        return dfs(m - 1, n - 1)

    def dp_2d(self, obstacleGrid: List[List[int]]) -> int:
        """
        Approach: 2D Dynamic Programming
        Time complexity: O(mn).
        Space complexity: O(mn).
        """
        # edge cases
        if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
            return 0

        m, n = len(obstacleGrid), len(obstacleGrid[0])

        # init dp
        dp = [[0] * n for _ in range(m)]

        for i in range(m):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = 1
            else:
                break

        for j in range(n):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = 1
            else:
                break

        # update dp
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    continue
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        return dp[-1][-1]

    def dp_1d(self, obstacleGrid: List[List[int]]) -> int:
        """
        Approach: 1D Dynamic Programming
        Time complexity: O(mn).
        Space complexity: O(n).
        """
        n = len(obstacleGrid[0])
        dp = [0] * (n + 1)
        dp[1] = 1

        for row in obstacleGrid:
            for j, x in enumerate(row):
                if x == 0:
                    dp[j + 1] += dp[j]
                else:
                    dp[j + 1] = 0
        return dp[n]


if __name__ == "__main__":
    solution = UniquePathsWithObstacles()
    obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
    assert solution.dp_2d(obstacleGrid) == 2
    assert solution.memoization(obstacleGrid) == 2
    assert solution.dp_1d(obstacleGrid) == 2

380. Insert Delete GetRandom O(1)

import random


class RandomizedSet:
    def __init__(self):
        self.nums = []
        self.pos = {}  # num: idx

    def insert(self, val: int) -> bool:
        if val in self.pos:
            return False
        self.pos[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.pos:
            return False

        idx = self.pos[val]
        last_val = self.nums[-1]
        self.nums[idx] = last_val
        self.pos[last_val] = idx

        self.nums.pop()
        del self.pos[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)


def test_RandomizedSet():
    obj = RandomizedSet()
    assert obj.insert(1)
    assert not obj.remove(2)
    assert obj.insert(2)
    assert obj.getRandom() in [1, 2]
    assert obj.remove(1)
    assert not obj.insert(2)
    assert obj.getRandom() == 2

383. Ransom Note

"""
-   Return `True` if the ransom note can be constructed from the magazines, otherwise, return `False`.
"""

from collections import Counter, defaultdict


# Array
def canConstructArray(ransomNote: str, magazine: str) -> bool:
    if len(ransomNote) > len(magazine):
        return False

    record = [0 for _ in range(26)]

    for i in magazine:
        record[ord(i) - ord("a")] += 1

    for j in ransomNote:
        record[ord(j) - ord("a")] -= 1

    for i in record:
        if i < 0:
            return False

    return True


# Dict
def canConstructDict(ransomNote: str, magazine: str) -> bool:
    if len(ransomNote) > len(magazine):
        return False

    record = defaultdict(int)

    for i in magazine:
        record[i] += 1

    for j in ransomNote:
        if j not in record or record[j] == 0:
            return False
        record[j] -= 1

    return True


# Counter
def canConstructCounter(ransomNote: str, magazine: str) -> bool:
    return not Counter(ransomNote) - Counter(magazine)


ransomNote = "aa"
magazine = "aab"
print(canConstructArray(ransomNote, magazine))  # True
print(canConstructDict(ransomNote, magazine))  # True
print(canConstructCounter(ransomNote, magazine))  # True

101. Symmetric Tree

  • LeetCode | 力扣

  • Tags: Tree, Depth First Search, Breadth First Search, Binary Tree

from collections import deque
from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


# Recursive
def is_symmetric_recursive(root: Optional[TreeNode]) -> bool:
    if not root:
        return True

    def check(left, right):
        if left is right:
            return True
        if not left or not right or left.val != right.val:
            return False
        outside = check(left.left, right.right)
        inside = check(left.right, right.left)
        return outside and inside

    return check(root.left, root.right)


# Iterative
def is_symmetric_iterative(root: Optional[TreeNode]) -> bool:
    if not root:
        return True

    q = deque()
    q.append(root.left)
    q.append(root.right)

    while q:
        left = q.popleft()
        right = q.popleft()

        if not left and not right:
            continue

        if not left or not right or left.val != right.val:
            return False

        q.append(left.left)
        q.append(right.right)
        q.append(left.right)
        q.append(right.left)

    return True


if __name__ == "__main__":
    root = [1, 2, 2, 3, 4, 4, 3]
    root = build(root)
    print(root)
    #     __1__
    #    /     \
    #   2       2
    #  / \     / \
    # 3   4   4   3
    assert is_symmetric_recursive(root) is True
    assert is_symmetric_iterative(root) is True

#include <iostream>

#include "include/trees.hpp"

class Solution {
   private:
    bool dfs(TreeNode *Left, TreeNode *Right) {
        if (Left == nullptr && Right == nullptr) return true;
        if (Left == nullptr || Right == nullptr || Left->val != Right->val)
            return false;
        return dfs(Left->left, Right->right) && dfs(Left->right, Right->left);
    }

   public:
    bool isSymmetric(TreeNode *root) {
        return root == nullptr || dfs(root->left, root->right);
    }
};

int main() {
    Solution solution;
    // Test with a symmetric tree
    std::vector<int> values = {1, 2, 2, 3, 4, 4, 3};
    TreeNode *root = TreeUtils::buildTree(values);
    bool result = solution.isSymmetric(root);
    std::cout << "Is symmetric: " << (result ? "true" : "false") << std::endl;
    return 0;
}

206. Reverse Linked List

from typing import Optional

from leetpattern.utils import LinkedList, ListNode


def reverse_list_iterative(head: Optional[ListNode]) -> Optional[ListNode]:
    cur = head
    prev = None

    while cur:
        temp = cur.next
        cur.next = prev

        prev = cur
        cur = temp

    return prev


def reverse_list_recursive(head: Optional[ListNode]) -> Optional[ListNode]:
    def reverse(cur, prev):
        if not cur:
            return prev

        temp = cur.next
        cur.next = prev
        return reverse(temp, cur)

    return reverse(head, None)


def test_reverse_list():
    ll = LinkedList([1, 2, 3, 4, 5])
    ll.head = reverse_list_iterative(ll.head)
    assert ll.to_array() == [5, 4, 3, 2, 1]

    ll = LinkedList([1, 2, 3, 4, 5])
    ll.head = reverse_list_recursive(ll.head)
    assert ll.to_array() == [5, 4, 3, 2, 1]

13. Roman to Integer

from itertools import pairwise


# Arrays
def romanToInt(s: str) -> int:
    ROMAN = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
    }

    res = 0

    for x, y in pairwise(s):
        x, y = ROMAN[x], ROMAN[y]
        res += x if x >= y else -x

    return res + ROMAN[s[-1]]


if __name__ == "__main__":
    assert romanToInt("III") == 3
    assert romanToInt("IV") == 4
    assert romanToInt("IX") == 9
    assert romanToInt("LVIII") == 58
    assert romanToInt("MCMXCIV") == 1994
    assert romanToInt("MMXXIII") == 2023

278. First Bad Version

"""
-   Find the first bad version given a function `isBadVersion`.
"""


# Binary Search
def firstBadVersion(n: int) -> int:
    left, right = 1, n

    while left <= right:
        mid = left + (right - left) // 2

        if isBadVersion(mid):
            right = mid - 1
        else:
            left = mid + 1

    return left


def isBadVersion(version: int) -> bool:
    pass

141. Linked List Cycle

from typing import Optional

from leetpattern.utils import LinkedList, ListNode


def has_cycle(head: Optional[ListNode]) -> bool:
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False


def test_has_cycle():
    ll = LinkedList([3, 2, 0, -4])
    ll.make_cycle(pos=1)
    assert has_cycle(ll.head)

    ll = LinkedList([1, 2])
    ll.make_cycle(pos=0)
    assert has_cycle(ll.head)

    ll = LinkedList([1, 2, 3, 4, 5])
    assert not has_cycle(ll.head)

#include <cassert>
#include <iostream>

#include "include/lists.hpp"
using namespace std;

class Solution {
   public:
    bool has_cycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (fast == slow) return true;
        }
        return false;
    }
};

int main() {
    Solution solution;

    ListNode* head = LinkedList::build({3, 2, 0, -4});
    // create cycle
    head = LinkedList::make_cycle(head, 1);
    assert(solution.has_cycle(head) == true);
    // no cycle
    ListNode* head2 = LinkedList::build({1, 2});
    assert(solution.has_cycle(head2) == false);
    // no cycle
    ListNode* head3 = LinkedList::build({1});
    assert(solution.has_cycle(head3) == false);

    return 0;
}

1903. Largest Odd Number in String

417. Pacific Atlantic Water Flow

  • LeetCode | 力扣

  • Tags: Array, Depth First Search, Breadth First Search, Matrix

from collections import deque
from typing import List


# DFS
def pacificAtlanticDFS(heights: List[List[int]]) -> List[List[int]]:
    m, n = len(heights), len(heights[0])
    pac, atl = set(), set()
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    def dfs(r, c, visited, prev_height):
        if (
            r not in range(m)
            or c not in range(n)
            or heights[r][c] < prev_height
            or (r, c) in visited
        ):
            return None

        visited.add((r, c))
        height = heights[r][c]
        for dr, dc in directions:
            dfs(dr + r, dc + c, visited, height)

    for c in range(n):
        dfs(0, c, pac, heights[0][c])
        dfs(m - 1, c, atl, heights[m - 1][c])

    for r in range(m):
        dfs(r, 0, pac, heights[r][0])
        dfs(r, n - 1, atl, heights[r][n - 1])

    return list(pac & atl)


# BFS
def pacificAtlanticBFS(heights: List[List[int]]) -> List[List[int]]:
    m, n = len(heights), len(heights[0])
    pac, atl = set(), set()
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def bfs(r, c, visited):
        q = deque([(r, c)])
        visited.add((r, c))

        while q:
            row, col = q.popleft()

            for dr, dc in directions:
                nr, nc = row + dr, col + dc

                if (
                    nr in range(m)
                    and nc in range(n)
                    and heights[row][col] <= heights[nr][nc]
                    and (nr, nc) not in visited
                ):
                    q.append((nr, nc))
                    visited.add((nr, nc))

    for c in range(n):
        bfs(0, c, pac)  # top
        bfs(m - 1, c, atl)  # bottom

    for r in range(m):
        bfs(r, 0, pac)  # left
        bfs(r, n - 1, atl)  # right

    return list(pac & atl)


heights = [
    [1, 2, 2, 3, 5],
    [3, 2, 3, 4, 4],
    [2, 4, 5, 3, 1],
    [6, 7, 1, 4, 5],
    [5, 1, 1, 2, 4],
]
print(pacificAtlanticDFS(heights))
# [(4, 0), (0, 4), (3, 1), (1, 4), (3, 0), (2, 2), (1, 3)]
print(pacificAtlanticBFS(heights))
# [(4, 0), (0, 4), (3, 1), (1, 4), (3, 0), (2, 2), (1, 3)]

787. Cheapest Flights Within K Stops

  • LeetCode | 力扣

  • Tags: Dynamic Programming, Depth First Search, Breadth First Search, Graph, Heap Priority Queue, Shortest Path

"""
-   Return the cheapest price from `src` to `dst` with at most `K` stops.
<iframe width="560" height="315" src="https://www.youtube.com/embed/5eIK3zUdYmE?si=aBR0VbHXTgNuVlGz" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
"""

import heapq
from collections import defaultdict
from typing import List


# Bellman-Ford
def findCheapestPriceBF(
    n: int, flights: List[List[int]], src: int, dst: int, k: int
) -> int:
    prices = [float("inf") for _ in range(n)]
    prices[src] = 0

    for _ in range(k + 1):
        temp = prices[:]
        for u, v, w in flights:
            temp[v] = min(temp[v], prices[u] + w)
        prices = temp

    return prices[dst] if prices[dst] != float("inf") else -1


# Dijkstra
def findCheapestPriceDijkstra(
    n: int, flights: List[List[int]], src: int, dst: int, k: int
) -> int:
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))

    heap = [(0, src, 0)]  # (price, city, stops)
    visited = defaultdict(int)  # {city: stops}

    while heap:
        price, city, stops = heapq.heappop(heap)

        if city == dst:
            return price

        if stops > k:
            continue

        if city in visited and visited[city] <= stops:
            continue

        visited[city] = stops

        for neighbor, cost in graph[city]:
            heapq.heappush(heap, (price + cost, neighbor, stops + 1))

    return -1


# |------------|------------------|---------|
# |  Approach  |       Time       |  Space  |
# |------------|------------------|---------|
# |Bellman-Ford|    O(k * E)      |  O(n)   |
# | Dijkstra   | O(E * log(V))    |  O(n)   |
# |------------|------------------|---------|


n = 4
flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]]
src = 0
dst = 3
k = 1
print(findCheapestPriceBF(n, flights, src, dst, k))  # 700
print(findCheapestPriceDijkstra(n, flights, src, dst, k))  # 700

#include <cassert>
#include <climits>
#include <queue>
#include <vector>
using namespace std;

class FindCheapestPrice {
   public:
    int bellman_ford(int n, vector<vector<int>>& flights, int src, int dst,
                     int k) {
        vector<int> dist(n, INT_MAX);
        dist[src] = 0;

        for (int i = 0; i <= k; ++i) {
            vector<int> temp(dist);
            for (auto& flight : flights) {
                int u = flight[0], v = flight[1], w = flight[2];
                if (dist[u] != INT_MAX && dist[u] + w < temp[v]) {
                    temp[v] = dist[u] + w;
                }
            }
            dist = temp;
        }
        return dist[dst] == INT_MAX ? -1 : dist[dst];
    }

    int dijkstra(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int, int>>> graph(n);
        for (auto& flight : flights) {
            graph[flight[0]].push_back({flight[1], flight[2]});
        }
        priority_queue<array<int, 3>, vector<array<int, 3>>,
                       greater<array<int, 3>>>
            min_heap;
        min_heap.push({0, src, k + 1});

        while (!min_heap.empty()) {
            auto [cost, u, stops] = min_heap.top();
            min_heap.pop();
            if (u == dst) {
                return cost;
            }
            if (stops > 0) {
                for (auto& [v, w] : graph[u]) {
                    min_heap.push({cost + w, v, stops - 1});
                }
            }
        }

        return -1;
    }
};

int main() {
    FindCheapestPrice solution;
    int n = 4;
    vector<vector<int>> flights = {
        {0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
    int src = 0, dst = 3, k = 1;
    assert(solution.bellman_ford(n, flights, src, dst, k) == 700);
    assert(solution.dijkstra(n, flights, src, dst, k) == 700);

    return 0;
}

2050. Parallel Courses III

  • LeetCode | 力扣

  • Tags: Array, Dynamic Programming, Graph, Topological Sort

863. All Nodes Distance K in Binary Tree

  • LeetCode | 力扣

  • Tags: Hash Table, Tree, Depth First Search, Breadth First Search, Binary Tree

from collections import deque
from typing import List

from binarytree import Node as TreeNode
from binarytree import build


# BFS
def distanceK(root: TreeNode, target: TreeNode, k: int) -> List[int]:
    parent = dict()

    def dfs(node, par=None):
        if node:
            parent[node] = par
            dfs(node.left, node)
            dfs(node.right, node)

    dfs(root)

    q = deque([(target, 0)])
    seen = set([target])

    while q:
        node, dist = q.popleft()

        if dist == k:
            return [node.val] + [node.val for node, _ in q]

        for nei in (node.left, node.right, parent[node]):
            if nei and nei not in seen:
                seen.add(nei)
                q.append((nei, dist + 1))

    return []


root = build([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
print(root)
#     ______3__
#    /         \
#   5__         1
#  /   \       / \
# 6     2     0   8
#      / \
#     7   4
target = root.left
k = 2
print(distanceK(root, target, k))  # [7, 4, 1]

81. Search in Rotated Sorted Array II

1192. Critical Connections in a Network

  • LeetCode | 力扣

  • Tags: Depth First Search, Graph, Biconnected Component

from collections import defaultdict
from typing import List


# Tarjan
def criticalConnections(n: int, connections: List[List[int]]) -> List[List[int]]:
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)

    disc = [-1] * n
    low = [-1] * n
    bridges = []
    time = 0

    def dfs(n1, prev):
        nonlocal time
        disc[n1], low[n1] = time, time
        time += 1

        for n2 in graph[n1]:
            if n2 == prev:
                continue
            if disc[n2] == -1:
                dfs(n2, n1)
                low[n1] = min(low[n1], low[n2])

                if low[n2] > disc[n1]:
                    bridges.append([n1, n2])
            else:
                low[n1] = min(low[n1], disc[n2])

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)

    return bridges


n = 4
connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
print(criticalConnections(n, connections))  # [[1, 3]]

658. Find K Closest Elements

  • LeetCode | 力扣

  • Tags: Array, Two Pointers, Binary Search, Sliding Window, Sorting, Heap Priority Queue

595. Big Countries

SELECT
    NAME,
    POPULATION,
    AREA
FROM
    WORLD
WHERE
    POPULATION >= 25000000
    OR AREA >= 3000000;

252. Meeting Rooms 👑

from typing import List


# Interval
def canAttendMeetings(intervals: List[List[int]]) -> bool:
    intervals.sort(key=lambda x: x[0])
    n = len(intervals)

    if n <= 1:
        return True

    for i in range(1, n):
        if intervals[i][0] < intervals[i - 1][1]:
            return False

    return True


if __name__ == "__main__":
    intervals = [[0, 30], [5, 10], [15, 20]]
    assert not canAttendMeetings(intervals)

102. Binary Tree Level Order Traversal

from collections import deque
from typing import List, Optional

from binarytree import Node as TreeNode
from binarytree import build


def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []

    q = deque([root])
    res = []

    while q:
        level = []
        size = len(q)

        for _ in range(size):
            cur = q.popleft()
            level.append(cur.val)

            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)

        res.append(level)

    return res


tree = build([3, 9, 20, None, None, 15, 7])
print(tree)
#   3___
#  /    \
# 9     _20
#      /   \
#     15    7
print(levelOrder(tree))  # [[3], [9, 20], [15, 7]]

643. Maximum Average Subarray I

from typing import List


# Sliding Window Fixed Size
def findMaxAverage1(nums: List[int], k: int) -> float:
    maxSum = float("-inf")
    cur = 0

    for idx, num in enumerate(nums):
        cur += num

        if idx < k - 1:
            continue

        maxSum = max(maxSum, cur)
        cur -= nums[idx - k + 1]

    return maxSum / k


# Sliding Window Fixed Size
def findMaxAverage2(nums: List[int], k: int) -> float:
    n = len(nums)
    if n == 1:
        return float(nums[0])

    cur = sum(nums[:k])

    maxSum = cur
    for i in range(k, n):
        cur += nums[i] - nums[i - k]
        maxSum = max(maxSum, cur)

    return maxSum / k


nums = [1, 12, -5, -6, 50, 3]
k = 4
print(findMaxAverage1(nums, k))  # 12.75
print(findMaxAverage2(nums, k))  # 12.75

733. Flood Fill

  • LeetCode | 力扣

  • Tags: Array, Depth First Search, Breadth First Search, Matrix

"""
- Replace all the pixels of the same color starting from the given pixel.
- In other words, find the connected component of the starting pixel and change the color of all the pixels in that component.
- Edge cases: If the starting pixel is already the target color, return the image as it is.
- **Flood Fill** is essentially a graph traversal algorithm (like BFS or DFS) applied to matrices (2D grids).
  It checks adjacent cells (up, down, left, right) of a starting point to determine whether they belong to the same region.
  Typically, it involves modifying or marking the cells that belong to the same connected component.

![flood_fill](../../assets/flood_fill_example.png)

![733](../../assets/0733.jpg)

|  1  |   1   |  1  |
| :-: | :---: | :-: |
|  1  | ==1== |  0  |
|  1  |   0   |  1  |

|  1  |   1   |  1  |
| :-: | :---: | :-: |
|  1  | ==2== |  0  |
|  1  |   0   |  1  |

|   1   | ==2== |  1  |
| :---: | :---: | :-: |
| ==2== | ==2== |  0  |
|   1   |   0   |  1  |

| ==2== | ==2== | ==2== |
| :---: | :---: | :---: |
| ==2== | ==2== |   0   |
| ==2== |   0   |   1   |
"""

from collections import deque
from typing import List


# DFS
def floodFillDFS(image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:

    org = image[sr][sc]
    m, n = len(image), len(image[0])

    if org == color:
        return image

    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or image[r][c] != org:
            return None

        image[r][c] = color

        dfs(r - 1, c)
        dfs(r + 1, c)
        dfs(r, c - 1)
        dfs(r, c + 1)

    dfs(sr, sc)

    return image


# BFS
def floodFillBFS(image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:

    org = image[sr][sc]
    m, n = len(image), len(image[0])
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    if org == color:
        return image

    q = deque([(sr, sc)])

    while q:
        r, c = q.popleft()
        image[r][c] = color

        for dr, dc in dirs:
            nr, nc = r + dr, c + dc

            if 0 <= nr < m and 0 <= nc < n and image[nr][nc] == org:
                q.append((nr, nc))

    return image


image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
sr = 1
sc = 1

print(floodFillDFS(image, sr, sc, 2))
# [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
print(floodFillBFS(image, sr, sc, 2))
# [[2, 2, 2], [2, 2, 0], [2, 0, 1]]

#include <cassert>
#include <functional>
#include <queue>
#include <vector>
using namespace std;

class Solution {
   private:
    void dfs(vector<vector<int>>& image, int org, int color, int r, int c) {
        int m = image.size(), n = image[0].size();
        if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] != org) {
            return;
        }
        image[r][c] = color;
        dfs(image, org, color, r - 1, c);
        dfs(image, org, color, r + 1, c);
        dfs(image, org, color, r, c - 1);
        dfs(image, org, color, r, c + 1);
    }

   public:
    // DFS
    vector<vector<int>> flood_fill_dfs(vector<vector<int>>& image, int sr,
                                       int sc, int color) {
        int org = image[sr][sc];
        if (org == color) return image;

        dfs(image, org, color, sr, sc);
        return image;
    }

    // DFS with lambda
    vector<vector<int>> flood_fill_dfs_lambda(vector<vector<int>>& image,
                                              int sr, int sc, int color) {
        int org = image[sr][sc];
        if (org == color) return image;

        int m = image.size(), n = image[0].size();

        function<void(int, int)> dfs = [&](int r, int c) -> void {
            if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] != org) {
                return;
            }
            image[r][c] = color;
            dfs(r - 1, c);
            dfs(r + 1, c);
            dfs(r, c - 1);
            dfs(r, c + 1);
        };

        dfs(sr, sc);

        return image;
    }

    // BFS
    vector<vector<int>> flood_fill_bfs(vector<vector<int>>& image, int sr,
                                       int sc, int color) {
        int org = image[sr][sc];
        if (org == color) return image;

        int m = image.size(), n = image[0].size();
        vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        queue<pair<int, int>> q;
        q.push({sr, sc});

        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();
            image[r][c] = color;
            for (auto& dir : dirs) {
                int nr = r + dir.first;
                int nc = c + dir.second;
                if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                    image[nr][nc] == org) {
                    q.push({nr, nc});
                }
            }
        }

        return image;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
    solution.flood_fill_dfs(image, 1, 1, 2);
    vector<vector<int>> expected = {{2, 2, 2}, {2, 2, 0}, {2, 0, 1}};
    assert((image == expected));

    image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
    solution.flood_fill_dfs_lambda(image, 1, 1, 2);
    assert((image == expected));

    image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
    solution.flood_fill_bfs(image, 1, 1, 2);
    assert((image == expected));
    return 0;
}

2384. Largest Palindromic Number

1674. Minimum Moves to Make Array Complementary

105. Construct Binary Tree from Preorder and Inorder Traversal

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Divide And Conquer, Tree, Binary Tree

from typing import List, Optional

from helper import TreeNode


def buildTree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    """
    preorder  root left right  1  2  3
    inorder   left root right  4  5  6
    """
    if len(preorder) == 0:
        return None

    root_val = preorder[0]  # 1
    root = TreeNode(root_val)

    separator_idx = inorder.index(root_val)  # 5

    left_inorder = inorder[:separator_idx]  # 4
    right_inorder = inorder[separator_idx + 1 :]  # 6

    left_preorder = preorder[1 : 1 + len(left_inorder)]  # 2
    right_preorder = preorder[1 + len(left_inorder) :]  # 3

    root.left = buildTree(left_preorder, left_inorder)
    root.right = buildTree(right_preorder, right_inorder)

    return root


preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
root = buildTree(preorder, inorder)
print(root)
#     3
#    / \
#   9  20
#     /  \
#    15   7

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right)
        : val(x), left(left), right(right) {}
};

class Solution {
   public:
    vector<int> preorder;
    unordered_map<int, int> inorderMap;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        for (size_t i = 0; i < inorder.size(); i++) {
            inorderMap[inorder[i]] = i;
        }
        return buildSubtree(0, 0, inorder.size() - 1);
    }

   private:
    TreeNode* buildSubtree(int rootIndex, int left, int right) {
        if (left > right) return nullptr;

        TreeNode* root = new TreeNode(preorder[rootIndex]);
        int inorderIndex = inorderMap[preorder[rootIndex]];

        root->left = buildSubtree(rootIndex + 1, left, inorderIndex - 1);
        root->right = buildSubtree(rootIndex + (inorderIndex - left + 1),
                                   inorderIndex + 1, right);

        return root;
    }
};

int main() {
    vector<int> preorder = {3, 9, 20, 15, 7};
    vector<int> inorder = {9, 3, 15, 20, 7};
    Solution solution;
    TreeNode* root = solution.buildTree(preorder, inorder);
    cout << root->val << endl;                // 3
    cout << root->left->val << endl;          // 9
    cout << root->right->val << endl;         // 20
    cout << root->right->left->val << endl;   // 15
    cout << root->right->right->val << endl;  // 7
    return 0;
}

1021. Remove Outermost Parentheses

72. Edit Distance

from functools import cache


# Recursive
def minDistanceDFS(word1: str, word2: str) -> int:
    n, m = len(word1), len(word2)

    @cache
    def dfs(i: int, j: int) -> int:
        if i < 0:
            return j + 1
        if j < 0:
            return i + 1
        if word1[i] == word2[j]:
            return dfs(i - 1, j - 1)

        return 1 + min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1))

    return dfs(n - 1, m - 1)


# Iterative
def minDistanceDP(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # no operation
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],  # delete
                    dp[i][j - 1],  # insert
                    dp[i - 1][j - 1],  # replace
                )
    return dp[-1][-1]


if __name__ == "__main__":
    word1 = "horse"
    word2 = "ros"
    print(minDistanceDFS(word1, word2))  # 3
    print(minDistanceDP(word1, word2))  # 3

189. Rotate Array

"""
- Rotate array with reversing subarrays
"""

from typing import List


# Array
def rotate(nums: List[int], k: int) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """

    def reverse(i: int, j: int) -> None:
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    n = len(nums)
    k %= n
    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)


nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
rotate(nums, k)
print(nums)  # [5, 6, 7, 1, 2, 3, 4]

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Array
void rotate(vector<int>& nums, int k) {
    k %= nums.size();

    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin() + k);
    reverse(nums.begin() + k, nums.end());
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    int k = 3;
    rotate(nums, k);
    // [5, 6, 7, 1, 2, 3, 4]
    for (const auto& num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

1480. Running Sum of 1d Array

1768. Merge Strings Alternately

2965. Find Missing and Repeated Values

88. Merge Sorted Array

from typing import List


class merge:
    @staticmethod
    def lr(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2, t = m - 1, n - 1, m + n - 1

        while p1 >= 0 or p2 >= 0:
            if p1 == -1:
                nums1[t] = nums2[p2]
                p2 -= 1
            elif p2 == -1:
                nums1[t] = nums1[p1]
                p1 -= 1
            elif nums1[p1] > nums2[p2]:
                nums1[t] = nums1[p1]
                p1 -= 1
            else:
                nums1[t] = nums2[p2]
                p2 -= 1

            t -= 1


if __name__ == "__main__":
    nums1 = [1, 2, 3, 0, 0, 0]
    m = 3
    nums2 = [2, 5, 6]
    n = 3
    merge.lr(nums1, m, nums2, n)
    assert nums1 == [1, 2, 2, 3, 5, 6]

#include <cassert>
#include <vector>
using namespace std;

class Solution {
   public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1, t = m + n - 1;

        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                nums1[t] = nums2[p2];
                p2--;
            } else if (p2 == -1) {
                nums1[t] = nums1[p1];
                p1--;
            } else if (nums1[p1] > nums2[p2]) {
                nums1[t] = nums1[p1];
                p1--;
            } else {
                nums1[t] = nums2[p2];
                p2--;
            }
            t--;
        }
    }
};

int main() {
    Solution solution;
    vector<int> nums1 = {1, 3, 6, 0, 0, 0};
    vector<int> nums2 = {2, 5, 6};
    vector<int> output = {1, 2, 3, 5, 6, 6};
    solution.merge(nums1, 3, nums2, 3);
    assert(nums1 == output);
    return 0;
}

2161. Partition Array According to Given Pivot

229. Majority Element II

from collections import Counter
from typing import List


# Hash Map
def majorityElementHash(nums: List[int]) -> List[int]:
    counts = Counter(nums)
    target = len(nums) // 3
    res = []

    for num in nums:
        if counts[num] > target and num not in res:
            res.append(num)

    return res


# Boyer-Moore
def majorityElementMoore(nums: List[int]) -> List[int]:
    if not nums:
        return []

    cdt1, cnt1 = None, 0
    cdt2, cnt2 = None, 0

    for num in nums:
        if num == cdt1:
            cnt1 += 1
        elif num == cdt2:
            cnt2 += 1
        elif cnt1 == 0:
            cdt1, cnt1 = num, 1
        elif cnt2 == 0:
            cdt2, cnt2 = num, 1
        else:
            cnt1 -= 1
            cnt2 -= 1

    return [n for n in (cdt1, cdt2) if nums.count(n) > len(nums) // 3]


nums = [3, 2, 3]
print(majorityElementHash(nums))  # [3]
print(majorityElementMoore(nums))  # [3]

876. Middle of the Linked List

from typing import Optional

from leetpattern.utils import LinkedList, ListNode


# Linked List
def middleNode(head: Optional[ListNode]) -> Optional[ListNode]:
    fast, slow = head, head

    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next

    return slow


def test_middleNode():
    # Test case 1: Odd number of nodes
    ll1 = LinkedList([1, 2, 3, 4, 5])
    middle1 = middleNode(ll1.head)
    result1 = LinkedList(middle1)
    assert result1.to_array() == [3, 4, 5]

    # Test case 2: Even number of nodes
    ll2 = LinkedList([1, 2, 3, 4, 5, 6])
    middle2 = middleNode(ll2.head)
    result2 = LinkedList(middle2)
    assert result2.to_array() == [4, 5, 6]

    # Test case 3: Single node
    ll3 = LinkedList([1])
    middle3 = middleNode(ll3.head)
    result3 = LinkedList(middle3)
    assert result3.to_array() == [1]

    # Test case 4: Two nodes
    ll4 = LinkedList([1, 2])
    middle4 = middleNode(ll4.head)
    result4 = LinkedList(middle4)
    assert result4.to_array() == [2]

36. Valid Sudoku

from typing import List


# Set
def isValidSudoku(board: List[List[str]]) -> bool:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    for i in range(9):
        for j in range(9):
            if board[i][j] == ".":
                continue

            if board[i][j] in rows[i]:
                return False
            rows[i].add(board[i][j])

            if board[i][j] in cols[j]:
                return False
            cols[j].add(board[i][j])

            box_index = (i // 3) * 3 + j // 3
            if board[i][j] in boxes[box_index]:
                return False
            boxes[box_index].add(board[i][j])

    return True


board = [
    ["5", "3", ".", ".", "7", ".", ".", ".", "."],
    ["6", ".", ".", "1", "9", "5", ".", ".", "."],
    [".", "9", "8", ".", ".", ".", ".", "6", "."],
    ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
    ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
    ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
    [".", "6", ".", ".", ".", ".", "2", "8", "."],
    [".", ".", ".", "4", "1", "9", ".", ".", "5"],
    [".", ".", ".", ".", "8", ".", ".", "7", "9"],
]
print(isValidSudoku(board))  # True

268. Missing Number

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Math, Binary Search, Bit Manipulation, Sorting

from typing import List


# Math
def missingNumberMath(nums: List[int]) -> int:
    n = len(nums)
    return (n * (n + 1)) // 2 - sum(nums)


# Bit Manipulation (XOR)
def missingNumberXOR(nums: List[int]) -> int:
    n = len(nums)

    for i, num in enumerate(nums):
        n ^= i ^ num

    return n


nums = [3, 0, 1]
print(missingNumberMath(nums))  # 2
print(missingNumberXOR(nums))  # 2

297. Serialize and Deserialize Binary Tree

  • LeetCode | 力扣

  • Tags: String, Tree, Depth First Search, Breadth First Search, Design, Binary Tree

from collections import deque
from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


# BFS
class BFS:
    def serialize(self, root: Optional[TreeNode]) -> str:
        if not root:
            return ""

        res = []
        q = deque([root])

        while q:
            node = q.popleft()

            if node:
                res.append(str(node.val))
                q.append(node.left)
                q.append(node.right)
            else:
                res.append("null")

        return ",".join(res)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data:
            return None

        nodes = data.split(",")
        root = TreeNode(int(nodes[0]))
        q = deque([root])
        index = 1

        while q:
            node = q.popleft()

            if nodes[index] != "null":
                node.left = TreeNode(int(nodes[index]))
                q.append(node.left)
            index += 1

            if nodes[index] != "null":
                node.right = TreeNode(int(nodes[index]))
                q.append(node.right)
            index += 1

        return root


# DFS
class DFS:
    def serialize(self, root: Optional[TreeNode]) -> str:
        def dfs(node):
            if not node:
                return ["null"]
            return [str(node.val)] + dfs(node.left) + dfs(node.right)

        return ",".join(dfs(root))

    def deserialize(self, data: str) -> Optional[TreeNode]:
        nodes = data.split(",")
        self.index = 0

        def dfs():
            if nodes[self.index] == "null":
                self.index += 1
                return None

            node = TreeNode(int(nodes[self.index]))
            self.index += 1

            node.left = dfs()
            node.right = dfs()

            return node

        root = dfs()
        return root


root = build([1, 2, 3, None, None, 4, 5])
print(root)
#   1__
#  /   \
# 2     3
#      / \
#     4   5

bfs = BFS()
data1 = bfs.serialize(root)
print(data1)  # "1,2,3,null,null,4,5,null,null,null,null"
root1 = bfs.deserialize(data1)
print(root1)
#   1__
#  /   \
# 2     3
#      / \
#     4   5

dfs = DFS()
data2 = dfs.serialize(root)
print(data2)  # "1,2,null,null,3,4,null,null,5,null,null"
root2 = dfs.deserialize(data2)
print(root2)
#   1__
#  /   \
# 2     3
#      / \
#     4   5

61. Rotate List

130. Surrounded Regions

  • LeetCode | 力扣

  • Tags: Array, Depth First Search, Breadth First Search, Union Find, Matrix

from collections import deque
from copy import deepcopy
from typing import List


# DFS
def solveDFS(board: List[List[str]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """
    if not board and not board[0]:
        return None

    m, n = len(board), len(board[0])

    def capture(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != "O":
            return None

        board[r][c] = "T"
        capture(r + 1, c)
        capture(r - 1, c)
        capture(r, c + 1)
        capture(r, c - 1)

    for r in range(m):
        for c in range(n):
            if board[r][c] == "O" and (r in [0, m - 1] or c in [0, n - 1]):
                capture(r, c)

    for r in range(m):
        for c in range(n):
            if board[r][c] == "O":
                board[r][c] = "X"

    for r in range(m):
        for c in range(n):
            if board[r][c] == "T":
                board[r][c] = "O"


# BFS
def solveBFS(board: List[List[str]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """
    if not board and not board[0]:
        return None

    m, n = len(board), len(board[0])
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def capture(r, c):
        q = deque([(r, c)])

        while q:
            row, col = q.popleft()

            for dr, dc in dirs:
                nr = row + dr
                nc = col + dc
                if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == "O":
                    board[nr][nc] = "T"
                    q.append((nr, nc))

    for r in range(m):
        for c in range(n):
            if board[r][c] == "O" and (r in [0, m - 1] or c in [0, n - 1]):
                board[r][c] = "T"
                capture(r, c)

    for r in range(m):
        for c in range(n):
            if board[r][c] == "O":
                board[r][c] = "X"

    for r in range(m):
        for c in range(n):
            if board[r][c] == "T":
                board[r][c] = "O"


if __name__ == "__main__":
    board = [
        ["X", "X", "X", "X"],
        ["X", "O", "O", "X"],
        ["X", "X", "O", "X"],
        ["X", "O", "X", "X"],
    ]

    b = deepcopy(board)
    solveDFS(b)
    assert b == [
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "O", "X", "X"],
    ]

    b = deepcopy(board)
    solveBFS(b)
    assert b == [
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "O", "X", "X"],
    ]

567. Permutation in String

  • LeetCode | 力扣

  • Tags: Hash Table, Two Pointers, String, Sliding Window

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False

    count1 = [0] * 26
    count2 = [0] * 26

    for i in range(len(s1)):
        count1[ord(s1[i]) - ord("a")] += 1
        count2[ord(s2[i]) - ord("a")] += 1

    matches = 0
    for i in range(26):
        if count1[i] == count2[i]:
            matches += 1

    l = 0
    for r in range(len(s1), len(s2)):
        if matches == 26:
            return True

        index = ord(s2[r]) - ord("a")
        count2[index] += 1
        if count1[index] == count2[index]:
            matches += 1
        elif count1[index] + 1 == count2[index]:
            matches -= 1

        index = ord(s2[l]) - ord("a")
        count2[index] -= 1
        if count1[index] == count2[index]:
            matches += 1
        elif count1[index] - 1 == count2[index]:
            matches -= 1

        l += 1

    return matches == 26


s1 = "ab"
s2 = "eidba"
print(checkInclusion(s1, s2))  # True

1648. Sell Diminishing-Valued Colored Balls

  • LeetCode | 力扣

  • Tags: Array, Math, Binary Search, Greedy, Sorting, Heap Priority Queue

987. Vertical Order Traversal of a Binary Tree

  • LeetCode | 力扣

  • Tags: Hash Table, Tree, Depth First Search, Breadth First Search, Sorting, Binary Tree

143. Reorder List

from typing import Optional

from leetpattern.utils import LinkedList, ListNode


# Linked List
def reorderList(head: Optional[ListNode]) -> None:
    """
    Do not return anything, modify head in-place instead.
    """
    if not head or not head.next:
        return

    # Middle of the linked list
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse the second half
    pre, cur = None, slow
    while cur:
        temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp

    # Merge two linked lists
    first, second = head, pre
    while second.next:
        temp1, temp2 = first.next, second.next
        first.next = second
        second.next = temp1
        first, second = temp1, temp2


def test_reorderList():
    ll = LinkedList([1, 2, 3, 4, 5, 6])
    assert ll.to_array() == [1, 2, 3, 4, 5, 6]
    reorderList(ll.head)
    assert ll.to_array() == [1, 6, 2, 5, 3, 4]

    ll2 = LinkedList([1, 2, 3, 4, 5])
    assert ll2.to_array() == [1, 2, 3, 4, 5]
    reorderList(ll2.head)
    assert ll2.to_array() == [1, 5, 2, 4, 3]

66. Plus One

from typing import List


# Math
def plusOne(digits: List[int]) -> List[int]:
    n = len(digits)

    for i in range(n - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        else:
            digits[i] = 0

    return [1] + digits


digits = [4, 3, 2, 1]
print(plusOne(digits))  # [4, 3, 2, 2]

#include <cassert>
#include <vector>
using namespace std;

class Solution {
   public:
    vector<int> plusOne(vector<int>& digits) {
        for (int i = digits.size() - 1; i >= 0; i--) {
            digits[i]++;
            if (digits[i] == 10)
                digits[i] = 0;
            else
                return digits;
        }
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

int main() {
    Solution solution;
    vector<int> digits;
    digits = {4, 3, 2, 1};
    assert((solution.plusOne(digits) == vector<int>{4, 3, 2, 2}));
    return 0;
}

493. Reverse Pairs

  • LeetCode | 力扣

  • Tags: Array, Binary Search, Divide And Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

224. Basic Calculator

class Solution:
    def calculate(self, s: str) -> int:
        """Stack: O(n) time, O(n) space.
        Use stack to save result and sign before '(',
        restore after ')'.
        """
        stack = []
        res = 0
        num = 0
        sign = 1

        for char in s:
            if char.isdigit():
                num = num * 10 + int(char)
            elif char == "+":
                res += sign * num
                num = 0
                sign = 1
            elif char == "-":
                res += sign * num
                num = 0
                sign = -1
            elif char == "(":
                stack.append(res)
                stack.append(sign)
                res = 0
                sign = 1
            elif char == ")":
                res += sign * num
                num = 0
                res *= stack.pop()
                res += stack.pop()

        res += sign * num
        return res


def test_calculate():
    s = Solution()
    for fn in (s.calculate,):
        assert fn("1 + 1") == 2
        assert fn(" 2-1 + 2 ") == 3
        assert fn("(1+(4+5+2)-3)+(6+8)") == 23
        assert fn("0") == 0

1482. Minimum Number of Days to Make m Bouquets

from typing import List


# Binary Search Min Answer
def minDays(bloomDay: List[int], m: int, k: int) -> int:
    n = len(bloomDay)
    if m * k > n:
        return -1

    def canMake(day: int) -> bool:
        bouquets = 0
        flowers = 0
        for bloom in bloomDay:
            if bloom <= day:
                flowers += 1
                if flowers == k:
                    bouquets += 1
                    flowers = 0
            else:
                flowers = 0
        return bouquets >= m

    left, right = min(bloomDay), max(bloomDay)
    res = -1

    while left <= right:
        mid = left + (right - left) // 2
        if canMake(mid):
            res = mid
            right = mid - 1
        else:
            left = mid + 1

    return res


if __name__ == "__main__":
    bloomDay = [1, 10, 3, 10, 2]
    m = 3
    k = 1
    assert minDays(bloomDay, m, k) == 3

258. Add Digits

67. Add Binary

2385. Amount of Time for Binary Tree to Be Infected

  • LeetCode | 力扣

  • Tags: Hash Table, Tree, Depth First Search, Breadth First Search, Binary Tree

680. Valid Palindrome II

410. Split Array Largest Sum

  • LeetCode | 力扣

  • Tags: Array, Binary Search, Dynamic Programming, Greedy, Prefix Sum