🧩 Mastering LeetCode Hard: 7 Complex Solutions Explained 🔗

Tackling LeetCode Hard problems can often feel like hitting a brick wall. However, breaking them down into digestible patterns—like Dynamic Programming, Backtracking, and Graph Theory—makes them far more approachable.

In this post, I’m sharing 7 of the most interesting LeetCode Hard problems I’ve solved in Go. To make this guide as useful as possible, I’ve distilled the explanations to focus heavily on the core intuition and complexity, making the leap from the problem statement to the working code easier to understand.

📑 Table of Contents 🔗

🔢 1. 60. Permutation Sequence 🔗

❓ The Problem 🔗

Given $n$ and $k$ , return the $k^{\text{th}}$ permutation sequence of numbers from $1$ to $n$ . For example, if $n = 3$ , the permutations are: "123", "132", "213", "231", "312", "321". If $k = 3$ , the answer is "213".

💡 The Intuition 🔗

Instead of generating all permutations (which would be too slow), we can use a mathematical approach leveraging factorials.

For $n$ digits, there are $n!$ total permutations. If we fix the first digit, there are $(n-1)!$ permutations of the remaining digits. We can determine the first digit by calculating which block of $(n-1)!$ permutations the $k^{\text{th}}$ permutation falls into. The index of our next digit in a sorted list of available digits will simply be $(k-1) / (n-1)!$ . After picking a digit, we update $k$ to be the remainder $k \bmod (n-1)!$ and recurse.

⏱️ Complexity 🔗

Time: $O(N^2)$ because deleting an element from a slice takes $O(N)$ time, and we do this $N$ times.
Space: $O(N)$ for the recursion stack and the digits array.

💻 Go Solution 🔗

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 🔗

❓ The Problem 🔗

Implement regular expression matching with . (matches any single character) and * (matches zero or more of the preceding element). The matching must cover the entire input string.

💡 The Intuition 🔗

This is a classic Dynamic Programming problem. We can use memoization to avoid redundant computations.

At any given character combination of string s and pattern p, if the next character in the pattern is *, we have two choices:

Skip it: Use zero occurrences of the preceding element.
Keep matching: If the current characters match, consume one character from s but stay on the * in p to potentially match more.

⏱️ Complexity 🔗

Time: $O(S \times P)$ where $S$ and $P$ are the lengths of the string and pattern.
Space: $O(S \times P)$ for the 2D memoization table.

💻 Go Solution 🔗

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 🔗

❓ The Problem 🔗

Given a non-empty binary tree, find the maximum path sum. A path can go up or down parent-child connections but doesn’t need to pass through the root.

💡 The Intuition 🔗

We use Depth-First Search (DFS). At every node, we evaluate two types of paths:

Extendable (fromRoot): The max path starting at the current node and going down one of its branches. A parent node can use this path.
Not Extendable (other): The max path entirely contained within the current subtree (e.g., looping from the left child, up to the current node, and down to the right child). This path is “closed” and cannot be extended upwards to a parent.

Our global max will be the highest of all the “not extendable” paths we find, or the root’s extendable path.

⏱️ Complexity 🔗

Time: $O(N)$ because we visit every node exactly once.
Space: $O(H)$ where $H$ is the height of the tree (recursion stack).

💻 Go Solution 🔗

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 🔗

❓ The Problem 🔗

Write a program to solve a 9x9 Sudoku puzzle. You must satisfy standard Sudoku rules (rows, columns, and 3x3 sub-boxes).

💡 The Intuition 🔗

This requires a backtracking algorithm. To make it efficient and avoid Time Limit Exceeded (TLE) errors on LeetCode, we optimize the search by using a heuristic: always attempt to fill the empty cell with the fewest possible valid numbers first. We use boolean arrays to instantly check if a number is available in a row, column, or 3x3 box.

⏱️ Complexity 🔗

Time: $O(9^M)$ where $M$ is the number of empty cells, but heavily pruned in practice due to the heuristic.
Space: $O(1)$ since the board is always 9x9 and our boolean arrays are fixed sizes.

💻 Go Solution 🔗

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 🔗

❓ The Problem 🔗

