🧩 Maîtriser LeetCode Hard : 7 solutions complexes expliquées 🔗

S’attaquer aux problèmes LeetCode Hard donne souvent l’impression de se heurter à un mur. Cependant, les décomposer en schémas digestes — comme la programmation dynamique, le backtracking et la théorie des graphes — les rend beaucoup plus accessibles.

Dans cet article, je partage 7 des problèmes LeetCode Hard les plus intéressants que j’ai résolus en Go. Pour rendre ce guide aussi utile que possible, j’ai condensé les explications afin de me concentrer fortement sur l’intuition fondamentale et la complexité, facilitant ainsi le passage de l’énoncé du problème au code fonctionnel.

📑 Table des Matières 🔗

🔢 1. 60. Permutation Sequence 🔗

❓ Le problème 🔗

Étant donné $n$ et $k$, renvoyez la $k^{\text{e}}$ séquence de permutation des nombres de $1$ à $n$. Par exemple, si $n = 3$, les permutations sont : "123", "132", "213", "231", "312", "321". Si $k = 3$, la réponse est "213".

💡 L’intuition 🔗

Au lieu de générer toutes les permutations (ce qui serait trop lent), nous pouvons utiliser une approche mathématique basée sur les factorielles.

Pour $n$ chiffres, il existe $n!$ permutations au total. Si nous fixons le premier chiffre, il reste $(n-1)!$ permutations pour les chiffres restants. Nous pouvons déterminer le premier chiffre en calculant dans quel bloc de $(n-1)!$ permutations se trouve la $k^{\text{e}}$ permutation. L’indice de notre prochain chiffre dans une liste triée de chiffres disponibles sera simplement $(k-1) / (n-1)!$. Après avoir choisi un chiffre, nous mettons à jour $k$ avec le reste $k \bmod (n-1)!$ et nous poursuivons par récurrence.

⏱️ Complexité 🔗

• Temps : $O(N^2)$ car la suppression d’un élément d’une tranche (slice) prend un temps $O(N)$, et nous effectuons cette opération $N$ fois.
• Espace : $O(N)$ pour la pile de récursion et le tableau de chiffres.

💻 Solution en Go 🔗

import "fmt"

func getPermutation(n int, k int) string {
	factorial := 1
	digits := []int{}

	// Calculate factorials and populate the digits slice
	for i := 1; i <= n; i++ {
		factorial *= i
		digits = append(digits, i)
	}

	return solvePermutation(n-1, k-1, factorial/n, digits)
}

func solvePermutation(n, k, factorial int, digits []int) string {
	// Find which block of permutations 'k' falls into
	index := k / factorial
	res := fmt.Sprintf("%d", digits[index])

	if n <= 0 {
		return res
	}

	// Update k for the next level: k % factorial
	// Update factorial for the next level: factorial / n
	// Remove the selected digit from the slice
	nextK := k % factorial
	nextFactorial := factorial / n
	remainingDigits := append(digits[:index], digits[index+1:]...)

	res += solvePermutation(n-1, nextK, nextFactorial, remainingDigits)
	return res
}

🔍 2. 10. Regular Expression Matching 🔗

❓ Le problème 🔗

Implémentez la correspondance d’expressions régulières avec . (correspond à n’importe quel caractère unique) et * (correspond à zéro ou plusieurs occurrences de l’élément précédent). La correspondance doit couvrir l’intégralité de la chaîne d’entrée.

💡 L’intuition 🔗

Il s’agit d’un problème classique de programmation dynamique. Nous pouvons utiliser la mémoïsation pour éviter les calculs redondants.

À chaque combinaison de caractères de la chaîne s et du motif p, si le caractère suivant dans le motif est *, nous avons deux choix :

1. L’ignorer : utiliser zéro occurrence de l’élément précédent.
2. Continuer la correspondance : si les caractères actuels correspondent, consommer un caractère de s mais rester sur le * dans p pour potentiellement faire correspondre d’autres caractères.

⏱️ Complexité 🔗

