🧩 LeetCode Hard meistern: 7 komplexe Lösungen erklärt 🔗

Das Lösen von „LeetCode Hard“-Problemen fühlt sich oft so an, als würde man gegen eine Wand laufen. Zerlegt man sie jedoch in verständliche Muster – wie dynamische Programmierung, Backtracking und Graphentheorie –, werden sie weitaus zugänglicher.

In diesem Beitrag teile ich 7 der spannendsten LeetCode-Hard-Probleme, die ich in Go gelöst habe. Um diesen Leitfaden so nützlich wie möglich zu gestalten, habe ich die Erklärungen stark auf die Kernintuition und die Komplexität konzentriert, damit der Sprung von der Aufgabenstellung zum funktionierenden Code leichter nachvollziehbar wird.

📑 Inhaltsverzeichnis 🔗

🔢 1. 60. Permutation Sequence 🔗

❓ Das Problem 🔗

Gegeben seien $n$ und $k$. Geben Sie die $k$-te Permutationsfolge der Zahlen von $1$ bis $n$ zurück. Für $n = 3$ lauten die Permutationen beispielsweise: "123", "132", "213", "231", "312", "321". Für $k = 3$ lautet die Antwort "213".

💡 Die Intuition 🔗

Anstatt alle Permutationen zu generieren (was zu langsam wäre), können wir einen mathematischen Ansatz nutzen, der auf Fakultäten basiert.

Für $n$ Ziffern gibt es insgesamt $n!$ Permutationen. Wenn wir die erste Ziffer festlegen, bleiben $(n-1)!$ Permutationen der verbleibenden Ziffern übrig. Wir können die erste Ziffer bestimmen, indem wir berechnen, in welchen Block von $(n-1)!$ Permutationen die $k$-te Permutation fällt. Der Index unserer nächsten Ziffer in einer sortierten Liste verfügbarer Ziffern ist einfach $(k-1) / (n-1)!$. Nachdem wir eine Ziffer ausgewählt haben, aktualisieren wir $k$ auf den Rest $k \bmod (n-1)!$ und rufen die Funktion rekursiv auf.

⏱️ Komplexität 🔗

• Zeit: $O(N^2)$, da das Löschen eines Elements aus einem Slice $O(N)$ Zeit benötigt und wir dies $N$-mal durchführen.
• Speicher: $O(N)$ für den Rekursions-Stack und das Ziffern-Array.

💻 Go-Lösung 🔗

import "fmt"

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

	// Fakultäten berechnen und das Ziffern-Slice füllen
	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 {
	// Ermitteln, in welchen Permutationsblock 'k' fällt
	index := k / factorial
	res := fmt.Sprintf("%d", digits[index])

	if n <= 0 {
		return res
	}

	// k für die nächste Ebene aktualisieren: k % factorial
	// Fakultät für die nächste Ebene aktualisieren: factorial / n
	// Die ausgewählte Ziffer aus dem Slice entfernen
	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 🔗

❓ Das Problem 🔗

Implementieren Sie den Abgleich regulärer Ausdrücke mit . (passt auf ein beliebiges einzelnes Zeichen) und * (passt auf null oder mehr Vorkommen des vorangehenden Elements). Der Abgleich muss den gesamten Eingabestring abdecken.

💡 Die Intuition 🔗

Dies ist ein klassisches Problem für dynamische Programmierung. Wir können Memoisation verwenden, um redundante Berechnungen zu vermeiden.

Bei jeder beliebigen Zeichenkombination aus String s und Muster p haben wir, falls das nächste Zeichen im Muster ein * ist, zwei Möglichkeiten:

1. Überspringen: Null Vorkommen des vorangehenden Elements verwenden.
2. Weiter abgleichen: Wenn die aktuellen Zeichen übereinstimmen, konsumieren wir ein Zeichen aus s, bleiben aber in p auf dem *, um potenziell weitere Zeichen abzugleichen.

⏱️ Komplexität 🔗

• Zeit: $O(S \times P)$, wobei $S$ und $P$ die Längen des Strings und des Musters sind.
• Speicher: $O(S \times P)$ für die 2D-Memoisationstabelle.

💻 Go-Lösung 🔗

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: Null Vorkommen
		if solveRegex(s, p, sn, pn, si, pi+2, memo) {
			res = true
		// Option B: Ein oder mehr Vorkommen (falls aktuelles Zeichen passt)
		} 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]) {
		// Normaler Zeichenabgleich
		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 🔗

❓ Das Problem 🔗

Gegeben sei ein nicht-leerer Binärbaum. Finden Sie die maximale Pfadsumme. Ein Pfad kann entlang von Eltern-Kind-Verbindungen nach oben oder unten verlaufen, muss aber nicht durch die Wurzel führen.

💡 Die Intuition 🔗

Wir verwenden die Tiefensuche (Depth-First Search, DFS). An jedem Knoten bewerten wir zwei Arten von Pfaden:

1. Erweiterbar (fromRoot): Der maximale Pfad, der am aktuellen Knoten beginnt und einen seiner Zweige hinunterläuft. Ein Elternknoten kann diesen Pfad weiterverwenden.
2. Nicht erweiterbar (other): Der maximale Pfad, der vollständig im aktuellen Teilbaum enthalten ist (z. B. vom linken Kind hinauf zum aktuellen Knoten und hinunter zum rechten Kind). Dieser Pfad ist „abgeschlossen“ und kann nicht nach oben zu einem Elternknoten erweitert werden.

Unser globales Maximum ist das höchste aller gefundenen „nicht erweiterbaren“ Pfade oder der erweiterbare Pfad der Wurzel.

⏱️ Komplexität 🔗

• Zeit: $O(N)$, da wir jeden Knoten genau einmal besuchen.
• Speicher: $O(H)$, wobei $H$ die Höhe des Baums ist (Rekursions-Stack).

💻 Go-Lösung 🔗

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)

	// Erweiterbarer Pfad (kann nur einen Zweig wählen oder am Knoten stoppen)
	currentFromRoot := max([]int{
		root.Val,
		sum([]int{root.Val, left}),
		sum([]int{root.Val, right}),
	})

	// Abgeschlossener Pfad (kann über den aktuellen Knoten laufen oder ganz in einem Kind liegen)
	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 🔗

