Here are 7 interesting LeetCode hard solutions solved by me and explained by Gemini.
AI summary
The post provides explanations and Go language solutions for seven LeetCode hard problems. Each problem’s explanation covers the problem statement and a detailed solution approach.
The problems included are:
fromroot
) and another confined to the current subtree (other
).k
course limit per semester.k
.Problem
Given n and k, return the kth permutation sequence. For example, if n = 3, the permutations are: “123”, “132”, “213”, “231”, “312”, “321” If k = 3, the answer would be “213”.
Solution
This problem can be solved using a mathematical approach that leverages factorials. We want to find the kth permutation. The key idea is to determine which digit comes first, then which digit comes second, and so on.
For n digits, there are n! 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 kth permutation falls into. The index of the first digit in the sorted list of available digits will be (k-1) / (n-1)!. We use (k-1) because k is 1-indexed.
After selecting the first digit, we update k to be k % (n-1)! and recursively solve for the remaining (n-1) digits.
func getPermutation(n int, k int) string {
// factorial stores (n-1)! initially, and then
// (n-2)!, etc., for each step.
factorial := 1
// digits stores the available digits in
// sorted order.
digits := []int{}
// Calculate factorials and populate the
// digits slice.
for i := 1; i <= n; i++ {
factorial *= i
digits = append(digits, i)
}
// The solve function is a recursive helper.
// n: remaining number of digits to place
// (n-1 initially, then n-2, etc.)
// k: the updated k value (0-indexed)
// factorial: (remaining_digits - 1)!
// digits: the currently available digits
return solve(n-1, k-1, factorial/n, digits)
}
func solve(n, k, factorial int, digits []int)
string {
// Calculate the index of the digit to pick
// from the current 'digits' slice.
// This index tells us which block of
// permutations 'k' falls into.
index := k / factorial
// Convert the chosen digit to a string and
// append it to the result.
res := fmt.Sprintf("%d", digits[index])
if n <= 0 {
return res
}
// If there are more digits to place (n > 0),
// recursively call solve.
// Update k for the next level of recursion:
// k % factorial.
// This effectively finds the position
// within the block of permutations
// determined by the chosen digit.
// Update factorial for the next level:
// factorial / n.
// This becomes (n-2)! if n was (n-1), etc.
// Remove the selected digit from the
// 'digits' slice for the next recursive
// call.
res += solve(n-1, k%factorial, factorial/n,
append(digits[:index],
digits[index+1:]...))
return res
}
Problem
Implement regular expression matching with ‘.’ and ‘*’. ‘.’ matches any single character. ‘*’ matches zero or more of the preceding element. The matching should cover the entire input string (not partial).
Solution
This is a classic dynamic programming problem. We can use memoization to avoid redundant computations. Let solve(si, pi) be a function that returns true if s[si:] matches p[pi:].
Base Cases:
Recursive Steps:
Consider the current characters s[si] and p[pi].
Case 1:
The next character in p is ‘*’. (p[pi+1] == ‘*’) This means p[pi] can be matched zero or more times.
a) Zero occurrences:
Skip p[pi] and ‘*’: solve(si, pi+2)
b) One or more occurrences:
If s[si] matches p[pi] (or p[pi] is ‘.’), then consume s[si] and try to match the rest of s with the current p[pi] and ‘*’: solve(si+1, pi)
Case 2:
The next character in p is not ‘*’. If s[si] matches p[pi] (or p[pi] is ‘.’), then move to the next characters in both strings: solve(si+1, pi+1) Otherwise, it’s not a match.
Memoization:
Use a 2D array memo
to store
results.
0: uncomputed, 1: false, 2: true
func isMatch(s string, p string) bool {
sn := len(s)
pn := len(p)
memo := make([][]int, sn+1)
for i := 0; i < sn+1; i++ {
memo[i] = make([]int, pn+1)
}
return solve(s, p, sn, pn, 0, 0, memo)
}
func solve(s, p string, sn, pn, si, pi int,
memo [][]int) bool {
// Check memoization table
if memo[si][pi] == 1 {
return false
}
if memo[si][pi] == 2 {
return true
}
res := false
// Base case: Both strings are fully matched
if si == sn && pi == pn {
res = true
// Case 1: p[pi+1] is '*'
} else if pi+1 < pn && p[pi+1] == '*' {
// Option a: Zero occurrences of p[pi]
if solve(s, p, sn, pn, si, pi+2, memo) {
res = true
// Option b: One or more occurrences of
// p[pi]
// s[si] matches p[pi], consume s[si] and
// stay at current p[pi] (because '*' can
// match more)
} else if si < sn &&
(p[pi] == '.' || p[pi] == s[si]) &&
solve(s, p, sn, pn, si+1, pi, memo) {
res = true
}
// Case 2: p[pi+1] is not '*'
// s[si] matches p[pi], move to next
// characters in both strings
} else if si < sn && pi < pn &&
(p[pi] == '.' || p[pi] == s[si]) &&
solve(s, p, sn, pn, si+1, pi+1, memo) {
res = true
}
// Store result in memoization table
if res {
memo[si][pi] = 2
} else {
memo[si][pi] = 1
}
return res
}
Problem
Given a non-empty binary tree, find the maximum path sum. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to pass through the root. It can go down or up.
Solution
This problem can be solved using a recursive approach (Depth-First Search). For each node, we need to consider two types of maximum path sums:
fromroot
: The maximum path sum that starts at the
current node and goes downwards (to its
left or right child, or just the node
itself). This path is “extendable” upwards
by its parent.other
: The maximum path sum within
the subtree rooted at the current node,
which could either be a path that passes
through the current node (using both left
and right child paths), or a path entirely
within its left or right subtree.
This path is “not extendable” upwards by
its parent.The global maximum path sum will be the
maximum of all other
values computed for
every node, and also the fromroot
value
of the initial root.
The solve
function returns two integers:
The first integer is the maximum path sum
that includes the root
and can be
extended upwards (i.e., it considers
root.Val
+
max(left_fromroot, right_fromroot)).
The second integer is the maximum path sum
that can be found within the subtree rooted
at root
, regardless of whether it goes
through root
or not, and this path cannot
be extended upwards by its parent.
The final answer is the maximum between the
maximum path sum originating from the root
that can be extended upwards (fromroot
)
and the maximum path sum found anywhere
in the entire tree (other
).
func maxPathSum(root *TreeNode) int {
fromroot, other := solve(root)
if fromroot > other {
return fromroot
}
return other
}
func solve(root *TreeNode) (int, int) {
// Base case: If the node is nil, return
// negative infinity for both values
// as an empty path cannot contribute to a
// positive sum.
if root == nil {
return math.MinInt, math.MinInt
}
// Recursively get the path sums from the left
// and right children.
left, otherleft := solve(root.Left)
right, otherright := solve(root.Right)
// Calculate 'fromroot':
// Max path sum starting at 'root' and going
// down.
// It's either just the node's value, or the
// node's value plus the best path from its
// left child,
// or the node's value plus the best path from
// its right child.
// We take the maximum to ensure we pick the
// best extendable path.
currentFromRoot := max([]int{
root.Val, sum([]int{root.Val, left}),
sum([]int{root.Val, right})})
// Calculate 'other':
// Max path sum within the current subtree.
// This can be:
// - The maximum path sum within the left
// subtree (`left`).
// - The maximum path sum within the right
// subtree (`right`).
// - The maximum "other" path sum found in the
// left child's subtree (`otherleft`).
// - The maximum "other" path sum found in the
// right child's subtree (`otherright`).
// - A path that goes through the current
// `root`, using both left and right branches:
// `root.Val + left + right`.
currentOther := max([]int{
left, right, otherleft, otherright,
sum([]int{root.Val, left, right})})
return currentFromRoot, currentOther
}
// Helper function to find the maximum in a
// slice of integers.
func max(s []int) int {
res := math.MinInt
for _, v := range s {
if v > res {
res = v
}
}
return res
}
// Helper function to sum a slice of integers.
// If any element is MinInt, it means that path
// is not valid for summation,
// so we propagate MinInt to avoid incorrect
// large sums from negative infinity.
func sum(s []int) int {
res := 0
for _, v := range s {
if v == math.MinInt {
return math.MinInt
}
res += v
}
return res
}
Problem
Write a program to solve a Sudoku puzzle by filling the empty cells. A Sudoku board (9x9) must satisfy the following rules:
Solution
This problem can be solved using a
backtracking algorithm.
We’ll maintain three boolean arrays to keep
track of available numbers:
rows[i][num]
will be true if num+1
is
present in row i
.
cols[j][num]
will be true if num+1
is
present in column j
.
boxes[box_row][box_col][num]
will be true
if num+1
is present in the 3x3 box.
func solveSudoku(board [][]byte) {
// First, initialize the `rows`, `cols`, and
// `boxes` arrays based on the
// pre-filled numbers in the input `board`.
rows := [9][9]bool{}
cols := [9][9]bool{}
boxes := [3][3][9]bool{}
// Populate the initial state of the `rows`,
// `cols`, and `boxes` arrays.
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
ch := board[i][j]
if ch == '.' {
continue // Skip empty cells
}
// Convert character digit to 0-indexed
// integer (e.g., '1' -> 0, '9' -> 8)
index := int(ch - '1')
rows[i][index] = true
cols[j][index] = true
// i/3 and j/3 give the 3x3 box
// coordinates
boxes[i/3][j/3][index] = true
}
}
// Start the recursive backtracking process.
solve(board, rows, cols, boxes)
}
// solve is a recursive helper function that
// attempts to fill the Sudoku board.
// It returns true if a valid solution is found,
// false otherwise.
func solve(board [][]byte,
rows, cols [9][9]bool,
boxes [3][3][9]bool) bool {
// Find the empty cell with the fewest
// possible valid numbers (heuristic).
// This helps to prune the search space
// earlier, making the solution faster.
besti := 0
bestj := 0
// Stores possible numbers (0-8 for 1-9).
// Initialized with 10 to ensure
// `len(options) < len(best)` is true for the
// first empty cell.
best := make([]int, 10)
// True if an empty cell is found
found := false
// Iterate through the board to find the next
// empty cell to fill.
// Optimization: if `best` already has 1
// option, no need to look for a better cell.
for i := 0; i < 9 && len(best) > 1; i++ {
for j := 0; j < 9 && len(best) > 1; j++ {
ch := board[i][j]
if ch != '.' {
continue // Skip pre-filled cells
}
found = true // An empty cell is found
// Find all possible numbers for the
// current empty cell (i, j)
options := []int{}
// res represents 0-indexed digit
// (0 for '1', ..., 8 for '9')
for res := 0; res < 9; res++ {
// Check if placing `res+1` in (i, j)
// violates Sudoku rules
// This number is already used in the
// row, column, or box
if rows[i][res] || cols[j][res] ||
boxes[i/3][j/3][res] {
continue
}
// Add to possible options
options = append(options, res)
}
// If the current cell has fewer options
// than the `best` cell found so far,
// update `best` to this cell's options
// and coordinates.
if len(options) < len(best) {
best = options
besti = i
bestj = j
}
}
}
// Base Case:
// If no empty cells were found, the board is
// solved.
if !found {
return true
}
// Backtracking Step:
// Try each possible number for the selected
// `best` empty cell.
for _, move := range best {
// Try placing 'move+1' in
// board[besti][bestj]
rows[besti][move] = true
cols[bestj][move] = true
boxes[besti/3][bestj/3][move] = true
// Convert 0-indexed int back to char digit
board[besti][bestj] = byte(move) + '1'
// Recursively call solve for the next empty
// cell
// If the recursive call returns true, a
// solution is found
if solve(board, rows, cols, boxes) {
return true
}
// Backtrack:
// If the current move leads to no solution,
// undo the move
rows[besti][move] = false
cols[bestj][move] = false
boxes[besti/3][bestj/3][move] = false
// Reset the cell to empty
board[besti][bestj] = '.'
}
// If no number for the current empty cell
// leads to a solution, return false.
return false
}
Problem
You have ’n’ courses, labeled from 1 to ’n’. You are given a list of ‘relations’ where relations[i] = [prevCourse_i, nextCourse_i] indicates that prevCourse_i must be taken before nextCourse_i. In each semester, you can take at most ‘k’ courses. You cannot take two or more courses that have prerequisites not yet taken. The goal is to return the minimum number of semesters required to take all courses.
This problem can be modeled as finding the minimum number of semesters to complete all courses in a Directed Acyclic Graph (DAG) with a constraint on the number of courses per semester. This is a variation of topological sort combined with optimization, best solved with Breadth-First Search (BFS) on states represented by bitmasks, effectively a shortest path problem in a state graph.
Solution
Breadth-First Search (BFS) on Bitmasks
Since ’n’ is up to 15, we can use bitmasks
to represent the set of courses already
taken.
A bitmask mask
will represent the state
of courses: if the i-th bit is set, course
(i+1) has been taken.
We want to find the minimum number of
semesters (cost) to reach the state
(1 << n)-1
(all courses taken).
func minNumberOfSemesters(n int,
relations [][]int, k int) int {
// `prerequisites` array:
// `prerequisites[i]` will be a bitmask
// representing all courses that must be taken
// *before* course (i+1).
prerequisites := make([]int, n)
for _, relation := range relations {
prevCourse := relation[0] - 1 // 0-indexed
nextCourse := relation[1] - 1 // 0-indexed
// Set the bit for prevCourse in the
// prerequisites mask for nextCourse.
prerequisites[nextCourse] |=
1 << prevCourse
}
// `states` and `costs` arrays will act as a
// queue for BFS.
// `states` stores the bitmasks (current sets
// of completed courses).
// `costs` stores the number of semesters
// taken to reach that state.
// Start with the initial state:
// no courses taken (mask 0).
states := []int{0}
// Cost for initial state is 0 semesters.
costs := []int{0}
// `added` map acts as a `visited` set for
// BFS, to avoid re-processing states.
// It stores `true` for states that have
// already been added to the queue.
added := map[int]bool{0: true}
// BFS loop: `cur` is the index of the current
// state being processed in the queue.
for cur := 0; ; cur++ {
// Get the current set of completed courses.
state := states[cur]
// Get the semesters taken to reach this
// state.
cost := costs[cur]
// Base case: If all courses are taken
// (mask is (1<<n)-1), we found the minimum
// semesters.
if state == (1<<n)-1 {
return cost
}
// `courses` will store the list of courses
// that *can* be taken in the current
// semester.
// These are courses not yet taken, whose
// prerequisites are satisfied.
courses := []int{}
// `next` will represent the state after
// taking *all possible* courses in this
// semester.
next := state
for course := 0; course < n; course++ {
// Bitmask for the current course.
bit := 1 << course
// Check if:
// 1. The course is NOT already in the
// current `state` (not taken yet).
// 2. ALL prerequisites for `course` are
// present in `state`.
// This is checked by
// `(prerequisites[course] & state) ==
// prerequisites[course]`.
// If `prerequisites[course]` is a
// subset of `state`, this condition is
// true.
if (state&bit) == 0 &&
(prerequisites[course]|state) ==
state {
// Add to list of available courses.
courses = append(courses, course)
// Add to a temporary `next` state
// (potential full set of available
// courses).
next |= bit
}
}
// `add` is a helper function to add a new
// state to the BFS queue if it hasn't been
// added yet.
add := func(next int) {
if added[next] {
return
}
added[next] = true
// Add the new state.
states = append(states, next)
// Cost increases by 1 semester.
costs = append(costs, cost+1)
}
// If the number of `courses` that can be
// taken is less than or equal to `k`,
// we can take all of them in the current
// semester.
if len(courses) <= k {
// Add the state where all currently
// available courses are taken.
add(next)
// Move to the next state in the BFS
// queue.
continue
}
// If `len(courses) > k`, we can only pick
// 'k' courses from `courses`.
// We need to explore all combinations of
// 'k' courses from `courses`.
// This is done using a recursive
// backtracking function `addStates`.
var addStates func(next, k, from int)
addStates = func(next, k, from int) {
// Base case for `addStates`:
// If 'k' courses have been chosen.
if k == 0 {
// Add this new state to the BFS queue.
add(next)
return
}
// Iterate through available courses
// starting from `from` index to avoid
// duplicate combinations.
for i := from; i < len(courses); i++ {
// Recursively call `addStates` to
// choose the next course.
// `next | (1 << courses[i])`:
// Add the current course to the `next`
// state.
// `k-1`: One less course to choose.
// `i+1`: Start searching from the next
// index to ensure unique combinations.
addStates(
next|(1<<courses[i]), k-1, i+1)
}
}
// Initial call to `addStates`:
// start with the `state` before choosing
// any new courses,
// choose `k` courses, starting from the
// first available course (index 0).
addStates(state, k, 0)
}
}
Problem
Given an m x n
matrix matrix
and an integer k
, find the maximum sum of a rectangle in the matrix such that its sum is no larger than k
. The rectangle can be of any size (1x1 to m x n).
Solution
This problem is a variation of the “Maximum Subarray Sum” problem, extended to 2D. A brute-force approach checking all possible rectangles would be O((mn)^3) or O(m^2n^2) depending on how sums are calculated. This is too slow for larger matrices.
The solution uses a 2D prefix sum array to efficiently calculate the sum of any subrectangle.
sums
of the same dimensions as the input matrix
is created.sums[i][j]
will store the sum of all elements in the rectangle from (0,0)
to (i,j)
.sums
array is populated iteratively.sums[i][j] = matrix[i][j] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]
(with appropriate handling for boundary conditions where i
or j
is 0). This formula is based on the inclusion-exclusion principle.starti
: row index for the top edge of the rectangle.startj
: column index for the left edge of the rectangle.endi
: row index for the bottom edge of the rectangle.endj
: column index for the right edge of the rectangle.(starti, startj, endi, endj)
, the sum of the current rectangle (currentSum
) is calculated using the precomputed sums
array. The calculation uses the same inclusion-exclusion principle:
currentSum = sums[endi][endj] - sums[starti-1][endj] - sums[endi][startj-1] + sums[starti-1][startj-1]
(again, with boundary checks).currentSum
is less than or equal to k
and currentSum
is greater than the current maximum found (res
), then res
is updated to currentSum
.The time complexity of this approach is O(N^2 * M^2) because of the four nested loops, where N is the number of rows and M is the number of columns. This is a complete brute-force approach after precalculating prefix sums.
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)
}
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]
}
}
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
}
Problem
In a directed graph with N
nodes and N
edges, an extra edge has been added to what was originally a directed tree. This added edge can cause one of two issues:
The task is to find this redundant edge. If there are multiple possible redundant edges that could be removed to restore the tree structure, you must return the one that appears last in the input edges
array.
Solution
The solution involves a multi-step approach to identify the redundant edge, considering the two possible scenarios:
edges
and build an “in-degree” map (or parents
map in the code) that records all parents for each node, and an “out-degree” map (outs
map) for children.bad
) ends up with an in-degree greater than 1 (meaning it has two parents).bad
node is found, the redundant edge must be one of the two edges pointing to bad
. To find the correct one (the one appearing last in the input edges
array), iterate through the edges
array in reverse order.(src, dst)
where dst
is the bad
node, hypothetically remove this edge. Then, perform a Depth-First Search (DFS) (check
function in the code) starting from a valid root (a node with in-degree 0 in the modified graph, or a suitable candidate in a cyclic scenario) to see if all N
nodes are reachable and no cycle is formed.bad
remains -1), then the added edge must have created a simple cycle. In this case, every node in the graph (except the root, if it exists) will still have an in-degree of 1.edges
array in reverse. For each edge, hypothetically remove it and then perform a DFS (check
function) to see if the remaining graph is a valid tree.check
function is crucial here: it verifies if all nodes can be reached from a starting root
candidate without encountering any revisited nodes (which would indicate a cycle). If all nodes are visited and no cycles are detected, then the removed edge was indeed the redundant one.The check
function:
n
, the outs
(adjacency list), a starting from
node, and the badfrom
, badto
edge (to be skipped if simulating removal) and a visited
map.visited
node, it means a cycle is present in the current path, so it returns false
.n
nodes without detecting a cycle, it returns true
.The overall algorithm efficiently handles both types of redundancy by prioritizing the “two parents” case and then falling back to cycle detection if necessary, always ensuring the last valid edge is returned.
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
}
For header {header}, explain the problem and the solution, and output this as inline comments in the code inside this header, make sure to use the code inside this header, not some other implementation.
For header {header}, explain the problem and the solution that is in this header with text, not inline code comments, make sure to use the code inside this header, not some other implementation.
Convert this text to markdown.