DrKode

Array & Hashing

Contains Duplicate

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hashset = set()
        for n in nums:
            if n in hashset:
                return True
            hashset.add(n)
        return False

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        countS = {}
        for c in s:
            if c not in countS:
                countS[c] = 0
            countS[c] += 1
        
        countT = {}
        for c in t:
            if c not in countT:
                countT[c] = 0
            countT[c] += 1

        for k in countS.keys():
            if (k not in countT) or (countS[k] != countT[k]):
                return False
        return True

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

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        hashmap = defaultdict(list)
        
        for word in strs:
            arr = [0] * 26
            for c in word:
                i = ord(c) - ord('a')
                arr[i] += 1
            
            keyy = ''
            for c in arr:
                keyy += str(c) + '#'
            hashmap[keyy].append(word)
        
        return list(hashmap.values())

Top K Frequent Elements

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        hashmap =  {}
        N = len(nums)
        
        for n in nums:
            if n not in hashmap:
                hashmap[n] = 0
            hashmap[n] += 1
                
                
        arr = [[] for _ in range(N + 1)]

        for keyy, v in hashmap.items():
            arr[v].append(keyy)
            
        res = []
        r = len(nums)
        
        while -1 < r:
            for n in arr[r]:
                res.append(n)
                if len(res) == k:
                    return res
            r -= 1
        return res

Encode & Decode Strings

class Solution:
    def encode(self, strs: List[str]) -> str:
        res = ''
        for s in strs:
            res += str(len(s)) + '#' + s
        return res

    def decode(self, s: str) -> List[str]:
        i = 0
        N = len(s)
        res = []

        while i < N:
            j = i

            while s[j+1] != '#':
                j += 1
            n = int(s[i:j+1])
            res.append(s[j+2:j+2+n])
            i = j + n + 2

            # j   -> at length of n
            # j+1 -> at '#'
            # j+2 -> word 1st index

        return res

Product of Array Except Self

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        N = len(nums)
        res = [1] * N
        cur = 1

        for i in range(N):
            res[i] *= cur
            cur *= nums[i]

        cur = 1
        for i in range(N-1, -1, -1):
            res[i] *= cur
            cur *= nums[i]

        return res

Longest Consecutive Subsequence

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        res = 0
        hashset = set(nums)
        for n in hashset:
            if n - 1 in hashset:
                continue
            m = n
            while m + 1 in hashset:
                m += 1
            res = max(res, m - n + 1)
        return res

Two Pointer

Valid Palindrome

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

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        N = len(nums)
        res = []
        for i in range(N-2):
            if i != 0 and nums[i-1] == nums[i]: continue
            l, r = i+1, N-1
            while l < r:
                v = nums[i] + nums[l] + nums[r]
                if v < 0:
                    l += 1
                elif 0 < v:
                    r -= 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    while l + 1 < r and nums[l] == nums[l+1]:
                        l += 1
                    l += 1
        return res

Container With Most Water

