# --- Pattern 1 : Deux pointeurs (two pointers) -- tableau trié, palindromes, paires ---
def paire_somme_cible(tableau: list[int], cible: int) -> tuple[int, int] | None:
    # O(n) au lieu de O(n^2) en force brute -- exige un tableau TRIÉ
    gauche, droite = 0, len(tableau) - 1
    while gauche < droite:
        total = tableau[gauche] + tableau[droite]
        if total == cible:
            return (gauche, droite)
        elif total < cible:
            gauche += 1   # augmenter la somme
        else:
            droite -= 1   # diminuer la somme
    return None

assert paire_somme_cible([1, 2, 4, 7, 11, 15], 15) == (2, 4)   # 4 + 11

def est_palindrome(s: str) -> bool:
    gauche, droite = 0, len(s) - 1
    while gauche < droite:
        if s[gauche] != s[droite]:
            return False
        gauche += 1; droite -= 1
    return True

# --- Pattern 2 : Fenêtre glissante (sliding window) -- sous-tableaux/sous-chaînes contigus ---
def plus_longue_sous_chaine_sans_repetition(s: str) -> int:
    # O(n) : la fenêtre [gauche, droite] ne contient jamais de doublon
    vus = {}
    gauche = 0
    max_longueur = 0
    for droite, caractere in enumerate(s):
        if caractere in vus and vus[caractere] >= gauche:
            gauche = vus[caractere] + 1   # on saute directement après la dernière occurrence
        vus[caractere] = droite
        max_longueur = max(max_longueur, droite - gauche + 1)
    return max_longueur

assert plus_longue_sous_chaine_sans_repetition("abcabcbb") == 3   # "abc"

# --- Pattern 3 : Fast & slow pointers -- détection de cycle, milieu de liste ---
def trouver_milieu_liste(tete) -> object:
    lent = rapide = tete
    while rapide and rapide.suivant:
        lent = lent.suivant
        rapide = rapide.suivant.suivant
    return lent   # quand rapide atteint la fin, lent est exactement au milieu

# --- Pattern 4 : Merge intervals -- fusionner des intervalles chevauchants ---
def fusionner_intervalles(intervalles: list[tuple[int, int]]) -> list[tuple[int, int]]:
    if not intervalles:
        return []
    intervalles_tries = sorted(intervalles)
    resultat = [intervalles_tries[0]]
    for debut, fin in intervalles_tries[1:]:
        dernier_debut, dernier_fin = resultat[-1]
        if debut <= dernier_fin:   # chevauchement -> fusionner
            resultat[-1] = (dernier_debut, max(dernier_fin, fin))
        else:
            resultat.append((debut, fin))
    return resultat

assert fusionner_intervalles([(1, 3), (2, 6), (8, 10), (15, 18)]) == [(1, 6), (8, 10), (15, 18)]

# --- Pattern 5 : Top K éléments -- toujours envisager un tas plutôt qu'un tri complet ---
import heapq
from collections import Counter

def k_elements_plus_frequents(tableau: list, k: int) -> list:
    compteur = Counter(tableau)
    return [element for element, _ in heapq.nlargest(k, compteur.items(), key=lambda x: x[1])]

# --- Pattern 6 : Recherche binaire sur la réponse (binary search on answer) ---
def capacite_minimale_expedition(poids: list[int], jours: int) -> int:
    # Minimiser la capacité du bateau pour livrer tous les colis en <= jours, dans l'ordre
    def jours_necessaires(capacite: int) -> int:
        jours_utilises, charge_actuelle = 1, 0
        for p in poids:
            if charge_actuelle + p > capacite:
                jours_utilises += 1
                charge_actuelle = 0
            charge_actuelle += p
        return jours_utilises

    gauche, droite = max(poids), sum(poids)
    while gauche < droite:
        milieu = (gauche + droite) // 2
        if jours_necessaires(milieu) <= jours:
            droite = milieu   # capacité suffisante -- on tente plus petit
        else:
            gauche = milieu + 1
    return gauche

assert capacite_minimale_expedition([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5) == 15

# --- Pattern 7 : BFS/DFS sur grille -- pattern très fréquent (îles, labyrinthes, jeux) ---
def chemin_le_plus_court_grille(grille: list[list[int]], depart: tuple, arrivee: tuple) -> int:
    from collections import deque
    lignes, colonnes = len(grille), len(grille[0])
    file = deque([(depart, 0)])
    visites = {depart}
    while file:
        (i, j), distance = file.popleft()
        if (i, j) == arrivee:
            return distance
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = i + di, j + dj
            if (0 <= ni < lignes and 0 <= nj < colonnes
                    and grille[ni][nj] == 0 and (ni, nj) not in visites):
                visites.add((ni, nj))
                file.append(((ni, nj), distance + 1))
    return -1

# --- Méthode générale face à un problème inconnu en entretien ---
# 1. Clarifier les contraintes (taille des entrées, doublons, valeurs négatives, tri déjà fait ?)
# 2. Commencer par une solution brute (force brute), même O(n^2)/O(n^3) -- valider la logique d'abord
# 3. Identifier le pattern (deux pointeurs ? fenêtre glissante ? DP ? graphe ? tas ?)
# 4. Optimiser en fonction du pattern identifié, en expliquant le compromis temps/espace
# 5. Tester sur les cas limites : tableau vide, un seul élément, doublons, valeurs extrêmes