> ALGORITHMS & DATA STRUCTURES

# Regola della somma: O(f + g) = O(max(f, g))
for i in range(n):       # O(n)
    ...
for j in range(n*n):    # O(n²)
    ...
# Totale: O(n²)

# Regola del prodotto: cicli annidati si moltiplicano
for i in range(n):       # O(n)
    for j in range(n):   #   × O(n)
        ...               # = O(n²)

# Logaritmico: dimezzamento ad ogni iterazione
while n > 1:             # O(log n)
    n //= 2

Misura la memoria aggiuntiva usata dall'algoritmo (escludendo l'input).

def fibonacci(n):
    # Caso base
    if n <= 1:
        return n
    # Caso ricorsivo
    return fibonacci(n - 1) + fibonacci(n - 2)  # O(2^n) !

# Con memoization: O(n)
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

Per ricorrenze della forma T(n) = a·T(n/b) + O(n^d):

from array import array

# Array statico di interi (tipizzato, più efficiente in memoria)
arr = array('i', [10, 20, 30, 40, 50])
arr[2]             # accesso O(1) → 30
len(arr)            # 5

# Typecodes: 'b'=int8, 'i'=int32, 'f'=float32, 'd'=float64

# Tuple: immutabile, più leggero di una lista
t = (1, 2, 3, 4, 5)
t[0]               # 1 — accesso O(1)

# list in Python = array dinamico con doubling strategy
a = []
a.append(10)       # O(1) ammortizzato — aggiunge in coda
a.append(20)
a.append(30)
a.insert(1, 15)    # O(n) — inserisce in posizione
a.pop()             # O(1) — rimuove ultimo
a.pop(0)            # O(n) — rimuove primo (shift tutti)
a.remove(15)       # O(n) — rimuove prima occorrenza
del a[1]            # O(n) — rimuove per indice

# Slicing
a = [1, 2, 3, 4, 5]
a[1:4]             # [2, 3, 4] — O(k) dove k = dimensione slice
a[::-1]            # [5, 4, 3, 2, 1] — reverse O(n)

# List comprehension
squares = [x**2 for x in range(10)]  # [0, 1, 4, 9, 16, ...]

class DynamicArray:
    def __init__(self):
        self.size = 0
        self.capacity = 1
        self.data = [None] * self.capacity

    def append(self, val):
        if self.size == self.capacity:
            self._resize(self.capacity * 2)  # doubling
        self.data[self.size] = val
        self.size += 1

    def _resize(self, new_cap):
        new_data = [None] * new_cap
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_cap

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, data):           # O(1)
        node = Node(data)
        node.next = self.head
        self.head = node

    def append(self, data):            # O(n) senza tail pointer
        node = Node(data)
        if not self.head:
            self.head = node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = node

    def delete(self, data):            # O(n)
        if self.head and self.head.data == data:
            self.head = self.head.next
            return
        cur = self.head
        while cur.next:
            if cur.next.data == data:
                cur.next = cur.next.next
                return
            cur = cur.next

    def reverse(self):                 # O(n) in-place
        prev, cur = None, self.head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        self.head = prev

class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):            # O(1) con tail
        node = DNode(data)
        if not self.tail:
            self.head = self.tail = node
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node

    def delete_node(self, node):      # O(1) dato il riferimento al nodo
        if node.prev: node.prev.next = node.next
        else:        self.head = node.next
        if node.next: node.next.prev = node.prev
        else:        self.tail = node.prev

def has_cycle(head):
    """Rileva ciclo in una linked list — Floyd's algorithm"""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

def find_middle(head):
    """Trova il nodo centrale in O(n) con un solo passaggio"""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

# 1) Con lista Python (semplice e veloce)
stack = []
stack.append(10)        # push
stack.append(20)
top = stack.pop()       # pop → 20

# 2) Con collections.deque (thread-safe, no reallocation)
from collections import deque
stack = deque()
stack.append(10)
stack.pop()