class Solution:
    def maxArea(self, height: List[int]) -> int:
        res = 0
        l, r = 0, len(height)-1
        while l < r:
            heit = min(height[l], height[r])
            res = max(res, heit * (r-l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return res

Sliding Window

Best Time to Buy And Sell Stock

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        bought = inf
        for n in prices:
            res = max(res, n - bought)
            bought = min(bought, n)
        return res

Longest Substing Without Repeating Characters

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        hashmap = {}
        l = res = 0
        for r in range(len(s)):
            if s[r] in hashmap:
                l = max(l,hashmap[s[r]] + 1)
            res = max(res, r - l + 1)
            hashmap[s[r]] = r
        return res

Minimum Window Substring

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        hashmapT = Counter(t)
        res = s+'a'
        l = 0
        hashmapC = Counter()
        needToMatch = len(hashmapT)
        for r in range(len(s)):
            hashmapC[s[r]] += 1
            needToMatch -= hashmapC[s[r]] == hashmapT[s[r]]
            while needToMatch == 0:
                if r - l + 1 < len(res):
                    res = s[l:r+1]
                needToMatch += hashmapC[s[l]] == hashmapT[s[l]]
                hashmapC[s[l]] -= 1
                l += 1
        return res if len(res) != len(s)+1 else ''

Stack

Valid Parentheses

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) & 1:
            return False
            
        hashmap = {
            ']':'[',
            ')':'(',
            '}':'{'
        }

        stack = []
        for c in s:
            if c not in hashmap:
                stack.append(c)
            elif stack and stack[-1] == hashmap[c]:
                stack.pop()
            else:
                return False
        return not stack

Binary Search

Find Minimum in Rotated Sorted Array

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

Search in Rotated Sorted Array

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l+r)//2
            if nums[mid] == target: return mid
            if nums[l] <= nums[mid]: #left sorted [1,2,3,4] or [2,3,4,1]
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else: # right sorted [4, 5, 1, 2, 3] or [5, 1, 2, 3, 4]
                if nums[mid] < target <= nums[r] :
                    l = mid + 1
                else:
                    r = mid - 1
        return -1

Linked List

Reverse Linked List

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

Merge 2 Sorted Lists

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = cur = ListNode()
        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
        if list2:
            cur.next = list2
        return head.next

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        prev, cur = None, slow.next
        slow.next = None
        while cur:
            temp = cur.next
            cur.next = prev
            prev = cur
            cur = temp
        first, second = head, prev
        while first and second:
            temp1, temp2 = first.next, second.next
            first.next = second
            second.next = temp1
            first, second = temp1, temp2

Remove Nth Node From End Of List

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        Dummy = ListNode(0, head)
        fast = head
        while n:
            fast = fast.next
            n -= 1
        
        slow = Dummy
        while fast:
            fast = fast.next
            slow = slow.next
        
        slow.next = slow.next.next
        return Dummy.next

Linked List Cycle

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

Merge K Sorted Lists

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) < 2:
            return lists[0] if lists else None
        mid = len(lists) // 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return self.merge(left, right)

    def merge(self, a, b):
        cur = Dummy = ListNode()
        while a and b:
            if a.val > b.val:
                cur.next = b
                b = b.next
            else:
                cur.next = a
                a = a.next
            cur = cur.next
        if a:
            cur.next = a
        if b:
            cur.next = b
        return Dummy.next

Tree

Invert Binary Tree

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

Maximum Depth of Binary Tree

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        q = []
        if root:
            q = [root]
        res = 0
        while q:
            nQ = []
            res += 1
            for cur in q:
                if cur.left:
                    nQ.append(cur.left)
                if cur.right:
                    nQ.append(cur.right)
            q = nQ
        return res

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p or not q:
            return not p and not q
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Subtree of Another Tree

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def dfs(a, b):
            if not b:
                return True
            if not a:
                return False
            if a.val == b.val and self.isSameTree(a, b):
                return True
            return dfs(a.left, subRoot) or dfs(a.right, subRoot)
        return dfs(root, subRoot)
    
    def isSameTree(self, a, b):
        if not a and not b:
            return True
        if a and b and a.val == b.val:
            return self.isSameTree(a.left, b.left) and self.isSameTree(a.right, b.right) 
        return False

Lowest Common Ancestor BS Tree

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.p, self.q = min(p.val, q.val), max(p.val, q.val)
        def dfs(node):
            if  self.p <= node.val <= self.q:
                return node
            if node.val < self.p:
                return dfs(node.right)
            return dfs(node.left)
        return dfs(root)

BTree Level Order Traversal

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

Validate BS Tree

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(left, node, right):
            if not node:
                return True
            if not left < node.val < right:
                return False
            return dfs(left, node.left, node.val) and dfs(node.val, node.right, right)
        return dfs(-math.inf, root, math.inf)