• Temps : $O(S \times P)$ où $S$ et $P$ sont les longueurs de la chaîne et du motif.
• Espace : $O(S \times P)$ pour la table de mémoïsation 2D.

💻 Solution en Go 🔗

func isMatch(s string, p string) bool {
	sn, pn := len(s), len(p)
	memo := make([][]int, sn+1)
	for i := range memo {
		memo[i] = make([]int, pn+1)
	}
	return solveRegex(s, p, sn, pn, 0, 0, memo)
}

func solveRegex(s, p string, sn, pn, si, pi int, memo [][]int) bool {
	if memo[si][pi] == 1 { return false }
	if memo[si][pi] == 2 { return true }

	res := false
	if si == sn && pi == pn {
		res = true
	} else if pi+1 < pn && p[pi+1] == '*' {
		// Option A: Zero occurrences
		if solveRegex(s, p, sn, pn, si, pi+2, memo) {
			res = true
		// Option B: One or more occurrences (if current char matches)
		} else if si < sn && (p[pi] == '.' || p[pi] == s[si]) && solveRegex(s, p, sn, pn, si+1, pi, memo) {
			res = true
		}
	} else if si < sn && pi < pn && (p[pi] == '.' || p[pi] == s[si]) {
		// Normal character match
		res = solveRegex(s, p, sn, pn, si+1, pi+1, memo)
	}

	if res {
		memo[si][pi] = 2
	} else {
		memo[si][pi] = 1
	}
	return res
}

🌳 3. 124. Binary Tree Maximum Path Sum 🔗

❓ Le problème 🔗

Étant donné un arbre binaire non vide, trouvez la somme maximale d’un chemin. Un chemin peut monter ou descendre le long des connexions parent-enfant, mais n’a pas besoin de passer par la racine.

💡 L’intuition 🔗

Nous utilisons un parcours en profondeur (DFS). À chaque nœud, nous évaluons deux types de chemins :

1. Prolongeable (fromRoot) : le chemin maximal partant du nœud actuel et descendant dans l’une de ses branches. Un nœud parent peut utiliser ce chemin.
2. Non prolongeable (other) : le chemin maximal entièrement contenu dans le sous-arbre actuel (par exemple, partant de l’enfant gauche, remontant jusqu’au nœud actuel et redescendant vers l’enfant droit). Ce chemin est « fermé » et ne peut pas être prolongé vers le haut jusqu’à un parent.

Notre maximum global sera le plus élevé de tous les chemins « non prolongeables » trouvés, ou le chemin prolongeable de la racine.

⏱️ Complexité 🔗

• Temps : $O(N)$ car nous visitons chaque nœud exactement une fois.
• Espace : $O(H)$ où $H$ est la hauteur de l’arbre (pile de récursion).

💻 Solution en Go 🔗

import "math"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxPathSum(root *TreeNode) int {
	fromRoot, other := solveTree(root)
	if fromRoot > other {
		return fromRoot
	}
	return other
}

func solveTree(root *TreeNode) (int, int) {
	if root == nil {
		return math.MinInt, math.MinInt
	}

	left, otherLeft := solveTree(root.Left)
	right, otherRight := solveTree(root.Right)

	// Extendable path (can only pick one branch or stop at node)
	currentFromRoot := max([]int{
		root.Val,
		sum([]int{root.Val, left}),
		sum([]int{root.Val, right}),
	})

	// Closed path (can arch over the current node, or be completely inside a child)
	currentOther := max([]int{
		left, right, otherLeft, otherRight,
		sum([]int{root.Val, left, right}),
	})

	return currentFromRoot, currentOther
}

func max(s []int) int {
	res := math.MinInt
	for _, v := range s {
		if v > res { res = v }
	}
	return res
}

func sum(s []int) int {
	res := 0
	for _, v := range s {
		if v == math.MinInt { return math.MinInt }
		res += v
	}
	return res
}

🧮 4. 37. Sudoku Solver 🔗

❓ Le problème 🔗

