---
title: "DSA SHEET"
category: "dsa"
summary: "Source: https://www.risingbrain.org/sheet Scraped: using python"
date: "2026-01-20"
---

#  DSA SHEET EXTRACTED


**Source:** https://www.risingbrain.org/sheet
**Scraped:** using python 

##  DSA PATTERNS
1. **Array**
2. **Strings**
3. **Binary Search**
4. **Stack**
5. **Linked List**
6. **Double Linked List**
7. **HashMap**
8. **Heap**
9. **Recursion**
10. **Tree**
11. **Binary Search Tree**
12. **Graph**
13. **Backtracking**
14. **Greedy**
15. **Trie**
16. **Bit Manipulation**
17. **Sliding Window (String)**
18. **Classic Binary Search**
19. **Binary Search on Answers**
20. **Monotonic Stack**
21. **Stack Simulation / Undo Operation**
22. **Stack-Based Design**
23. **Recursive Stack**
24. **Linked List + Stack**
25. **Sliding Window + HashMap**


# DSA Topics - Code Examples

---

### **1. Array**

**Theory**  
An array is a linear data structure that stores elements in contiguous memory locations. It allows **O(1)** access to elements via indexing but has fixed size, requiring resizing for dynamic operations.

**Code Example**

```python
# Kadane's Algorithm: Find maximum subarray sum
def max_subarray_sum(nums):
    max_sum = current_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

# Test
print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # Output: 6
```

---

### **2. Strings**

**Theory**  
A string is a sequence of characters. Common operations include substring manipulation, pattern matching, and palindrome checks.

**Code Example**

```python
# Check if a string is a palindrome
def is_palindrome(s):
    s = ''.join(c.lower() for c in s if c.isalnum())
    return s == s[::-1]

# Test
print(is_palindrome("A man, a plan, a canal: Panama"))  # Output: True
```

---

### **3. Binary Search**

**Theory**  
Binary search is a divide-and-conquer algorithm that achieves **O(log n)** time complexity on sorted arrays.

**Code Example**

```python
# Classic binary search
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        low = mid + 1 if arr[mid] < target else low
        high = mid - 1 if arr[mid] > target else high
    return -1

# Test
print(binary_search([1, 3, 5, 7, 9], 5))  # Output: 2
```

---

### **4. Stack**

**Theory**  
A stack is a **LIFO (Last In, First Out)** data structure supporting push, pop, and peek operations.

**Code Example**

```python
# Simple stack implementation
class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, val):
        self.items.append(val)
    
    def pop(self):
        return self.items.pop() if self.items else None
    
    def peek(self):
        return self.items[-1] if self.items else None

# Test
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop())  # Output: 2
```

---

### **5. Linked List**

**Theory**  
A linked list consists of nodes with values and pointers to the next node. Allows efficient insertions/deletions with **O(n)**access time.

**Code Example**

```python
# Detect cycle in linked list (Floyd's Algorithm)
class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
```

---

### **6. Double Linked List**

**Theory**  
A doubly linked list allows bidirectional traversal with **prev** and **next** pointers. Useful for efficient deletions and LRU caches.

**Code Example**

```python
# Doubly linked list node
class DoublyNode:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

def insert_at_end(head, val):
    new_node = DoublyNode(val)
    if not head:
        return new_node
    current = head
    while current.next:
        current = current.next
    current.next = new_node
    new_node.prev = current
    return head
```

---

### **7. HashMap**

**Theory**  
A hash map stores key-value pairs with **O(1)** average lookup and insertion time. Used for frequency counting and caching.

**Code Example**

```python
# Count character frequencies
def count_chars(s):
    return {char: s.count(char) for char in set(s)}

# Or using get()
def count_chars_alt(s):
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    return freq

# Test
print(count_chars("hello"))  # Output: {'h': 1, 'e': 1, 'l': 2, 'o': 1}
```

---

### **8. Heap**

**Theory**  
A heap is a priority queue where parent nodes are greater (max-heap) or smaller (min-heap) than children.

**Code Example**

```python
import heapq

# Find k largest elements
def k_largest(nums, k):
    return heapq.nlargest(k, nums)

# Find k smallest elements
def k_smallest(nums, k):
    return heapq.nsmallest(k, nums)

# Test
print(k_largest([3, 1, 4, 1, 5, 9], 3))  # Output: [9, 5, 4]
```

---

### **9. Recursion**

**Theory**  
Recursion solves problems by breaking them into smaller subproblems with a base case and recursive case.

**Code Example**

```python
from functools import lru_cache

# Fibonacci with memoization
@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Test
print(fibonacci(10))  # Output: 55
```