# 3) Implementazione con linked list
class Stack:
    def __init__(self):
        self._top = None
        self._size = 0

    def push(self, data):
        node = Node(data)
        node.next = self._top
        self._top = node
        self._size += 1

    def pop(self):
        if not self._top: raise IndexError("empty")
        data = self._top.data
        self._top = self._top.next
        self._size -= 1
        return data

    def peek(self): return self._top.data

# Verifica parentesi bilanciate
def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in '([{':
            stack.append(c)
        elif c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
    return len(stack) == 0

from collections import deque

# Coda FIFO
q = deque()
q.append(10)           # enqueue
q.append(20)
front = q.popleft()    # dequeue → 10
q[0]                    # peek → 20

# Deque (doppia estremità)
dq = deque()
dq.appendleft(5)       # inserisci a sinistra
dq.append(10)           # inserisci a destra
dq.popleft()            # rimuovi da sinistra
dq.pop()                # rimuovi da destra

# Coda con capacità massima (buffer circolare)
buf = deque(maxlen=5)  # se pieno, rimuove dal lato opposto

class CircularQueue:
    def __init__(self, k):
        self.data = [None] * k
        self.head = self.tail = -1
        self.size, self.cap = 0, k

    def enqueue(self, val):
        if self.size == self.cap: raise OverflowError
        self.tail = (self.tail + 1) % self.cap
        if self.head == -1: self.head = 0
        self.data[self.tail] = val
        self.size += 1

    def dequeue(self):
        if self.size == 0: raise IndexError
        val = self.data[self.head]
        self.head = (self.head + 1) % self.cap
        self.size -= 1
        return val

Il caso peggiore O(n) si verifica quando tutte le chiavi collidono nello stesso bucket.

# dict è un hash table ottimizzato (open addressing)
d = {}
d["chiave"] = 42       # inserimento
val = d["chiave"]        # accesso
d.get("missing", 0)     # accesso con default
del d["chiave"]          # rimozione
"chiave" in d            # ricerca → O(1) medio

# set: hash table senza valori (solo chiavi)
s = {1, 2, 3}
s.add(4)                 # O(1)
3 in s                    # O(1)

# Counter per frequenze
from collections import Counter
freq = Counter([1,2,2,3,3,3])  # {3: 3, 2: 2, 1: 1}
freq.most_common(2)                # [(3, 3), (2, 2)]

# defaultdict: valore di default automatico
from collections import defaultdict
adj = defaultdict(list)          # lista di adiacenza
adj["A"].append("B")

class HashTable:
    def __init__(self, capacity=16):
        self.cap = capacity
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0

    def _hash(self, key):
        return hash(key) % self.cap

    def put(self, key, val):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, val)
                return
        self.buckets[idx].append((key, val))
        self.size += 1

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key: return v
        raise KeyError(key)

Proprietà: per ogni nodo, tutti i valori nel sottoalbero sinistro sono < e nel destro sono >.

class BSTNode:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

def insert(root, key):
    if not root:
        return BSTNode(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    if not root or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

def find_min(root):
    while root.left:
        root = root.left
    return root

def delete(root, key):
    if not root: return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if not root.left: return root.right
        if not root.right: return root.left
        # Due figli: sostituisci con successore in-order
        succ = find_min(root.right)
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root

def inorder(root):       # Sx → Radice → Dx  (ordinato per BST!)
    if root:
        inorder(root.left)
        print(root.key)
        inorder(root.right)

def preorder(root):      # Radice → Sx → Dx  (utile per copiare l'albero)
    if root:
        print(root.key)
        preorder(root.left)
        preorder(root.right)

def postorder(root):     # Sx → Dx → Radice  (utile per distruggere)
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.key)

def level_order(root):   # BFS per livelli
    from collections import deque
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.key)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)

# Rotazione singola destra (caso LL)
#       z               y
#      / \            /   \
#     y   T4   →    x     z
#    / \           / \   / \
#   x   T3        T1 T2 T3 T4
#  / \
# T1  T2

