Geometry

Maximum Manhattan distance

Find the largest Manhattan distance between any two points in a set.

Runtime: Linear Memory: Constant

Point inside triangle

Determine if a point lies inside a given triangle.

Runtime: Constant Memory: Constant

Strings

Knuth-Morris-Pratt (KMP)

Linear time string matching.

Runtime: Linear Memory: Linear

Manacher's algorithm

Find the longest palindromic substring of a string.

Runtime: Linear Memory: Linear

Rabin-Karp algorithm

String matching with a rolling hash. Worst case quadratic time.

Runtime: Linear Memory: Constant