LeetCode

[neetcode.io]

If there is only one connected component, DFS/BFS starting from a node visits all nodes.

• Number of times we have to start DFS is the answer
• Can be done in O(V+E) time and O(V+E) space

Alternatively, can be done by using Disjoint Set Union (DSU).

• Take each vertex as a set
• Then for each edge do union of the vertex sets
• Count the number of times union was done. Say \(k\)
• \(|V| - k\) is the answer

If there are no loops and the number of connected components is 1.

• Can be done in O(V + E) time and O(V+E) space
  • Since E = V - 1 in a valid tree, if we abort in time, we do this in O(V) always.
• Start DFS from say node 0, abort if a cycle is found
• In the end check if all nodes are visited

Given two string s1 and s2 find the longest common substring.

• Can be done in \(O(mn)\) using DP
• Think of the recursive function that gives longest substring starting at index i1, i2
• The general problem for \(k\) strings can be done in \(O(\Pi_{k} l_k)\) using DP.

[neetcode.io]

Given a string s find the longest substring which is a palindrome.

Approach 1:

• Can be done in \(O(n^2)\) time complexity and \(O(1)\) space complexity
• Think of center of the palindrom and expand from there.
  • \(2n - 1\) centers
  • max expansion of \(n\) for any of them

Approach 2: Can also be done in O(n) using Manacher's algorithm.

Approach 3:

• Can also be done in O(n²) time complexity and O(n²) space complexity using DP.
• Think of the bruteforce algorithm, and notice the is_palindrome function
  • It is called \(O(n^2)\) times and take \(O(n)\) time always, so a total \(O(n^3)\) time.
  • But if we write it recursively and then memoize we can do this in \(O(n^2)\) time total.

Variation:

• Find the number of palindromes in a string

Given coins of some denominations \(n\) make change for an amount \(t\) using least amount of coins. You can use coin of each denomination any amount of time.

• Can be done in \(O(nt)\) time and \(O(t)\) space.

[neetcode.io]

Where subsequence is defined as sequence obtained by deleting some or none of the characters but with order maintained.

• Can be done using DP in \(O(m*n)\) time and \(O(m*n)\) space.

• Space can be optimized to \(O(min(m,n))\)

  Look at how the dp table is looked up in the bottom up loop. You can make do with prev row and current row of table. And if you optimize it further, you can do with current row and one entry from previous row.

Given an array of integers nums, find the subarray with the largest sum and return the sum. A subarray is a contiguous non-empty sequence.

• Greedy approach can do this in \(O(n)\) time and \(O(1)\) space.

Also,

• Can be done in \(O(n^3)\) using bruteforce: There are \(O(n^2)\) subsequence, whose sum takes \(O(n)\) each.
• Sum computation can be reused by DP table, thus complexity reduced to \(O(n^2)\) time and \(O(n^2)\) space.

Also,

• A better bruteforce does this in \(O(n^2)\)

Also,

• We can do this recursively. Think of how to use two mutually recursive functions max_subarray_starting_at(i), max_subarray_starting_after(i).
• And its corresponding DP does this in \(O(n)\) time and \(O(n)\) space.