def rotate_right(z):
    y = z.left
    z.left = y.right
    y.right = z
    z.height = 1 + max(h(z.left), h(z.right))
    y.height = 1 + max(h(y.left), h(y.right))
    return y

# Rotazione singola sinistra (caso RR) — simmetrica
def rotate_left(z):
    y = z.right
    z.right = y.left
    y.left = z
    z.height = 1 + max(h(z.left), h(z.right))
    y.height = 1 + max(h(y.left), h(y.right))
    return y

def h(node): return node.height if node else 0
def bf(node): return h(node.left) - h(node.right)  # balance factor

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        self.height = 1

def avl_insert(root, key):
    if not root: return AVLNode(key)
    if key < root.key:   root.left  = avl_insert(root.left, key)
    elif key > root.key: root.right = avl_insert(root.right, key)
    else: return root

    root.height = 1 + max(h(root.left), h(root.right))
    balance = bf(root)

    # Caso LL
    if balance > 1 and key < root.left.key:
        return rotate_right(root)
    # Caso RR
    if balance < -1 and key > root.right.key:
        return rotate_left(root)
    # Caso LR
    if balance > 1 and key > root.left.key:
        root.left = rotate_left(root.left)
        return rotate_right(root)
    # Caso RL
    if balance < -1 and key < root.right.key:
        root.right = rotate_right(root.right)
        return rotate_left(root)

    return root

Min-heap: genitore ≤ figli. Max-heap: genitore ≥ figli. Su array: figli di i in posizione 2i+1 e 2i+2, genitore in (i-1)//2.

import heapq

# Min-heap
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
minimo = heapq.heappop(heap)    # → 2
peek = heap[0]                    # → 5 (min senza rimuovere)

# Heapify: trasforma lista in heap in O(n)
arr = [9, 3, 7, 1, 5]
heapq.heapify(arr)              # arr ora è un min-heap

# Max-heap: negare i valori
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -2)
massimo = -heapq.heappop(max_heap)  # → 5

# N più grandi / piccoli
heapq.nlargest(3, arr)         # 3 più grandi
heapq.nsmallest(3, arr)        # 3 più piccoli

# Coda a priorità con tuple (priorità, dato)
pq = []
heapq.heappush(pq, (3, "bassa"))
heapq.heappush(pq, (1, "alta"))
heapq.heappush(pq, (2, "media"))
_, task = heapq.heappop(pq)     # → "alta"

class MinHeap:
    def __init__(self):
        self.data = []

    def push(self, val):
        self.data.append(val)
        self._sift_up(len(self.data) - 1)

    def pop(self):
        self.data[0], self.data[-1] = self.data[-1], self.data[0]
        val = self.data.pop()
        self._sift_down(0)
        return val

    def _sift_up(self, i):
        while i > 0:
            parent = (i - 1) // 2
            if self.data[i] < self.data[parent]:
                self.data[i], self.data[parent] = self.data[parent], self.data[i]
                i = parent
            else: break

    def _sift_down(self, i):
        n = len(self.data)
        while 2*i+1 < n:
            j = 2*i+1
            if j+1 < n and self.data[j+1] < self.data[j]: j += 1
            if self.data[i] > self.data[j]:
                self.data[i], self.data[j] = self.data[j], self.data[i]
                i = j
            else: break

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):                 # O(m)
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word):                 # O(m)
        node = self._find(word)
        return node is not None and node.is_end

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

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

from collections import defaultdict

# Grafo non orientato non pesato
graph = defaultdict(list)
graph["A"].append("B")
graph["B"].append("A")  # bidirezionale

# Grafo orientato pesato
wgraph = defaultdict(list)
wgraph["A"].append(("B", 5))    # A → B con peso 5
wgraph["A"].append(("C", 3))    # A → C con peso 3

# Da lista di archi
edges = [("A","B"), ("A","C"), ("B","C")]
adj = defaultdict(list)
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)   # non orientato

# Grafo con V nodi (0..V-1)
V = 4
matrix = [[0] * V for _ in range(V)]
matrix[0][1] = 1  # arco 0→1
matrix[1][0] = 1  # non orientato

