Translate this page

LeetCode Hard Solutions Explained 🔗

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:

Table of Contents

60. Permutation Sequence 🔗

Problem and solution.

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
}

10. Regular Expression Matching 🔗

Problem and solution.

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:

  1. If both si and pi have reached the end of their respective strings, it’s a match.
  2. If pi has reached the end of p but si has not reached the end of s, it’s not a match (unless remaining s characters can be matched by a preceding ‘*’).

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
}

124. Binary Tree Maximum Path Sum 🔗

Problem and solution.

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:

  1. 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.
  2. 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
}

37. Sudoku Solver 🔗

Problem and solution.

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells. A Sudoku board (9x9) must satisfy the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The input board contains only digits ‘1’-‘9’ and the character ‘.’.

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
}

1494. Parallel Courses II 🔗

Problem and solution.

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

363. Max Sum of Rectangle No Larger Than K 🔗

Problem and solution.

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.

  1. 2D Prefix Sum Array Initialization:
    • A 2D array 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).
  2. Populating the Prefix Sum Array:
    • The 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.
  3. Iterating Through All Possible Rectangles:
    • The core of the solution involves four nested loops to define all possible rectangles:
      • 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.
    • For each combination of (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).
    • If 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
}

685. Redundant Connection II 🔗

Problem and solution.

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:

  1. A node having two parents: In a directed tree, every node (except the root) has exactly one parent. The added edge might create a situation where a single node receives incoming edges from two different parents.
  2. A cycle: Even if no node has two parents, the added edge might connect a descendant back to an ancestor (or itself), forming a cycle.

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:

  1. Detecting a node with two parents:
    • First, iterate through all the given 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.
    • While building these maps, check if any node (bad) ends up with an in-degree greater than 1 (meaning it has two parents).
    • If such a 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.
    • For each edge (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.
    • The first edge (when iterating in reverse) that, when removed, results in a valid directed tree (single root, no cycles, all nodes reachable) is the answer.
  2. Detecting a cycle when no node has two parents:
    • If, after the initial scan, no node has an in-degree of 2 (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.
    • To find the redundant edge (the one that completes the cycle and appears last), iterate through the 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.
    • The 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:

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
}

Gemini prompts 🔗

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.


Download my free ebook


Subscribe to my mailing list and get a free email course

* indicates required
Interests



Translate this page

Updated on 2025 Jun 27.

DISCLAIMER: This is not professional advice. The ideas and opinions presented here are my own, not necessarily those of my employer.