LeetCode Hard Solutions Explained 🔗

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
}

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
}

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
}

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
}

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

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
}

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
}