🧩 Dominando o LeetCode Hard: 7 Soluções Complexas Explicadas 🔗

Encarar problemas Hard (Difíceis) do LeetCode muitas vezes parece dar de cara com um muro. No entanto, dividi-los em padrões digeríveis — como Programação Dinâmica, Backtracking e Teoria dos Grafos — os torna muito mais acessíveis.

Neste post, compartilho 7 dos problemas Hard mais interessantes do LeetCode que resolvi em Go. Para tornar este guia o mais útil possível, destilei as explicações para focar fortemente na intuição central e na complexidade, facilitando o salto entre o enunciado do problema e o código funcional.

📑 Índice 🔗

🔢 1. 60. Permutation Sequence 🔗

❓ O Problema 🔗

Dados $n$ e $k$ , retorne a $k^{\text{ésima}}$ sequência de permutação dos números de $1$ a $n$ . Por exemplo, se $n = 3$ , as permutações são: "123", "132", "213", "231", "312", "321". Se $k = 3$ , a resposta é "213".

💡 A Intuição 🔗

Em vez de gerar todas as permutações (o que seria lento demais), podemos usar uma abordagem matemática baseada em fatoriais.

Para $n$ dígitos, existem $n!$ permutações no total. Se fixarmos o primeiro dígito, haverá $(n-1)!$ permutações dos dígitos restantes. Podemos determinar o primeiro dígito calculando em qual bloco de $(n-1)!$ permutações a $k^{\text{ésima}}$ permutação se encontra. O índice do nosso próximo dígito em uma lista ordenada de dígitos disponíveis será simplesmente $(k-1) / (n-1)!$ . Depois de escolher um dígito, atualizamos $k$ para ser o resto $k \bmod (n-1)!$ e aplicamos a recursão.

⏱️ Complexidade 🔗

Tempo: $O(N^2)$ , pois remover um elemento de um slice leva tempo $O(N)$ , e fazemos isso $N$ vezes.
Espaço: $O(N)$ para a pilha de recursão e o array de dígitos.

💻 Solução em 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 🔗

❓ O Problema 🔗

Implemente a correspondência de expressões regulares com . (corresponde a qualquer caractere único) e * (corresponde a zero ou mais ocorrências do elemento anterior). A correspondência deve cobrir toda a string de entrada.

💡 A Intuição 🔗

Este é um problema clássico de Programação Dinâmica. Podemos usar memoização para evitar cálculos redundantes.

Em qualquer combinação de caracteres da string s e do padrão p, se o próximo caractere no padrão for *, temos duas escolhas:

Pular: Usar zero ocorrências do elemento anterior.
Continuar combinando: Se os caracteres atuais coincidirem, consumir um caractere de s, mas permanecer no * em p para potencialmente combinar mais caracteres.

⏱️ Complexidade 🔗

Tempo: $O(S \times P)$ , onde $S$ e $P$ são os comprimentos da string e do padrão.
Espaço: $O(S \times P)$ para a tabela de memoização 2D.

💻 Solução em 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 🔗

❓ O Problema 🔗

Dada uma árvore binária não vazia, encontre a soma máxima de um caminho. Um caminho pode subir ou descer pelas conexões pai-filho, mas não precisa passar pela raiz.

💡 A Intuição 🔗

Usamos Busca em Profundidade (DFS). Em cada nó, avaliamos dois tipos de caminhos:

Estensível (fromRoot): O caminho máximo que começa no nó atual e desce por um de seus ramos. Um nó pai pode usar esse caminho.
Não Estensível (other): O caminho máximo inteiramente contido na subárvore atual (por exemplo, subindo do filho esquerdo até o nó atual e descendo para o filho direito). Esse caminho é “fechado” e não pode ser estendido para cima até um pai.

Nosso máximo global será o maior entre todos os caminhos “não estensíveis” que encontrarmos, ou o caminho estensível da raiz.

⏱️ Complexidade 🔗

Tempo: $O(N)$ , pois visitamos cada nó exatamente uma vez.
Espaço: $O(H)$ , onde $H$ é a altura da árvore (pilha de recursão).

💻 Solução em 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 🔗

❓ O Problema 🔗

Escreva um programa para resolver um quebra-cabeça de Sudoku 9x9. Você deve satisfazer as regras padrão do Sudoku (linhas, colunas e subcaixas 3x3).

💡 A Intuição 🔗

Isso requer um algoritmo de backtracking. Para torná-lo eficiente e evitar erros de Tempo Limite Excedido (TLE) no LeetCode, otimizamos a busca usando uma heurística: sempre tente preencher primeiro a célula vazia com o menor número possível de opções válidas. Usamos arrays booleanos para verificar instantaneamente se um número está disponível em uma linha, coluna ou caixa 3x3.

⏱️ Complexidade 🔗

Tempo: $O(9^M)$ , onde $M$ é o número de células vazias, mas fortemente podado na prática graças à heurística.
Espaço: $O(1)$ , já que o tabuleiro é sempre 9x9 e nossos arrays booleanos têm tamanhos fixos.

💻 Solução em 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 🔗

❓ O Problema 🔗

Você recebe um inteiro $n$ , indicando que existem $n$ cursos rotulados de $1$ a $n$ . Você também recebe um array relations onde relations[i] = [prevCourse, nextCourse], representando uma relação de pré-requisito. Em um semestre, você pode cursar no máximo $k$ disciplinas. Retorne o número mínimo de semestres necessários para concluir todos os cursos.