---

### **10. Tree**

**Theory**  
A tree is a hierarchical structure with a root and child nodes. Supports DFS, BFS traversals.

**Code Example**

```python
from collections import deque

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

# BFS traversal
def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result
```

---

### **11. Binary Search Tree (BST)**

**Theory**  
A BST enforces **left < root < right** property. Supports insertion, search with **O(h)** complexity.

**Code Example**

```python
# Insert into BST
def insert_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    return root

# Search in BST
def search_bst(root, val):
    if not root:
        return None
    if root.val == val:
        return root
    return search_bst(root.left if val < root.val else root.right, val)
```

---

### **12. Graph**

**Theory**  
Graphs consist of nodes and edges. Representations: adjacency list (sparse) and adjacency matrix (dense).

**Code Example**

```python
from collections import deque, defaultdict

# BFS traversal
def bfs_graph(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Test
graph = defaultdict(list)
graph[0] = [1, 2]
graph[1] = [2]
graph[2] = [3]
graph[3] = []
```

---

### **13. Backtracking**

**Theory**  
Backtracking explores all possible solutions recursively, pruning invalid paths.

**Code Example**

```python
# Generate all subsets
def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

# Test
print(subsets([1, 2]))  # Output: [[], [1], [1, 2], [2]]
```

---

### **14. Greedy**

**Theory**  
Greedy algorithms make locally optimal choices at each step (e.g., activity selection, coin change).

**Code Example**

```python
# Activity selection problem
def activity_selection(activities):
    # Sort by end time
    activities.sort(key=lambda x: x[1])
    selected = [activities[0]]
    for i in range(1, len(activities)):
        if activities[i][0] >= selected[-1][1]:
            selected.append(activities[i])
    return selected

# Test
acts = [(0, 5), (1, 3), (2, 4), (4, 7)]
print(activity_selection(acts))  # Output: [(0, 5), (4, 7)]
```

---

### **15. Trie**

**Theory**  
A trie is a tree structure for storing strings. Each node represents a character. Used for autocomplete and prefix searches.

**Code Example**


```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
```

---

### **16. Bit Manipulation**

**Theory**  
Bit manipulation works directly with binary representations using XOR, AND, OR, and shifts.

**Code Example**

```python
# Find single number (all others appear twice)
def single_number(nums):
    return sum(set(nums)) * 2 - sum(nums)

# Or using XOR
def single_number_xor(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

# Test
print(single_number([1, 2, 2, 3, 3]))  # Output: 1
```

---

### **17. Sliding Window (String)**

**Theory**  
Sliding window maintains a window of characters and adjusts size to satisfy constraints (e.g., unique characters).

**Code Example**

```python
# Longest substring without repeating characters
def length_longest_substring(s):
    char_index = {}
    max_length = start = 0
    for end, char in enumerate(s):
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1
        char_index[char] = end
        max_length = max(max_length, end - start + 1)
    return max_length

# Test
print(length_longest_substring("abcabcbb"))  # Output: 3
```

---

### **18. Classic Binary Search**

**Theory**  
Binary search on sorted arrays by comparing target with middle element and narrowing search space.

**Code Example**


```python
# Binary search template
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Test
print(binary_search([1, 3, 5, 7, 9], 7))  # Output: 3
```

---

### **19. Binary Search on Answers**

**Theory**  
Treat answer space as sorted and binary search to find optimal value (minimum/maximum feasible).

**Code Example**


```python
# Minimum days to eat oranges
def minimumDays(n):
    def can_finish(days):
        return n <= days * 2  # Simplified check
    
    low, high = 1, n
    while low < high:
        mid = (low + high) // 2
        if can_finish(mid):
            high = mid
        else:
            low = mid + 1
    return low
```

---

### **20. Monotonic Stack**

**Theory**  
Monotonic stacks maintain elements in increasing/decreasing order. Used for next greater element, histogram problems.

**Code Example**


```python
# Next greater element for each element
def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []
    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    return result

# Test
print(next_greater_element([1, 2, 1]))  # Output: [2, -1, -1]
```

---

### **21. Stack Simulation / Undo Operation**

**Theory**  
Use a stack to simulate operations like undo/redo by pushing and popping elements.

**Code Example**


```python
# Simple undo operation
class TextEditor:
    def __init__(self):
        self.text = []
    
    def type(self, char):
        self.text.append(char)
    
    def undo(self):
        if self.text:
            self.text.pop()
    
    def get_text(self):
        return ''.join(self.text)

# Test
editor = TextEditor()
editor.type('a')
editor.type('b')
editor.undo()
print(editor.get_text())  # Output: a
```