Écrivez un programme pour résoudre une grille de Sudoku 9x9. Vous devez respecter les règles standards du Sudoku (lignes, colonnes et sous-grilles 3x3).

💡 L’intuition 🔗

Cela nécessite un algorithme de backtracking (retour sur trace). Pour le rendre efficace et éviter les erreurs de dépassement de temps limite (Time Limit Exceeded - TLE) sur LeetCode, nous optimisons la recherche en utilisant une heuristique : toujours essayer de remplir en premier la case vide ayant le moins de chiffres valides possibles. Nous utilisons des tableaux booléens pour vérifier instantanément si un chiffre est disponible dans une ligne, une colonne ou une sous-grille 3x3.

⏱️ Complexité 🔗

• Temps : $O(9^M)$ où $M$ est le nombre de cases vides, mais fortement élagué en pratique grâce à l’heuristique.
• Espace : $O(1)$ puisque la grille fait toujours 9x9 et que nos tableaux booléens ont une taille fixe.

💻 Solution en Go 🔗

func solveSudoku(board [][]byte) {
	var rows, cols [9][9]bool
	var boxes [3][3][9]bool

	// Populate initial state
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] != '.' {
				idx := board[i][j] - '1'
				rows[i][idx], cols[j][idx], boxes[i/3][j/3][idx] = true, true, true
			}
		}
	}
	backtrackSudoku(board, &rows, &cols, &boxes)
}

func backtrackSudoku(board [][]byte, rows, cols *[9][9]bool, boxes *[3][3][9]bool) bool {
	bestI, bestJ := -1, -1
	minOptions := 10 // Start higher than the max possible options (9)

	// Heuristic: Find the cell with the fewest valid options
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] == '.' {
				options := 0
				for val := 0; val < 9; val++ {
					if !rows[i][val] && !cols[j][val] && !boxes[i/3][j/3][val] {
						options++
					}
				}
				if options < minOptions {
					minOptions = options
					bestI, bestJ = i, j
				}
			}
		}
	}

	// Base case: No empty cells left
	if bestI == -1 { return true }

	// Try placing valid numbers in the chosen optimal cell
	for val := 0; val < 9; val++ {
		if !rows[bestI][val] && !cols[bestJ][val] && !boxes[bestI/3][bestJ/3][val] {
			board[bestI][bestJ] = byte(val + '1')
			rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = true, true, true

			if backtrackSudoku(board, rows, cols, boxes) {
				return true
			}

			// Backtrack
			board[bestI][bestJ] = '.'
			rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = false, false, false
		}
	}
	return false
}

🎓 5. 1494. Parallel Courses II 🔗

❓ Le problème 🔗

On vous donne un entier $n$, qui indique qu’il y a $n$ cours numérotés de $1$ à $n$. On vous donne également un tableau relations où relations[i] = [prevCourse, nextCourse], représentant une relation de prérequis. Au cours d’un semestre, vous pouvez suivre au maximum $k$ cours. Renvoyez le nombre minimum de semestres nécessaires pour suivre tous les cours.

💡 L’intuition 🔗

Comme $n$ est petit ($n \leq 15$), nous pouvons utiliser un parcours en largeur (BFS) combiné à des masques de bits (Bitmasks). Un masque de bits représente l’état des cours que nous avons terminés. À chaque semestre, nous identifions tous les cours disponibles (dont les prérequis sont entièrement remplis). Si le nombre de cours disponibles dépasse $k$, nous devons parcourir toutes les combinaisons possibles de taille $k$ en énumérant les sous-masques. Nous utilisons un tableau visited pour éviter de revisiter les mêmes combinaisons.

⏱️ Complexité 🔗

• Temps : $O(3^N)$ dans le pire des cas, car nous parcourons les sous-masques des cours disponibles.
• Espace : $O(2^N)$ pour stocker les états visités et la file BFS.

💻 Solution en Go 🔗