Kth Smallest Element in BS-Tree

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        cur = root
        while k:
            while cur:
                stack.append(cur)
                cur = cur.left
            newCur = stack.pop()
            k -= 1
            if k == 0:
                return newCur.val
            cur = newCur.right

Construct B-Tree From Preorder and Inorder Traversal

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:        
        H = {n:i for i, n in enumerate(inorder)}
        N = len(preorder)
        
        def dfs(start, end, i):
            if start > end:
                return None, i
            node = TreeNode(preorder[i])
            indx = H[node.val]
            node.left, i = dfs(start, indx-1, i + 1)
            node.right, i = dfs(indx+1,end, i)
            return node, i
        
        return dfs(0, N-1, 0)[0]

B-Tree Maximum Path Sum

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return [-inf, 0]
            left = dfs(node.left)
            right = dfs(node.right)
            a, b = max(0, left[1]), max(0, right[1])
            return max(left[0], a+node.val+b, right[0]), max(a+node.val, b+node.val)
        return dfs(root)[0]

Serialize and Deserialize BTree

class Codec:
    def serialize(self, root):
        res = []
        def dfs(node):
            if not node:
                res.append('N')
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ','.join(res)

    def deserialize(self, data):
        data = data.split(',')
        self.i = 0
        def dfs():
            if data[self.i] == 'N':
                self.i += 1
                return
            node = TreeNode(int(data[self.i]))
            self.i += 1
            node.left = dfs()
            node.right = dfs()
            return node
        return dfs()

Heap

Find Median From data-stream

class MedianFinder:
    def __init__(self):
        self.left = []
        self.right = []

    def addNum(self, num: int) -> None:
        heappush(self.left, -num)
        
        if len(self.left) - 1 > len(self.right):
            n = -heappop(self.left)
            heappush(self.right, n)
            
        if self.right and self.right[0] < -self.left[0]:
            n1 = heappop(self.left)
            n2 = heappop(self.right)
            heappush(self.left, -n2)
            heappush(self.right, -n1)
            
    def findMedian(self) -> float:
        if (len(self.left) + len(self.right)) % 2: #Odd
            return -self.left[0]
        return (-self.left[0] + self.right[0])/2

Backtracking

Combination Sum

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        def dfs(i, curSum, sub):
            if curSum >= target or i >= len(candidates):
                if curSum == target:
                    res.append(sub[:])
                return
            dfs(i, curSum + candidates[i], sub + [candidates[i]])
            dfs(i+1, curSum, sub)
        dfs(0, 0, [])
        return res

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        row, col = len(board), len(board[0])
        N = len(word)

        def go(i, r, c):
            if i == N:
                return True
            if not(-1 < r < row and -1 < c < col and board[r][c] == word[i]):
                return False
            ch = board[r][c]
            board[r][c] = "-"
            res = go(i+1, r-1,c) or go(i+1, r,c+1) or go(i+1, r,c-1) or go(i+1, r+1,c)
            board[r][c] = ch
            return res
        
        for r in range(row):
            for c in range(col):
                if go(0, r, c):
                    return True
        return False

Tries

Implement Trie Prefix Tree

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur:
                cur[c] = {}
            cur = cur[c]
        cur["#"] = {}

    def search(self, word: str) -> bool:
        cur = self.root
        for c in word:
            if c not in cur:
                return False
            cur = cur[c]
        return '#' in cur
        
    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for c in prefix:
            if c not in cur:
                return False
            cur = cur[c]
        return True

Design Add And Search Words Data Structure

