Advanced DSA Patterns

# Adjacency List (most common for interviews)
from collections import defaultdict

graph = defaultdict(list)
edges = [[0,1], [0,2], [1,2], [1,3]]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)    # remove for directed graph

# Weighted graph
graph[u].append((v, weight))

# Adjacency Matrix
n = 4
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1

# Kahn's Algorithm (BFS - preferred for interviews)
from collections import deque, defaultdict

def topological_sort(num_courses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    # Start with nodes that have no prerequisites
    queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) == num_courses:
        return order       # valid ordering
    return []              # cycle exists!

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    # graph[u] = [(v, weight), ...]
    dist = {start: 0}
    heap = [(0, start)]       # (distance, node)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float('inf')):
            continue           # skip outdated entry
        for v, w in graph[u]:
            new_dist = d + w
            if new_dist < dist.get(v, float('inf')):
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))

    return dist  # {node: shortest_distance}

# Example: Network Delay Time
def network_delay(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    dist = dijkstra(graph, k)
    if len(dist) == n:
        return max(dist.values())
    return -1

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False  # already connected
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px           # union by rank
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.components -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

# Detect cycle in undirected graph
def has_cycle(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):
            return True   # already connected = cycle
    return False

def has_cycle_directed(graph, n):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(node):
        color[node] = GRAY        # currently exploring
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return True    # back edge = cycle!
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK       # done with this node
        return False

    for i in range(n):
        if color[i] == WHITE and dfs(i):
            return True
    return False

# Classic 0/1 Knapsack
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]               # skip item
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1])  # take item
    return dp[n][capacity]

# Subset Sum (can we make target?)
def can_sum(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for t in range(target, num - 1, -1):  # reverse!
            dp[t] = dp[t] or dp[t - num]
    return dp[target]

# Partition Equal Subset Sum
def can_partition(nums):
    total = sum(nums)
    if total % 2: return False
    return can_sum(nums, total // 2)

# 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]

# Edit Distance (Levenshtein)
def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],      # delete
                    dp[i][j-1],      # insert
                    dp[i-1][j-1]    # replace
                )
    return dp[m][n]

# O(n²) DP
def lis(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# O(n log n) with bisect
import bisect
def lis_fast(nums):
    tails = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

# Unique Paths (m×n grid, only right or down)
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

# Minimum Path Sum
def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0: continue
            elif i == 0: grid[i][j] += grid[i][j-1]
            elif j == 0: grid[i][j] += grid[i-1][j]
            else: grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    return grid[m-1][n-1]

# House Robber (can't rob adjacent)
def rob(nums):
    if not nums: return 0
    if len(nums) <= 2: return max(nums)
    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])  # skip or rob
        prev2 = prev1
        prev1 = curr
    return prev1

def backtrack(result, current, choices, start):
    if is_solution(current):         # base case
        result.append(current[:])    # add copy!
        return

    for i in range(start, len(choices)):
        # 1. Choose
        current.append(choices[i])
        # 2. Explore
        backtrack(result, current, choices, i + 1)  # or i for reuse
        # 3. Unchoose (backtrack)
        current.pop()

# SUBSETS — all possible subsets (power set)
# [1,2,3] → [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]
def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])     # add every state
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

# PERMUTATIONS — all orderings
# [1,2,3] → [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]
def permutations(nums):
    result = []
    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()
    backtrack([], nums)
    return result

# COMBINATIONS — choose k from n
# n=4, k=2 → [1,2],[1,3],[1,4],[2,3],[2,4],[3,4]
def combinations(n, k):
    result = []
    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        for i in range(start, n + 1):
            current.append(i)
            backtrack(i + 1, current)
            current.pop()
    backtrack(1, [])
    return result

# N-Queens
def solve_n_queens(n):
    result = []
    cols = set()
    diag1 = set()   # row - col
    diag2 = set()   # row + col

    def backtrack(row, board):
        if row == n:
            result.append(["." * c + "Q" + "." * (n-c-1) for c in board])
            return
        for col in range(n):
            if col in cols or row-col in diag1 or row+col in diag2:
                continue         # prune!
            cols.add(col); diag1.add(row-col); diag2.add(row+col)
            backtrack(row + 1, board + [col])
            cols.discard(col); diag1.discard(row-col); diag2.discard(row+col)

    backtrack(0, [])
    return result

# Word Search in Grid
def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, idx):
        if idx == len(word): return True
        if r < 0 or r >= rows or c < 0 or c >= cols: return False
        if board[r][c] != word[idx]: return False
        temp = board[r][c]
        board[r][c] = "#"              # mark visited
        found = (dfs(r+1,c,idx+1) or dfs(r-1,c,idx+1) or
                 dfs(r,c+1,idx+1) or dfs(r,c-1,idx+1))
        board[r][c] = temp               # unchoose!
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

# Next Greater Element
def next_greater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices
    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    return result