---

### **22. Stack-Based Design**

**Theory**  
Use multiple stacks to implement other data structures or maintain extra information (e.g., min tracking).

**Code Example**

```python
# Stack with O(1) max retrieval
class MaxStack:
    def __init__(self):
        self.stack = []
        self.max_stack = []
    
    def push(self, val):
        self.stack.append(val)
        if not self.max_stack or val >= self.max_stack[-1]:
            self.max_stack.append(val)
    
    def pop(self):
        if self.stack.pop() == self.max_stack[-1]:
            self.max_stack.pop()
    
    def get_max(self):
        return self.max_stack[-1] if self.max_stack else None
```

---

### **23. Recursive Stack**

**Theory**  
Recursion uses a call stack to process elements. Reverse linked lists, process top element then recurse.

**Code Example**

```python
# Reverse linked list recursively
def reverse_list(head):
    if not head or not head.next:
        return head
    new_head = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return new_head
```

---

### **24. Linked List + Stack**

**Theory**  
Combine linked lists with stacks for backward traversal (e.g., next greater node).

**Code Example**

```python
# Next greater node in linked list
def next_greater_node(head):
    stack = []
    current = head
    while current:
        while stack and current.val > stack[-1][0]:
            val, node = stack.pop()
            node.next_val = current.val
        stack.append((current.val, current))
        current = current.next
    return head
```

---

### **25. Sliding Window + HashMap**

**Theory**  
Maintain a sliding window with hashmap to track character frequencies and adjust window size.

**Code Example**

```python
# Longest substring with all unique characters
def longest_unique(s):
    char_map = {}
    max_len = left = 0
    for right, char in enumerate(s):
        char_map[char] = char_map.get(char, 0) + 1
        while char_map[char] > 1:
            char_map[s[left]] -= 1
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

# Test
print(longest_unique("abcabcbb"))  # Output: 3
```

---

### **26. Heap with Sliding Window**

**Theory**  
Maintain a heap of window elements to track maximum/minimum. Remove outdated elements.

**Code Example**

```python
import heapq

# Sliding window maximum
def sliding_window_max(nums, k):
    if not nums or k <= 0:
        return []
    max_heap = [(-nums[i], i) for i in range(k)]
    heapq.heapify(max_heap)
    result = [-max_heap[0][0]]
    
    for i in range(k, len(nums)):
        heapq.heappush(max_heap, (-nums[i], i))
        while max_heap[0][1] <= i - k:
            heapq.heappop(max_heap)
        result.append(-max_heap[0][0])
    return result

# Test
print(sliding_window_max([1, 3, 1, 2, 0, 5], 3))  # Output: [3, 3, 2, 5]
```

---

### **27. Implementation of Heap**

**Theory**  
Heap is implemented using arrays. For max-heap/min-heap, parent >= children or parent <= children.

**Code Example**

```python
# Min-heap from scratch
class MinHeap:
    def __init__(self):
        self.heap = []
    
    def push(self, val):
        self.heap.append(val)
        self._bubble_up(len(self.heap) - 1)
    
    def pop(self):
        if len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._bubble_down(0)
        return root
    
    def _bubble_up(self, i):
        parent = (i - 1) // 2
        if i > 0 and self.heap[i] < self.heap[parent]:
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            self._bubble_up(parent)
    
    def _bubble_down(self, i):
        smallest = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self._bubble_down(smallest)
```

---

### **28. Linear Recursion**

**Theory**  
Linear recursion reduces problem size by one at each step. Time complexity: **O(n)**.

**Code Example**


```python
# Factorial
def factorial(n):
    return 1 if n == 0 else n * factorial(n - 1)

# Sum of array
def sum_array(arr):
    return 0 if not arr else arr[0] + sum_array(arr[1:])

# Test
print(factorial(5))  # Output: 120
print(sum_array([1, 2, 3, 4]))  # Output: 10
```

---

### **29. Recursive String Processing**

**Theory**  
Process substrings recursively (palindrome checks, substring counts).

**Code Example**

```python
# Check palindrome recursively
def is_palindrome_rec(s, left=0, right=None):
    if right is None:
        right = len(s) - 1
    if left >= right:
        return True
    return s[left] == s[right] and is_palindrome_rec(s, left + 1, right - 1)

# Test
print(is_palindrome_rec("racecar"))  # Output: True
```

---

### **30. Choice-Based Backtracking**

**Theory**  
Generate all combinations, subsets, or permutations by making choices and backtracking.

**Code Example**