# Pesato: matrix[u][v] = peso (0 o inf se non esiste)
INF = float('inf')
wmatrix = [[INF]*V for _ in range(V)]
for i in range(V): wmatrix[i][i] = 0

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

# BFS con distanza minima (grafi non pesati)
def bfs_distance(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nb in graph[node]:
            if nb not in dist:
                dist[nb] = dist[node] + 1
                queue.append(nb)
    return dist

# DFS iterativo (con stack)
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        order.append(node)
        for nb in graph[node]:
            stack.append(nb)
    return order

# DFS ricorsivo
def dfs_recursive(graph, node, visited=None):
    if visited is None: visited = set()
    visited.add(node)
    for nb in graph[node]:
        if nb not in visited:
            dfs_recursive(graph, nb, visited)
    return visited

# Rilevare cicli in un grafo orientato (DFS con colori)
def has_cycle(graph, n):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    def dfs(u):
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY: return True    # back edge!
            if color[v] == WHITE and dfs(v): return True
        color[u] = BLACK
        return False
    return any(dfs(i) for i in range(n) if color[i] == WHITE)

import heapq

def dijkstra(graph, src):
    """graph[u] = [(v, weight), ...] — pesi ≥ 0"""
    dist = {src: 0}
    pq = [(0, src)]
    prev = {}

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')):
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                prev[v] = u
                heapq.heappush(pq, (nd, v))

    return dist, prev

# Ricostruzione percorso
def reconstruct_path(prev, src, dst):
    path = []
    node = dst
    while node != src:
        path.append(node)
        node = prev[node]
    path.append(src)
    return path[::-1]

def bellman_ford(edges, n, src):
    """edges = [(u, v, weight), ...] — supporta pesi negativi"""
    dist = [float('inf')] * n
    dist[src] = 0

    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Rileva cicli a peso negativo
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("Ciclo a peso negativo!")
    return dist

import heapq

def a_star(graph, start, goal, heuristic):
    """heuristic(node) → stima distanza al goal (ammissibile!)"""
    pq = [(heuristic(start), 0, start)]  # (f, g, node)
    g_score = {start: 0}
    prev = {}

    while pq:
        f, g, u = heapq.heappop(pq)
        if u == goal:
            return reconstruct_path(prev, start, goal), g
        if g > g_score.get(u, float('inf')):
            continue
        for v, w in graph[u]:
            ng = g + w
            if ng < g_score.get(v, float('inf')):
                g_score[v] = ng
                prev[v] = u
                heapq.heappush(pq, (ng + heuristic(v), ng, v))

    return None, float('inf')  # nessun percorso

def floyd_warshall(dist):
    """dist = matrice V×V (dist[i][j] = peso, inf se non connesso)"""
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist  # O(V³)

def kruskal(n, edges):
    """edges = [(weight, u, v), ...] — O(E log E)"""
    edges.sort()
    uf = UnionFind(n)  # vedi sezione Union-Find
    mst = []
    cost = 0
    for w, u, v in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, w))
            cost += w
    return mst, cost

def prim(graph, start=0):
    """graph[u] = [(v, weight), ...] — O((V+E) log V)"""
    visited = {start}
    pq = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(pq)
    mst, cost = [], 0

    while pq:
        w, u, v = heapq.heappop(pq)
        if v in visited: continue
        visited.add(v)
        mst.append((u, v, w))
        cost += w
        for nb, nw in graph[v]:
            if nb not in visited:
                heapq.heappush(pq, (nw, v, nb))
    return mst, cost

from collections import deque, defaultdict

