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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

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

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

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

# 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

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

# 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

# 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

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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

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

# 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

# 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

# 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

# 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

# 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(",")))

---