❓ Das Problem 🔗

Schreiben Sie ein Programm, das ein 9x9-Sudoku-Rätsel löst. Dabei müssen die Standard-Sudoku-Regeln (Zeilen, Spalten und 3x3-Teilblöcke) eingehalten werden.

💡 Die Intuition 🔗

Dies erfordert einen Backtracking-Algorithmus. Um ihn effizient zu gestalten und „Time Limit Exceeded“-Fehler (TLE) auf LeetCode zu vermeiden, optimieren wir die Suche mithilfe einer Heuristik: Versuche immer zuerst, das leere Feld mit den wenigsten möglichen gültigen Zahlen zu füllen. Wir verwenden boolesche Arrays, um sofort zu prüfen, ob eine Zahl in einer Zeile, einer Spalte oder einem 3x3-Block verfügbar ist.

⏱️ Komplexität 🔗

• Zeit: $O(9^M)$, wobei $M$ die Anzahl der leeren Felder ist, in der Praxis jedoch durch die Heuristik stark beschnitten (Pruning).
• Speicher: $O(1)$, da das Spielfeld immer 9x9 groß ist und unsere booleschen Arrays feste Größen haben.

💻 Go-Lösung 🔗

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

	// Anfangszustand erfassen
	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 // Höher starten als die maximal möglichen Optionen (9)

	// Heuristik: Finde das Feld mit den wenigsten gültigen Optionen
	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
				}
			}
		}
	}

	// Basisfall: Keine leeren Felder mehr übrig
	if bestI == -1 { return true }

	// Versuche, gültige Zahlen in das gewählte optimale Feld einzutragen
	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
			}

			// Backtracking
			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 🔗

❓ Das Problem 🔗

Gegeben sei eine ganze Zahl $n$, die angibt, dass es $n$ Kurse gibt, die von $1$ bis $n$ nummeriert sind. Außerdem ist ein Array relations gegeben, wobei relations[i] = [prevCourse, nextCourse] eine Voraussetzungsbeziehung darstellt. In einem Semester können Sie höchstens $k$ Kurse belegen. Geben Sie die minimale Anzahl an Semestern zurück, die benötigt wird, um alle Kurse abzuschließen.

💡 Die Intuition 🔗

Da $n$ klein ist ($n \leq 15$), können wir eine Breitensuche (Breadth-First Search, BFS) in Kombination mit Bitmasken verwenden. Eine Bitmaske repräsentiert den Zustand der Kurse, die wir bereits abgeschlossen haben. In jedem Semester ermitteln wir alle verfügbaren Kurse (deren Voraussetzungen vollständig erfüllt sind). Wenn die Anzahl der verfügbaren Kurse $k$ übersteigt, müssen wir mithilfe von Submasken-Aufzählung durch alle möglichen Kombinationen der Größe $k$ iterieren. Wir nutzen ein visited-Map/Array, um zu verhindern, dass dieselben Kombinationen mehrfach besucht werden.

⏱️ Komplexität 🔗

• Zeit: $O(3^N)$ im ungünstigsten Fall, da wir über die Submasken der verfügbaren Kurse iterieren.
• Speicher: $O(2^N)$, um die besuchten Zustände und die BFS-Warteschlange zu speichern.

💻 Go-Lösung 🔗