func minNumberOfSemesters(n int, relations [][]int, k int) int {
	// prerequisites[i] is a bitmask of courses that must be taken before course i
	prerequisites := make([]int, n)
	for _, relation := range relations {
		prevCourse := relation[0] - 1
		nextCourse := relation[1] - 1
		prerequisites[nextCourse] |= 1 << prevCourse
	}

	// states and costs act as a BFS queue
	states := []int{0}
	costs := []int{0}
	added := map[int]bool{0: true}

	for cur := 0; ; cur++ {
		state := states[cur]
		cost := costs[cur]

		// Base case: All courses have been taken
		if state == (1<<n)-1 {
			return cost
		}

		// Find all courses available to take this semester
		courses := []int{}
		next := state
		for course := 0; course < n; course++ {
			bit := 1 << course
			if (state&bit) == 0 && (prerequisites[course]|state) == state {
				courses = append(courses, course)
				next |= bit
			}
		}

		add := func(next int) {
			if added[next] {
				return
			}
			added[next] = true
			states = append(states, next)
			costs = append(costs, cost+1)
		}

		// If we can take all available courses in one semester, do so
		if len(courses) <= k {
			add(next)
			continue
		}

		// Otherwise, explore all combinations of size k
		var addStates func(next, k, from int)
		addStates = func(next, k, from int) {
			if k == 0 {
				add(next)
				return
			}
			for i := from; i < len(courses); i++ {
				addStates(next|(1<<courses[i]), k-1, i+1)
			}
		}
		addStates(state, k, 0)
	}
}

📐 6. 363. Max Sum of Rectangle No Larger Than K 🔗

❓ Le problème 🔗

Étant donné une matrice $m \times n$ et un entier $k$, renvoyez la somme maximale d’un rectangle dans la matrice telle que sa somme ne soit pas supérieure à $k$.

💡 L’intuition 🔗

Nous pouvons compresser la matrice 2D en un tableau 1D en fixant les limites de colonnes gauche et droite. Une fois que nous avons un tableau 1D représentant les sommes des lignes entre ces colonnes, le problème se réduit à trouver une somme de sous-tableau $\leq k$. En maintenant une liste triée de sommes préfixes (à l’aide d’un arbre binaire de recherche ou d’une simple insertion dans un tableau trié), nous pouvons rechercher efficacement la plus petite somme préfixe qui satisfait current_prefix - past_prefix <= k, ou précalculer une table de sommes préfixes 2D pour interroger n’importe quel sous-rectangle en temps $O(1)$.

⏱️ Complexité 🔗

• Temps : $O(R^2 \times C^2)$ en utilisant des sommes préfixes 2D (ou $O(C^2 \times R \log R)$ avec des sommes préfixes 1D triées, où $C$ représente les colonnes et $R$ les lignes).
• Espace : $O(R \times C)$ pour la matrice de sommes préfixes 2D (ou $O(R)$ pour les sommes de lignes compressées en 1D).

💻 Solution en Go 🔗

import "math"

func maxSumSubmatrix(matrix [][]int, k int) int {
	n := len(matrix)
	m := len(matrix[0])
	res := math.MinInt
	sums := make([][]int, n)
	for i := 0; i < n; i++ {
		sums[i] = make([]int, m)
	}

	// Precompute 2D prefix sums
	sums[0][0] = matrix[0][0]
	for i := 1; i < n; i++ {
		sums[i][0] = matrix[i][0] + sums[i-1][0]
	}
	for j := 1; j < m; j++ {
		sums[0][j] = matrix[0][j] + sums[0][j-1]
	}
	for i := 1; i < n; i++ {
		for j := 1; j < m; j++ {
			sums[i][j] = matrix[i][j] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]
		}
	}

	// Evaluate all possible subrectangles using inclusion-exclusion
	for starti := 0; starti < n; starti++ {
		for startj := 0; startj < m; startj++ {
			for endi := starti; endi < n; endi++ {
				for endj := startj; endj < m; endj++ {
					sum := sums[endi][endj]
					if starti > 0 {
						sum -= sums[starti-1][endj]
					}
					if startj > 0 {
						sum -= sums[endi][startj-1]
					}
					if starti > 0 && startj > 0 {
						sum += sums[starti-1][startj-1]
					}
					if sum <= k && sum > res {
						res = sum
					}
				}
			}
		}
	}
	return res
}

