Curated List of Top 75 LeetCode

LeetCodeQuestions.md

Array

• Two Sum
• Best Time to Buy and Sell Stock
• Contains Duplicate
• Product of Array Except Self
• Maximum Subarray
• Maximum Product Subarray
• Find Minimum in Rotated Sorted Array
• Search in Rotated Sorted Array
• 3Sum
• Container With Most Water

---

Binary

• Sum of Two Integers
• Number of 1 Bits
• Counting Bits
• Missing Number
• Reverse Bits

---

Dynamic Programming

• Climbing Stairs
• Coin Change
• Longest Increasing Subsequence
• Longest Common Subsequence
• Word Break Problem
• Combination Sum
• House Robber
• House Robber II
• Decode Ways
• Unique Paths
• Jump Game

---

Graph

• Clone Graph
• Course Schedule
• Pacific Atlantic Water Flow
• Number of Islands
• Longest Consecutive Sequence
• Alien Dictionary (Leetcode Premium)
• Graph Valid Tree (Leetcode Premium)
• Number of Connected Components in an Undirected Graph (Leetcode Premium)

---

Interval

• Insert Interval
• Merge Intervals
• Non-overlapping Intervals
• Meeting Rooms (Leetcode Premium)
• Meeting Rooms II (Leetcode Premium)

---

Linked List

• Reverse a Linked List
• Detect Cycle in a Linked List
• Merge Two Sorted Lists
• Merge K Sorted Lists
• Remove Nth Node From End Of List
• Reorder List

---

Matrix

• Set Matrix Zeroes
• Spiral Matrix
• Rotate Image
• Word Search

---

String

• Longest Substring Without Repeating Characters
• Longest Repeating Character Replacement
• Minimum Window Substring
• Valid Anagram
• Group Anagrams
• Valid Parentheses
• Valid Palindrome
• Longest Palindromic Substring
• Palindromic Substrings
• Encode and Decode Strings (Leetcode Premium)

---

Tree

• Maximum Depth of Binary Tree
• Same Tree
• Invert/Flip Binary Tree
• Binary Tree Maximum Path Sum
• Binary Tree Level Order Traversal
• Serialize and Deserialize Binary Tree
• Subtree of Another Tree
• Construct Binary Tree from Preorder and Inorder Traversal
• Validate Binary Search Tree
• Kth Smallest Element in a BST
• Lowest Common Ancestor of BST
• Implement Trie (Prefix Tree)
• Add and Search Word
• Word Search II

---

Heap

• Merge K Sorted Lists
• Top K Frequent Elements
• Find Median from Data Stream

string convertions and validations

• String to Integer (atoi)
• Integer to English Words
• Valid Number

Important Link:

14 Patterns to Ace Any Coding Interview Question

Implement Trie (Prefix Tree)
my soln

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = {}
        
        
    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.trie
        for c in word:
            if c in node:
                node = node[c]
            else:
                node[c] = {}
                node = node[c]
        node['$'] = True
        
            
    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        def dfs(node, word, i):
            if i == len(word):
                if '$' in node:
                    return True
                return False
            char = word[i]
            if char in node:
                return dfs(node[char], word, i+1)
            return False
        return dfs(self.trie, word, 0)
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        def dfs(node, prefix, i):
            if i == len(prefix):
                return True
            
            char = prefix[i]
            if char in node:
                return dfs(node[char], prefix, i+1)
            return False
        return dfs(self.trie, prefix, 0)

Add and Search Word
my soln

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = {}
        

    def addWord(self, word: str) -> None:
        node = self.trie
        for c in word:
            node[c] = node.get(c, {})
            node = node[c]
        node['$'] = True
            
        

    def search(self, word: str) -> bool:
        def dfs(node, word, i):
            if i == len(word):
                if '$' in node:
                    return True
                return False
            
            char = word[i]
            if char == '.':
                for char, child in node.items():
                    if char != '$' and dfs(child, word, i+1):
                        return True
                return False
            elif char in node:
                return dfs(node[char],word, i+1)
            return False
        return dfs(self.trie, word, 0)

Alien Dictionary
topological sort: https://www.youtube.com/watch?v=ddTC4Zovtbc

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        self.graph = defaultdict(set)
        
        # add all unique chars as node to graph
        for w in words:
            for c in w:
                self.graph[c]
        
        # find the orders
        for i in range(1, len(words)):
            w1 = words[i-1]
            w2 = words[i]
            shorterlen = min(len(w1), len(w2))
            found_order = False
            for j in range(shorterlen):
                if w1[j] != w2[j]:
                    found_order = True
                    self.graph[w1[j]].add(w2[j])
                    break
            if not found_order and len(w1) > len(w2):
                return ""
       
        # topo sort
        self.seen = set()
        self.stack = []
        self.has_cycle = False
        
        def dfs(char, seen_path):
            # check if have cycle
            if char in seen_path:
                self.has_cycle = True
                return
            
            if char in self.seen:
                return
            
            seen_path.add(char)
            for child in self.graph[char]:
                dfs(child, seen_path)
            seen_path.remove(char)
            self.seen.add(char)
            self.stack.append(char)
        
        for char in self.graph:
            dfs(char, set())
            if self.has_cycle:
                return ""
        return ''.join(self.stack[::-1])

Merge K Sorted Lists

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        for idx, headlistnode in enumerate(lists):
            if headlistnode:
                heap.append((headlistnode.val, idx))
        
        # sort asc accourding to list node val
        heapq.heapify(heap)
        # dummy node
        head = ListNode()
        cur = head
        while heap:
            min_val, idx = heapq.heappop(heap)
            new_node = ListNode(min_val)
            cur.next = new_node
            cur = cur.next
            
            # push next val from idx list onto heap
            push_node = lists[idx] = lists[idx].next
            if push_node:
                heapq.heappush(heap, (push_node.val, idx))
        return head.next

String to Integer (atoi)
https://leetcode.com/submissions/detail/574279356/