def topological_sort(graph, n):
    in_deg = [0] * n
    for u in graph:
        for v in graph[u]:
            in_deg[v] += 1

    queue = deque(i for i in range(n) if in_deg[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                queue.append(v)

    if len(order) != n:
        raise ValueError("Il grafo ha un ciclo!")
    return order

Scorre l'array dall'inizio alla fine confrontando ogni elemento con il target. Non richiede alcuna precondizione sui dati: funziona su array non ordinati e su qualsiasi sequenza iterabile. È la strategia più semplice, ma anche la più lenta su grandi input.

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Richiede array ordinato. Ad ogni passo confronta il target con l'elemento centrale e scarta metà dell'intervallo di ricerca, dimezzando lo spazio rimanente ad ogni iterazione. Usa una divisione per calcolare l'indice mediano, quindi è efficiente su memoria ad accesso casuale (RAM).

# Richiede array ORDINATO

# Iterativa
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:   return mid
        elif arr[mid] < target: lo = mid + 1
        else:                     hi = mid - 1
    return -1

# bisect (libreria standard)
from bisect import bisect_left, bisect_right, insort

arr = [1, 3, 5, 7, 9]
bisect_left(arr, 5)     # → 2 (primo indice dove 5 può andare)
bisect_right(arr, 5)    # → 3 (dopo l'ultimo 5)
insort(arr, 6)           # inserisce mantenendo ordinato

# Ricerca binaria su condizione (lower bound)
def lower_bound(lo, hi, predicate):
    """Trova il minimo x in [lo,hi] tale che predicate(x) è True"""
    while lo < hi:
        mid = (lo + hi) // 2
        if predicate(mid): hi = mid
        else:               lo = mid + 1
    return lo

Richiede array ordinato. Divide l'intervallo usando i numeri di Fibonacci invece che a metà. Utile quando l'accesso agli elementi ha costo non uniforme (es. memoria su disco/nastro): usa solo addizioni e sottrazioni, evitando la divisione richiesta dalla ricerca binaria.

# Richiede array ORDINATO

def fibonacci_search(arr, target):
    n = len(arr)

    # Trova il più piccolo numero di Fibonacci >= n
    fib2 = 0               # (k-2)-esimo
    fib1 = 1               # (k-1)-esimo
    fib  = fib1 + fib2   # k-esimo
    while fib < n:
        fib2 = fib1
        fib1 = fib
        fib  = fib1 + fib2

    offset = -1           # intervallo eliminato da sinistra

    while fib > 1:
        i = min(offset + fib2, n - 1)

        if arr[i] < target:    # scarta sottoarray sinistro
            fib    = fib1
            fib1   = fib2
            fib2   = fib - fib1
            offset = i
        elif arr[i] > target:  # scarta sottoarray destro
            fib  = fib2
            fib1 = fib1 - fib2
            fib2 = fib - fib1
        else:
            return i

    # Confronto finale sull'ultimo elemento
    if fib1 and offset + 1 < n and arr[offset + 1] == target:
        return offset + 1
    return -1

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped: break  # ottimizzazione: già ordinato

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

def quick_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        lt, gt = partition(arr, lo, hi)
        quick_sort(arr, lo, lt - 1)
        quick_sort(arr, gt + 1, hi)

def median_of_three(arr, lo, hi):
    mid = (lo + hi) // 2
    if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
    if arr[lo] > arr[hi]:  arr[lo], arr[hi]  = arr[hi],  arr[lo]
    if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi],  arr[mid]
    arr[mid], arr[hi] = arr[hi], arr[mid]
    return arr[hi]

def partition(arr, lo, hi):
    pivot = median_of_three(arr, lo, hi)
    lt, i, gt = lo, lo, hi
    while i <= gt:
        if   arr[i] < pivot: arr[lt], arr[i] = arr[i], arr[lt]; lt += 1; i += 1
        elif arr[i] > pivot: arr[i], arr[gt] = arr[gt], arr[i]; gt -= 1
        else:                i += 1
    return lt, gt

def heap_sort(arr):
    n = len(arr)

    def sift_down(i, size):
        while 2*i+1 < size:
            j = 2*i+1
            if j+1 < size and arr[j+1] > arr[j]: j += 1
            if arr[i] < arr[j]:
                arr[i], arr[j] = arr[j], arr[i]
                i = j
            else: break

    # Build max-heap O(n)
    for i in range(n//2 - 1, -1, -1):
        sift_down(i, n)

    # Extract max ripetutamente
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(0, end)

# sorted() e list.sort() usano Timsort: O(n log n), stabile
arr = [3, 1, 4, 1, 5]
sorted(arr)                      # nuova lista ordinata
arr.sort()                       # in-place
sorted(arr, reverse=True)      # decrescente
sorted(arr, key=lambda x: -x) # custom key

# Ordinamento stabile: ordina per più chiavi
data = [("B",2), ("A",1), ("B",1)]
sorted(data, key=lambda x: (x[0], x[1]))
# → [('A', 1), ('B', 1), ('B', 2)]

def counting_sort(arr, k):
    """Ordina interi in [0, k). Stabile."""
    count = [0] * k
    for x in arr:
        count[x] += 1
    i = 0
    for val in range(k):
        for _ in range(count[val]):
            arr[i] = val
            i += 1

def radix_sort(arr):
    """Ordina interi non negativi. d = cifre, k = base (10)."""
    if not arr: return
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        _counting_by_digit(arr, exp)
        exp *= 10

def _counting_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for x in arr:
        count[(x // exp) % 10] += 1
    for i in range(1, 10):
        count[i] += count[i-1]
    for x in reversed(arr):
        d = (x // exp) % 10
        count[d] -= 1
        output[count[d]] = x
    arr[:] = output

# Top-down (memoization)
def fib_memo(n, memo={}):
    if n <= 1: return n
    if n not in memo:
        memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

# Bottom-up (tabulazione)
def fib_tab(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Ottimizzato in spazio O(1)
def fib_opt(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]  # non prendere
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][W]

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]

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):
            cost = 0 if s1[i-1] == s2[j-1] else 1
            dp[i][j] = min(
                dp[i-1][j] + 1,       # cancellazione
                dp[i][j-1] + 1,       # inserimento
                dp[i-1][j-1] + cost  # sostituzione
            )
    return dp[m][n]

def coin_change(coins, amount):
    """Minimo numero di monete per raggiungere amount"""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

def activity_selection(activities):
    """activities = [(start, end), ...] — massimizza il numero"""
    activities.sort(key=lambda x: x[1])  # ordina per fine
    result = [activities[0]]
    for s, e in activities[1:]:
        if s >= result[-1][1]:  # non si sovrappone
            result.append((s, e))
    return result

import heapq

def huffman(freq):
    """freq = {'a': 5, 'b': 9, ...} → codici Huffman"""
    heap = [(f, c) for c, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        f1, c1 = heapq.heappop(heap)
        f2, c2 = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, (c1, c2)))
    return heap[0]

import random

def quick_select(arr, k):
    """Trova il k-esimo elemento più piccolo (0-indexed)"""
    pivot = random.choice(arr)
    lo = [x for x in arr if x < pivot]
    eq = [x for x in arr if x == pivot]
    hi = [x for x in arr if x > pivot]

    if k < len(lo):
        return quick_select(lo, k)
    elif k < len(lo) + len(eq):
        return pivot
    else:
        return quick_select(hi, k - len(lo) - len(eq))

def max_subarray(arr):
    """Somma massima di un sotto-array contiguo"""
    best = cur = arr[0]
    for x in arr[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

def permutations(arr):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i, val in enumerate(remaining):
            path.append(val)
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()
    backtrack([], arr)
    return result

def subsets(arr):
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(arr)):
            path.append(arr[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

def n_queens(n):
    solutions = []
    cols = set()
    diag1 = set()  # r - c
    diag2 = set()  # r + c

    def solve(r, queens):
        if r == n:
            solutions.append(queens[:])
            return
        for c in range(n):
            if c in cols or r-c in diag1 or r+c in diag2:
                continue
            cols.add(c); diag1.add(r-c); diag2.add(r+c)
            solve(r+1, queens + [c])
            cols.discard(c); diag1.discard(r-c); diag2.discard(r+c)

    solve(0, [])
    return solutions

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

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

    def union(self, x, y):            # con union by rank
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.components -= 1
        return True

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