```python
# All permutations
def permute(nums):
    result = []
    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for num in nums:
            if num not in path:
                path.append(num)
                backtrack(path)
                path.pop()
    backtrack([])
    return result

# Test
print(permute([1, 2]))  # Output: [[1, 2], [2, 1]]
```

---

### **31. Constraint-Based Backtracking**

**Theory**  
Choose whether to include an element while satisfying constraints (subset sum, valid parentheses).

**Code Example**


```python
# Subset sum
def subset_sum(nums, target):
    result = []
    def backtrack(start, path, current_sum):
        if current_sum == target:
            result.append(path[:])
            return
        if current_sum > target or start >= len(nums):
            return
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path, current_sum + nums[i])
            path.pop()
    backtrack(0, [], 0)
    return result

# Test
print(subset_sum([1, 2, 3], 3))  # Output: [[1, 2], [3]]
```

---

### **32. Grid / Path Backtracking**

**Theory**  
Explore all valid paths in a grid recursively (maze traversal, pathfinding).

**Code Example**

```python
# Paths in grid from (0,0) to (m-1,n-1)
def paths_in_grid(m, n):
    result = []
    def dfs(x, y, path):
        if x == m - 1 and y == n - 1:
            result.append(path)
            return
        if x + 1 < m:
            dfs(x + 1, y, path + "D")
        if y + 1 < n:
            dfs(x, y + 1, path + "R")
    dfs(0, 0, "")
    return result

# Test
print(paths_in_grid(2, 2))  # Output: ['DD', 'DR', 'RD', 'RR']
```

---

### **33. Decision Tree / Sequence Generation**

**Theory**  
Generate sequences recursively by making choices at each step (binary strings, letter combinations).

**Code Example**

```python
# All binary strings of length n
def binary_strings(n):
    result = []
    def generate(current):
        if len(current) == n:
            result.append(current)
            return
        generate(current + "0")
        generate(current + "1")
    generate("")
    return result

# Test
print(binary_strings(2))  # Output: ['00', '01', '10', '11']
```

---

### **34. 1D / Linear DP**

**Theory**  
Use a 1D array to track optimal solutions for sequences, sums, or counts.

**Code Example**

```python
# Minimum coins for target amount
def min_coins(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# Test
print(min_coins([1, 2, 5], 5))  # Output: 1
```

---

### **35. 2D / Grid DP**

**Theory**  
Use a 2D array to track states for rows/columns (minimum path, unique paths).

**Code Example**

```python
# Minimum path sum in grid
def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            dp[i][j] = grid[i][j] + min(
                dp[i-1][j] if i > 0 else float('inf'),
                dp[i][j-1] if j > 0 else float('inf')
            )
    return dp[m-1][n-1]

# Test
print(min_path_sum([[1, 3], [2, 1]]))  # Output: 4
```

---

### **36. DP on Strings**

**Theory**  
Use 2D DP for substring/subsequence problems (LCS, edit distance, palindromes).

**Code Example**

```python
# Longest common subsequence
def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

# Test
print(lcs("abcde", "ace"))  # Output: 3
```

---

### **37. DP on Intervals**

**Theory**  
Track optimal solutions for subarrays/intervals (matrix chain, balloon burst).

**Code Example**

```python
# Burst balloons with maximum coins
def burst_balloons(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    
    for length in range(3, n + 1):
        for left in range(n - length + 1):
            right = left + length - 1
            for k in range(left + 1, right):
                coins = nums[left] * nums[k] * nums[right]
                dp[left][right] = max(dp[left][right], 
                                      dp[left][k] + coins + dp[k][right])
    return dp[0][n-1]

# Test
print(burst_balloons([3, 1, 5, 8]))  # Complex output based on burst sequence
```

---

### **38. DP on Trees / DAGs**

**Theory**  
Use recursion + memoization for tree-based DP (tree diameter, house robber on trees).

**Code Example**

```python
# Tree diameter
def tree_diameter(root):
    def dfs(node):
        if not node:
            return 0, 0
        left_h, left_d = dfs(node.left)
        right_h, right_d = dfs(node.right)
        height = 1 + max(left_h, right_h)
        diameter = max(left_d, right_d, left_h + right_h)
        return height, diameter
    
    _, diameter = dfs(root)
    return diameter
```

---

### **39. Basic Trie Operations**

**Theory**  
Insert, search, and delete operations in a trie for efficient prefix/word searches.

**Code Example**

```python
# Trie with search and startsWith
class Trie:
    def __init__(self):
        self.root = {}
    
    def insert(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node['$'] = True
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return '$' in node
    
    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True
```

---

### **40. Bitwise Trie / XOR**

