Home

Algorithms notes

Arrays

• Majority element can be found in O(n) using Boyer-Moore algo (called MJRTY).

Graphs

• Shortest cycle can be found in O(n^3) using modification of Floyd-Warshall algo to find all cycles of form ... -> a -> k -> b -> ... where path from a to b is the shortest one consisting of vertices 1 .. k - 1 only. The idea was found in this Quora answer. See my Timus 1004 problem solution for the implementation.