func minNumberOfSemesters(n int, relations [][]int, k int) int {
	// prerequisites[i] ist eine Bitmaske der Kurse, die vor Kurs i belegt werden müssen
	prerequisites := make([]int, n)
	for _, relation := range relations {
		prevCourse := relation[0] - 1
		nextCourse := relation[1] - 1
		prerequisites[nextCourse] |= 1 << prevCourse
	}

	// states und costs fungieren als BFS-Warteschlange
	states := []int{0}
	costs := []int{0}
	added := map[int]bool{0: true}

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

		// Basisfall: Alle Kurse wurden abgeschlossen
		if state == (1<<n)-1 {
			return cost
		}

		// Alle Kurse finden, die in diesem Semester belegt werden können
		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)
		}

		// Wenn wir alle verfügbaren Kurse in einem Semester belegen können, tun wir das
		if len(courses) <= k {
			add(next)
			continue
		}

		// Andernfalls alle Kombinationen der Größe k untersuchen
		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 🔗

❓ Das Problem 🔗

Gegeben seien eine $m \times n$-Matrix und eine ganze Zahl $k$. Geben Sie die maximale Summe eines Rechtecks innerhalb der Matrix zurück, sodass dessen Summe nicht größer als $k$ ist.

💡 Die Intuition 🔗

Wir können die 2D-Matrix in ein 1D-Array komprimieren, indem wir die linke und rechte Spaltengrenze fixieren. Sobald wir ein 1D-Array haben, das die Zeilensummen zwischen diesen Spalten darstellt, reduziert sich das Problem auf die Suche nach einer Teilarray-Summe $\leq k$. Indem wir eine sortierte Liste von Präfixsummen führen (über einen binären Suchbaum oder einfaches Einfügen in ein sortiertes Array), können wir effizient die kleinste Präfixsumme abfragen, die current_prefix - past_prefix <= k erfüllt, oder eine 2D-Präfixsummentabelle vorberechnen, um jedes Teilrechteck in $O(1)$ Zeit abzufragen.

⏱️ Komplexität 🔗

• Zeit: $O(R^2 \times C^2)$ mit 2D-Präfixsummen (oder $O(C^2 \times R \log R)$ mit sortierten 1D-Präfixsummen, wobei $C$ die Spalten und $R$ die Zeilen sind).
• Speicher: $O(R \times C)$ für die 2D-Präfixsummenmatrix (oder $O(R)$ für 1D-komprimierte Zeilensummen).

💻 Go-Lösung 🔗

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)
	}

	// 2D-Präfixsummen vorberechnen
	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]
		}
	}

	// Alle möglichen Teilrechtecke mittels Inklusions-Exklusions-Prinzip auswerten
	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 🔗

❓ Das Problem 🔗

In einem gerichteten Graphen hat jeder Knoten genau einen Elternknoten, mit Ausnahme des Wurzelknotens, der keinen Elternknoten besitzt. Nun wird eine zusätzliche gerichtete Kante hinzugefügt. Finden Sie die Kante, die entfernt werden kann, sodass der resultierende Graph ein gültiger gewurzelter Baum ist. Gibt es mehrere Lösungen, geben Sie diejenige zurück, die in der Eingabe als Letztes vorkommt.

💡 Die Intuition 🔗

Da es sich um einen gerichteten Graphen handelt, verursacht die hinzugefügte Kante eines von zwei Problemen (oder beide):

1. Ein Knoten erhält zwei Elternknoten.
2. Es entsteht ein Zyklus.

Wir prüfen zunächst, ob ein Knoten zwei Elternknoten hat. Ist dies der Fall, muss die redundante Kante eine der beiden Kanten sein, die auf diesen Knoten zeigen. Andernfalls bildet die zusätzliche Kante einen gerichteten Zyklus. Wir können Kandidatenkanten in umgekehrter Eingabereihenfolge testen und per DFS (oder Union-Find) überprüfen, ob das Entfernen der Kandidatenkante einen gültigen gewurzelten Baum hinterlässt, in dem alle $N$ Knoten von der Wurzel aus ohne Zyklen erreichbar sind.

⏱️ Komplexität 🔗

• Zeit: $O(N^2)$ bei Verwendung von DFS-Verifikation (oder $O(N \times \alpha(N))$ mit Union-Find, wobei $\alpha$ die inverse Ackermann-Funktion ist).
• Speicher: $O(N)$ für die Adjazenz-Maps und die Menge der besuchten Knoten.

💻 Go-Lösung 🔗

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
}

Hat Ihnen diese Aufschlüsselung gefallen? LeetCode-Hard-Probleme erfordern Geduld, aber das Studium der zugrunde liegenden Muster macht den Lösungsprozess reproduzierbar. Bleiben Sie dran, üben Sie weiter und viel Erfolg bei Ihren Interviews!