# Daily Temperatures (days until warmer)
def daily_temperatures(temps):
    n = len(temps)
    result = [0] * n
    stack = []
    for i in range(n):
        while stack and temps[i] > temps[stack[-1]]:
            idx = stack.pop()
            result[idx] = i - idx  # days difference
        stack.append(i)
    return result

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._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None

    def _find(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    # Autocomplete: find all words with prefix
    def autocomplete(self, prefix):
        node = self._find(prefix)
        if not node: return []
        results = []
        def dfs(node, path):
            if node.is_end:
                results.append(prefix + path)
            for char, child in node.children.items():
                dfs(child, path + char)
        dfs(node, "")
        return results

# Merge Intervals
def merge_intervals(intervals):
    intervals.sort()
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:       # overlapping
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

# Non-Overlapping Intervals (min removals)
def erase_overlap(intervals):
    intervals.sort(key=lambda x: x[1])  # sort by END
    count = 0
    prev_end = float('-inf')
    for start, end in intervals:
        if start >= prev_end:
            prev_end = end            # keep this interval
        else:
            count += 1                # remove (overlap)
    return count

# Meeting Rooms II (min rooms needed)
import heapq
def min_meeting_rooms(intervals):
    intervals.sort()
    heap = []   # tracks end times of active meetings
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)       # reuse room
        heapq.heappush(heap, end)
    return len(heap)

# Jump Game (can reach end?)
def can_jump(nums):
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach: return False
        max_reach = max(max_reach, i + jump)
    return True

# FIXED window: max sum of k elements
def max_sum_k(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # slide: add right, remove left
        max_sum = max(max_sum, window_sum)
    return max_sum

# VARIABLE window: min length subarray with sum >= target
def min_subarray_len(target, nums):
    left = 0
    curr_sum = 0
    min_len = float('inf')
    for right in range(len(nums)):
        curr_sum += nums[right]          # expand
        while curr_sum >= target:
            min_len = min(min_len, right - left + 1)
            curr_sum -= nums[left]       # shrink
            left += 1
    return min_len if min_len != float('inf') else 0

# Minimum Window Substring (all chars of t in s)
from collections import Counter
def min_window(s, t):
    need = Counter(t)
    missing = len(t)
    left = start = 0
    min_len = float('inf')
    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        while missing == 0:              # all chars found
            if right - left + 1 < min_len:
                min_len = right - left + 1
                start = left
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return s[start:start + min_len] if min_len != float('inf') else ""

# 3Sum — find all triplets that sum to 0
def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]: continue  # skip dups
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]: left += 1
                while left < right and nums[right] == nums[right-1]: right -= 1
                left += 1; right -= 1
            elif total < 0: left += 1
            else: right -= 1
    return result

# Container With Most Water
def max_area(height):
    left, right = 0, len(height) - 1
    max_water = 0
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_water = max(max_water, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water

# Remove Duplicates in-place (sorted)
def remove_dups(nums):
    if not nums: return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

# Single Number (every element appears twice except one)
def single_number(nums):
    result = 0
    for num in nums:
        result ^= num      # XOR: a ^ a = 0, a ^ 0 = a
    return result

# Power of 2
def is_power_of_2(n):
    return n > 0 and (n & (n - 1)) == 0
    # 8 = 1000, 7 = 0111 → 1000 & 0111 = 0000 → True!

# Count set bits (number of 1s)
def count_bits(n):
    count = 0
    while n:
        count += n & 1    # check last bit
        n >>= 1           # shift right
    return count
    # Or: bin(n).count('1')

# Missing Number (0 to n, one missing)
def missing_number(nums):
    result = len(nums)
    for i, num in enumerate(nums):
        result ^= i ^ num  # XOR index with value
    return result

# Reverse Bits
def reverse_bits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

# Check if palindrome
def is_palindrome(s):
    return s == s[::-1]

# Valid Palindrome (ignore non-alphanumeric)
def is_valid_palindrome(s):
    cleaned = [c.lower() for c in s if c.isalnum()]
    return cleaned == cleaned[::-1]

# Longest Palindromic Substring — expand from center
def longest_palindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return s[l+1:r]

    result = ""
    for i in range(len(s)):
        # Odd length: "aba"
        odd = expand(i, i)
        # Even length: "abba"
        even = expand(i, i + 1)
        result = max(result, odd, even, key=len)
    return result

# Count Palindromic Substrings
def count_palindromes(s):
    count = 0
    for i in range(len(s)):
        for l, r in [(i,i), (i,i+1)]:  # odd & even
            while l >= 0 and r < len(s) and s[l] == s[r]:
                count += 1
                l -= 1; r += 1
    return count

# Reverse Words in String
def reverse_words(s):
    return " ".join(s.split()[::-1])

# String to Integer (atoi)
def my_atoi(s):
    s = s.strip()
    if not s: return 0
    sign = -1 if s[0] == '-' else 1
    start = 1 if s[0] in '+-' else 0
    result = 0
    for i in range(start, len(s)):
        if not s[i].isdigit(): break
        result = result * 10 + int(s[i])
    result *= sign
    return max(-2**31, min(2**31 - 1, result))

# Longest Common Prefix
def longest_prefix(strs):
    if not strs: return ""
    for i, chars in enumerate(zip(*strs)):
        if len(set(chars)) > 1:
            return strs[0][:i]
    return min(strs)

# Check if string is rotation of another
def is_rotation(s1, s2):
    return len(s1) == len(s2) and s2 in s1 + s1

# Encode/Decode Strings
def encode(strs):
    return "".join(f"{len(s)}#{s}" for s in strs)

def decode(s):
    result, i = [], 0
    while i < len(s):
        j = s.index('#', i)
        length = int(s[i:j])
        result.append(s[j+1:j+1+length])
        i = j + 1 + length
    return result