class WordDictionary:
    def __init__(self):
        self.root = {}

    def addWord(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur:
                cur[c] = {}
            cur = cur[c]
        cur['1'] = {}
        

    def search(self, word: str) -> bool:
        def dfs(i, cur):
            if i == len(word):
                return '1' in cur
            if word[i] == '.':
                for k in cur:
                    if dfs(i+1, cur[k]):
                        return True
                return False
            return word[i] in cur and dfs(i+1, cur[word[i]])
        return dfs(0, self.root)

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        A = {}
        for w in words:
            cur = A
            for c in w:
                if c not in cur:
                    cur[c] = {}
                cur = cur[c]
            cur['#'] = w
        
        def dfs(r, c, cur):
            if not (-1 < r < row and -1 < c < col and board[r][c] in cur):
                return []
            ch = board[r][c]
            board[r][c] = '-'
            res = []
            if '#' in cur[ch]:
                res += [cur[ch]['#']]
            
            for dr, dc in [(r-1, c), (r, c+1), (r+1, c), (r, c-1)]:
                res += dfs(dr, dc, cur[ch])

            board[r][c] = ch
            return res
        
        row, col = len(board), len(board[0])
        res = []
        for r in range(row):
            for c in range(col):
                res += dfs(r, c, A)
        return list(set(res))

Graph

Number of Islands

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        row, col = len(grid), len(grid[0])
        res = 0

        def dfs(r, c):
            if not (-1 < r < row and -1 < c < col and grid[r][c] == '1'):
                return
            grid[r][c] = '0'
            for dr, dc in [(r-1, c), (r, c+1), (r+1, c), (r, c-1)]:
                dfs(dr, dc)
        
        for r in range(row):
            for c in range(col):
                if grid[r][c] == '1':
                    res += 1
                    dfs(r, c)
        return res

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

Pacific Atlantic Water Flow

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        visitedA = set()
        visitedP = set()
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        def dfs(prev, r, c, state):
            if not(-1 < r < row and -1 < c < col and (r, c) not in state and heights[r][c] >= prev):
                return
            prev = heights[r][c]
            state.add((r, c))
            for dr, dc in directions:
                dfs(prev, dr+r, dc+c, state)

        row, col = len(heights), len(heights[0])
        for r in range(row):
            dfs(-inf, r, 0, visitedP)
            dfs(-inf, r, col-1, visitedA)

        for c in range(col):
            dfs(-inf, 0, c, visitedP)
            dfs(-inf, row-1, c, visitedA)


        res = []
        for k in visitedA:
            if k in visitedP:
                res.append(k)
        return res

Course Schedule

class Solution:
    def canFinish(self, N: int, pre: List[List[int]]) -> bool:
        adj = defaultdict(list)
        for u, v in pre:
            adj[u].append(v)
        visited = [N+1] * N
        def dfs(node):
            if visited[node] == N+1:
                visited[node] = False #cycle
                for nei in adj[node]:
                    if not dfs(nei):
                        return False
                visited[node] = True #valid
            return visited[node]
        for n in range(N):
            if not dfs(n):
                return False
        return True

Graph Valid Tree

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        adj = defaultdict(list)
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        
        visited = set()
        q = [[-1, 0]] # par, node
        while q:
            newQ = []
            for par, node in q:
                if node in visited:
                    return False
                visited.add(node)
                for nei in adj[node]:
                    if par == nei: continue
                    newQ.append([node, nei])
            q = newQ
        return len(visited) == n

No of Connected Compenents In An Undirected Graph

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        visit = [False] * n
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        def dfs(node):
            for nei in adj[node]:
                if not visit[nei]:
                    visit[nei] = True
                    dfs(nei)
        
        res = 0
        for node in range(n):
            if not visit[node]:
                visit[node] = True
                dfs(node)
                res += 1
        return res

Advance Graph

Alien Dictionary

class Solution:
    def foreignDictionary(self, words: List[str]) -> str:
        adj = defaultdict(set)

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            minLen = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
                return ""
            for j in range(minLen):
                if w1[j] != w2[j]:
                    adj[w1[j]].add(w2[j])
                    break

        visited = {}
        res = []

        def dfs(char):
            if char in visited:
                return visited[char]

            visited[char] = True

            for neighChar in adj[char]:
                if dfs(neighChar):
                    return True

            visited[char] = False
            res.append(char)

        for char in adj:
            if dfs(char):
                return ""

        res.reverse()
        return "".join(res)

1D Programming

Climbing Stairs

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

class Solution:
    def rob(self, nums: List[int]) -> int:
        a, b = 0, 0
        for n in nums:
            temp = b
            b = max(a+n, b)
            a = temp
        return b

class Solution:
    def rob(self, nums: List[int]) -> int:
        def go(nums):
            bag1 = bag2 = 0
            for n in nums:
                temp = bag1
                bag1 = max(bag1, bag2 + n)
                bag2 = temp
            return bag1
        return max(go(nums[:-1]), go(nums[1:]), nums[0])

Longest Palindrome Substring

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def check(l, r):
            while -1 < l and r < N and s[l] == s[r]:
                l -= 1
                r += 1
            return l+1, r-1
            
        res = ''
        N = len(s)
        for i in range(N):
            l, r = check(i, i)
            if len(res) < r - l + 1:
                res = s[l:r+1]
            l, r = check(i, i+1)
            if len(res) < r - l + 1:
                res = s[l:r+1]
        return res

Palindrome Substring

class Solution:
    def countSubstrings(self, s: str) -> int:
        def check(l, r):
            cur = 0
            while -1 < l and r < N and s[l] == s[r]:
                cur += 1
                l -= 1
                r += 1
            return cur
        
        res = 0
        N = len(s)
        for i in range(N):
            res += check(i, i) + check(i, i+1)
        return res

class Solution:
    def numDecodings(self, s: str) -> int:
        cache = {len(s):1}
        def dfs(i):
            if i in cache:
                return cache[i]
            if s[i] == '0':
                return 0
            res = dfs(i+1)
            if i+1 < len(s) and (0 < int(s[i:i+2]) < 27):
                res += dfs(i+2)
            cache[i] = res
            return res
        return dfs(0)

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

Maximum Product Subarray

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = -inf
        a = b = 1
        for n in nums:
            tempA = a*n
            tempB = b*n
            a = max(tempA, tempB ,n)
            b = min(tempA, tempB ,n)
            res = max(a, res)
        return res

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        N = len(s)
        dp = [False] * (N+1)
        dp[-1] = True
        
        for i in range(N-1, -1, -1):
            for w in wordDict:
                L = len(w)
                if s[i:i+L] == w:
                    dp[i] |= dp[i+L]
        return dp[0]

Longest Increasing Subsequence

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        N = len(s)
        dp = [False] * (N+1)
        dp[-1] = True
        
        for i in range(N-1, -1, -1):
            for w in wordDict:
                L = len(w)
                if s[i:i+L] == w:
                    dp[i] |= dp[i+L]
        return dp[0]

2D Programming

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
        for _ in range(m-1):
            newDp = [1] * n
            for c in range(n-2, -1, -1):
                newDp[c] = dp[c] + newDp[c+1]
            dp = newDp
        return dp[0]

Longest Common Subsequence

class Solution:
    def longestCommonSubsequence(self, t1: str, t2: str) -> int:
        dp = [[0] * (len(t2)+1) for _ in range(len(t1)+1)]
        for i in range(len(t1)-1, -1, -1):
            for j in range(len(t2)-1, -1, -1):
                if t1[i] == t2[j]:
                    dp[i][j] = 1 + dp[i+1][j+1]
                else:
                    dp[i][j] = max(dp[i][j+1], dp[i+1][j])
        return dp[0][0]

Greedy

Maximum Subarray
Jump Game

Intervals

Insert Intervals
Merge Intervals
Non Overlapping Intervals
Meeting Room
Meeting Room 2

Math & Geometry

Rotate Image
Spiral Matrix
Set Matrix Zeroes

Bit Manipulation

Number of 1 Bits
Counting Bits
Reverse Bits
Missing Number
Sum of 2 Integer