Kosaraju’s vs Tarjan’s Kosaraju’s algorithm finds the Topological Sorting of the original directed graph. For this, it uses DFS. Next it reverses the graph and runs DFS on the topologically sorted vertices. So it takes two DFS though the time complexity is O(|V|+|E|). Tarjan’s algorithm, on the other hand, only uses one DFS but uses […]

# Month: October 2021

This is a array/string problem and you can look up this problem on HackerRank. To solve this one, it can not theoretically be any better than O(n) time complexity. Here I convert the string to character array, then for each character and if this is a small ASCII character between a-z, then subtract the value […]