💡 A Intuição 🔗

Como $n$ é pequeno ( $n \leq 15$ ), podemos usar Busca em Largura (BFS) combinada com Máscaras de Bits (Bitmasks). Uma máscara de bits representa o estado dos cursos que já concluímos. Em cada semestre, identificamos todos os cursos disponíveis (cujos pré-requisitos foram totalmente atendidos). Se os cursos disponíveis excederem $k$ , devemos iterar por todas as combinações possíveis de tamanho $k$ usando enumeração de submáscaras. Usamos um mapa de visitados para evitar revisitar as mesmas combinações.

⏱️ Complexidade 🔗

Tempo: $O(3^N)$ no pior caso, pois iteramos pelas submáscaras de cursos disponíveis.
Espaço: $O(2^N)$ para armazenar os estados visitados e a fila da BFS.

💻 Solução em 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 🔗

❓ O Problema 🔗

Dada uma matriz $m \times n$ e um inteiro $k$ , retorne a soma máxima de um retângulo na matriz tal que sua soma não seja maior que $k$ .

💡 A Intuição 🔗

Podemos comprimir a matriz 2D em um array 1D fixando os limites das colunas esquerda e direita. Uma vez que temos um array 1D representando as somas das linhas entre essas colunas, o problema se reduz a encontrar a soma de um subarray $\leq k$ . Mantendo uma lista ordenada de somas de prefixos (usando uma árvore de busca binária ou inserção simples em array ordenado), podemos consultar eficientemente a menor soma de prefixo que satisfaça current_prefix - past_prefix <= k, ou pré-computar uma tabela de soma de prefixos 2D para consultar qualquer sub-retângulo em tempo $O(1)$ .

⏱️ Complexidade 🔗

Tempo: $O(R^2 \times C^2)$ usando somas de prefixos 2D (ou $O(C^2 \times R \log R)$ com somas de prefixos 1D ordenadas, onde $C$ são as colunas e $R$ são as linhas).
Espaço: $O(R \times C)$ para a matriz de soma de prefixos 2D (ou $O(R)$ para somas de linhas 1D comprimidas).

💻 Solução em 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 🔗

❓ O Problema 🔗

Em um grafo direcionado, cada nó tem exatamente um pai, exceto o nó raiz, que não tem pais. Uma aresta direcionada extra foi adicionada. Encontre a aresta que pode ser removida para que o grafo resultante seja uma árvore enraizada válida. Se houver múltiplas respostas, retorne a que ocorre por último na entrada.

💡 A Intuição 🔗

Como é um grafo direcionado, a aresta adicionada cria um de dois problemas (ou ambos):

Um nó passa a ter dois pais.
Um ciclo é formado.

Primeiro fazemos uma varredura para ver se algum nó tem dois pais. Se tiver, a aresta redundante deve ser uma das duas arestas que apontam para esse nó. Caso contrário, a aresta extra forma um ciclo direcionado. Podemos testar as arestas candidatas na ordem inversa da entrada e verificar via DFS (ou Union-Find) se a remoção da aresta candidata deixa uma árvore enraizada válida onde todos os $N$ nós são alcançáveis a partir da raiz sem ciclos.

⏱️ Complexidade 🔗

Tempo: $O(N^2)$ usando verificação por DFS (ou $O(N \times \alpha(N))$ com Union-Find, onde $\alpha$ é a função inversa de Ackermann).
Espaço: $O(N)$ para os mapas de adjacência e conjunto de visitados.

💻 Solução em 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
}

Gostou desta análise? Problemas Difíceis do LeetCode exigem paciência, mas estudar os padrões subjacentes torna o processo repetível. Continue construindo, continue praticando e boa sorte em suas entrevistas!

📚 Baixe Meu Ebook Gratuito 🔗

Baixe a edição offline selecionada de O Estilo de Vida do Kaue—um guia prático para otimizar 🍏 Saúde, 💰 Riqueza, ❤️ Amor e 🧘 Sentido.

📬 Assine Minha Newsletter 🔗

Receba notificações quando eu publicar novos ensaios, resumos de livros e guias práticos sobre como viver bem. Sem spam—cancele quando quiser.

💬 Comentários e Discussão 🔗

Tem alguma pergunta, perspectiva ou sugestão? Compartilhe suas ideias abaixo. Os comentários usam o GitHub Discussions (sem anúncios e sem spam)—clique em Entrar com o GitHub abaixo para comentar ou reagir (criar uma conta gratuita no GitHub leva menos de um minuto).

AVISO LEGAL: O conteúdo deste site tem finalidade exclusivamente informativa e educacional e não constitui aconselhamento médico, psicológico, financeiro, de investimentos, tributário ou jurídico. As ideias, a curadoria e as opiniões aqui apresentadas são exclusivamente minhas e não representam as do meu empregador. Os resumos de livros, palestras e artigos são comentários educacionais independentes e permanecem propriedade intelectual de seus respectivos autores. Ferramentas de IA podem ser utilizadas para auxiliar na edição, formatação e síntese; embora todos os esforços sejam feitos para garantir a precisão, erros podem ocorrer. PRIVACIDADE: Este site utiliza serviços de terceiros para inscrição opcional em newsletter (follow.it), comentários (giscus / GitHub Discussions) e mídia incorporada (YouTube), que podem processar endereços IP e cookies dos visitantes de acordo com suas respectivas políticas de privacidade.