🔗 7. 685. Redundant Connection II 🔗

❓ Le problème 🔗

Dans un graphe orienté, chaque nœud a exactement un parent, à l’exception du nœud racine qui n’en a aucun. Une arête orientée supplémentaire est ajoutée. Trouvez l’arête qui peut être supprimée pour que le graphe résultant soit un arbre enraciné valide. S’il existe plusieurs réponses, renvoyez celle qui apparaît en dernier dans l’entrée.

💡 L’intuition 🔗

Comme il s’agit d’un graphe orienté, l’arête ajoutée crée l’un des deux problèmes suivants (ou les deux) :

1. Un nœud se retrouve avec deux parents.
2. Un cycle est formé.

Nous analysons d’abord le graphe pour voir si un nœud a deux parents. Si c’est le cas, l’arête redondante doit être l’une des deux arêtes pointant vers ce nœud. Sinon, l’arête supplémentaire forme un cycle orienté. Nous pouvons tester les arêtes candidates dans l’ordre inverse de l’entrée et vérifier via un parcours DFS (ou Union-Find) si la suppression de l’arête candidate laisse un arbre enraciné valide où tous les $N$ nœuds sont accessibles depuis la racine sans cycles.

⏱️ Complexité 🔗

• Temps : $O(N^2)$ en utilisant une vérification par DFS (ou $O(N \times \alpha(N))$ avec Union-Find, où $\alpha$ est la fonction inverse d’Ackermann).
• Espace : $O(N)$ pour les tables d’adjacence et l’ensemble des nœuds visités.

💻 Solution en Go 🔗

func findRedundantDirectedConnection(edges [][]int) []int {
	n := len(edges)
	parents := map[int][]int{}
	outs := map[int][]int{}
	for _, edge := range edges {
		src := edge[0] - 1
		dst := edge[1] - 1
		parents[dst] = append(parents[dst], src)
		outs[src] = append(outs[src], dst)
	}

	roots := map[int]bool{}
	bad := -1
	for i := 0; i < n; i++ {
		if len(parents[i]) == 0 {
			roots[i] = true
		}
		if len(parents[i]) > 1 {
			bad = i
		}
	}

	if len(roots) == 0 {
		for i := 0; i < n; i++ {
			if check(n, outs, i, -1, -1, map[int]bool{}) {
				roots[i] = true
			}
		}
	}

	if len(roots) > 1 {
		for i := len(edges) - 1; i >= 0; i-- {
			edge := edges[i]
			src := edge[0] - 1
			dst := edge[1] - 1
			if roots[dst] {
				return []int{src + 1, dst + 1}
			}
		}
	}

	for root := range roots {
		if len(parents[root]) > 0 {
			return []int{parents[root][0] + 1, root + 1}
		}
		for from := len(parents[bad]) - 1; from >= 0; from-- {
			if check(n, outs, root, parents[bad][from], bad, map[int]bool{}) {
				return []int{parents[bad][from] + 1, bad + 1}
			}
		}
	}
	return []int{-1, -1}
}

func check(n int, outs map[int][]int, from, badfrom, badto int, visited map[int]bool) bool {
	if visited[from] {
		return false
	}
	visited[from] = true
	if len(visited) == n {
		return true
	}
	for _, to := range outs[from] {
		if from == badfrom && to == badto {
			continue
		}
		if check(n, outs, to, badfrom, badto, visited) {
			return true
		}
	}
	return false
}

Vous avez apprécié cette analyse ? Les problèmes LeetCode Hard demandent de la patience, mais l’étude des schémas sous-jacents rend le processus reproductible. Continuez à construire, continuez à vous entraîner, et bonne chance pour vos entretiens !