Function smawk::row_minima

pub fn row_minima<T: PartialOrd + Copy, M: Matrix<T>>(matrix: &M) -> Vec<usize>

Compute row minima in O(m + n) time.

This implements the SMAWK algorithm for efficiently finding row minima in a totally monotone matrix.

The SMAWK algorithm is from Agarwal, Klawe, Moran, Shor, and Wilbur, Geometric applications of a matrix searching algorithm, Algorithmica 2, pp. 195-208 (1987) and the code here is a translation David Eppstein’s Python code.

Running time on an m ✕ n matrix: O(m + n).

Examples

use smawk::Matrix;
let matrix = vec![vec![4, 2, 4, 3],
                  vec![5, 3, 5, 3],
                  vec![5, 3, 3, 1]];
assert_eq!(smawk::row_minima(&matrix),
           vec![1, 1, 3]);

Panics

It is an error to call this on a matrix with zero columns.