You are given an integer $n$ , which indicates that there are $n$ courses labeled from $1$ to $n$ . You are also given an array relations where relations[i] = [prevCourse, nextCourse], representing a prerequisite relationship. In one semester, you can take at most $k$ courses. Return the minimum number of semesters needed to take all courses.

💡 The Intuition 🔗

Because $n$ is small ( $n \leq 15$ ), we can use Breadth-First Search (BFS) combined with Bitmasks. A bitmask represents the state of courses we’ve completed. In each semester, we identify all available courses (whose prerequisites are fully met). If the available courses exceed $k$ , we must iterate through all possible combinations of size $k$ using submask enumeration. We use a visited array to prevent revisiting the same combinations.

⏱️ Complexity 🔗

Time: $O(3^N)$ worst case, as we iterate through submasks of available courses.
Space: $O(2^N)$ to store the visited states and the BFS queue.

💻 Go Solution 🔗

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 🔗

❓ The Problem 🔗

Given an $m \times n$ matrix and an integer $k$ , return the max sum of a rectangle in the matrix such that its sum is no larger than $k$ .

💡 The Intuition 🔗

We can compress the 2D matrix into a 1D array by fixing the left and right column boundaries. Once we have a 1D array representing the row sums between those columns, the problem reduces to finding a subarray sum $\leq k$ . By maintaining a sorted list of prefix sums (using a binary search tree or simple sorted array insertion), we can efficiently query the smallest prefix sum that satisfies current_prefix - past_prefix <= k, or precompute a 2D prefix sum table to query any subrectangle in $O(1)$ time.

⏱️ Complexity 🔗

Time: $O(R^2 \times C^2)$ using 2D prefix sums (or $O(C^2 \times R \log R)$ with sorted 1D prefix sums, where $C$ is columns and $R$ is rows).
Space: $O(R \times C)$ for the 2D prefix sum matrix (or $O(R)$ for 1D compressed row sums).

💻 Go Solution 🔗

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 🔗

❓ The Problem 🔗

In a directed graph, every node has exactly one parent except for the root node, which has no parents. An extra directed edge is added. Find the edge that can be removed so the resulting graph is a valid rooted tree. If there are multiple answers, return the one occurring last in the input.

💡 The Intuition 🔗

Because it’s a directed graph, the added edge creates one of two issues (or both):

A node gets two parents.
A cycle is formed.

We first scan to see if any node has two parents. If it does, the redundant edge must be one of the two edges pointing to that node. Otherwise, the extra edge forms a directed cycle. We can test candidate edges in reverse input order and verify via DFS (or Union-Find) whether removing the candidate edge leaves a valid rooted tree where all $N$ nodes are reachable from the root without cycles.

⏱️ Complexity 🔗

Time: $O(N^2)$ using DFS verification (or $O(N \times \alpha(N))$ with Union-Find, where $\alpha$ is the Inverse Ackermann function).
Space: $O(N)$ for the adjacency maps and visited set.

💻 Go Solution 🔗

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
}

Enjoyed this breakdown? LeetCode Hard problems require patience, but studying the underlying patterns makes the process repeatable. Keep building, keep practicing, and good luck in your interviews!

📚 Download My Free Ebook 🔗

Get the curated offline edition of Kaue's Way of Life—a practical field guide to optimizing 🍏 Health, 💰 Wealth, ❤️ Love, and 🧘 Meaning.

📬 Join My Mailing List 🔗

Get notified when I publish new essays, book summaries, and practical guides on living well. No spam—unsubscribe anytime.

💬 Comments & Discussion 🔗

DISCLAIMER: The content on this site is for informational and educational purposes only and does not constitute medical, psychological, financial, investment, tax, or legal advice. The ideas, curation, and opinions presented here are my own and do not represent those of my employer. Book, lecture, and article summaries are independent educational commentary and remain the intellectual property of their respective authors. AI tools may be used to assist with editing, formatting, and synthesis; while every effort is made to ensure accuracy, errors may occur. PRIVACY: This site uses third-party services for cookieless analytics (Google Analytics), optional newsletter subscriptions (Mailchimp), comments (Disqus), live chat (Tawk.to), and embedded media (YouTube), which may process visitor IP addresses and cookies in accordance with their respective privacy policies.