**Theory**  
Use trie for binary representations to efficiently find maximum/minimum XOR pairs.

**Code Example**

```python
# Maximum XOR in array
def find_max_xor(nums):
    class BitTrie:
        def __init__(self):
            self.root = {}
        
        def insert(self, num):
            node = self.root
            for i in range(31, -1, -1):
                bit = (num >> i) & 1
                node = node.setdefault(bit, {})
        
        def find_max_xor_with(self, num):
            node, max_xor = self.root, 0
            for i in range(31, -1, -1):
                bit = (num >> i) & 1
                toggle = 1 - bit
                if toggle in node:
                    max_xor |= (1 << i)
                    node = node[toggle]
                else:
                    node = node[bit]
            return max_xor
    
    trie = BitTrie()
    for num in nums:
        trie.insert(num)
    
    return max(trie.find_max_xor_with(num) for num in nums)

# Test
print(find_max_xor([14, 70, 53, 83, 49]))  # Output: 86
```

---

### **41. Basic Bit Operations**

**Theory**  
Use XOR, AND, OR, shifts to solve problems (find missing number, single element).

**Code Example**


```python
# Find missing number in 0 to n
def find_missing(nums):
    n = len(nums)
    xor_all = 0
    for i in range(n + 1):
        xor_all ^= i
    for num in nums:
        xor_all ^= num
    return xor_all

# Count set bits
def count_bits(n):
    return [bin(i).count('1') for i in range(n + 1)]

# Test
print(find_missing([0, 1, 3]))  # Output: 2
```

---

### **42. Subsets / Bitmask**

**Theory**  
Use bitmasks to iterate through all subsets (2^n) for combinatorial problems.

**Code Example**



```python
# Generate all subsets using bitmask
def subsets_bitmask(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result

# Test
print(subsets_bitmask([1, 2]))  # Output: [[], [1], [2], [1, 2]]
```

---

### **43. Priority Queue**

**Theory**  
A priority queue (heap) efficiently retrieves highest/lowest priority elements.

**Code Example**



```python
import heapq

# Top K frequent elements
def top_k_frequent(nums, k):
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    return heapq.nlargest(k, freq, key=freq.get)

# Test
print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))  # Output: [1, 2]
```

---

### **44. Trees (General)**

**Theory**  
Trees are hierarchical structures supporting traversal, height calculation, and validation.

**Code Example**

python

Download

Copy code

```python
# Tree height
def tree_height(root):
    if not root:
        return 0
    return 1 + max(tree_height(root.left), tree_height(root.right))

# Inorder traversal
def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

# Test
# Assuming root is a TreeNode
```

---

### **45. Arrays (General)**

**Theory**  
Arrays are fundamental. Use sorting, two-pointer, or sliding window patterns.

**Code Example**

```python
# Two-pointer: find pair with sum
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current = nums[left] + nums[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1
        else:
            right -= 1
    return []

# Test
print(two_sum_sorted([1, 2, 7, 11], 9))  # Output: [0, 3]
```

---

### **46. String (General)**

**Theory**  
Strings are character sequences. Use substring manipulation, hashing, or sliding window.

**Code Example**


```python
# Check anagrams
def are_anagrams(s1, s2):
    return sorted(s1) == sorted(s2)

# Group anagrams
def group_anagrams(words):
    from collections import defaultdict
    groups = defaultdict(list)
    for word in words:
        key = ''.join(sorted(word))
        groups[key].append(word)
    return list(groups.values())

# Test
print(group_anagrams(["eat", "tea", "tan", "ate", "nat"]))
```

---

### **47. Stacks (General)**

**Theory**  
Stacks support LIFO operations. Used for expression evaluation, parentheses matching.

**Code Example**



```python
# Valid parentheses
def is_valid(s):
    stack = []
    pairs = {'(': ')', '{': '}', '[': ']'}
    for char in s:
        if char in pairs:
            stack.append(char)
        elif not stack or pairs[stack.pop()] != char:
            return False
    return not stack

# Test
print(is_valid("()[]{}"))  # Output: True
```

---

### **48. Trees (Serialization)**

**Theory**  
Trees can be serialized/deserialized for storage or transmission.

**Code Example**


```python
# Serialize and deserialize tree
def serialize(root):
    if not root:
        return "null"
    left = serialize(root.left)
    right = serialize(root.right)
    return f"{root.val},{left},{right}"

def deserialize(data):
    def build(nodes):
        val = next(nodes)
        if val == "null":
            return None
        node = TreeNode(int(val))
        node.left = build(nodes)
        node.right = build(nodes)
        return node
    return build(iter(data.split(",")))
```

---