Saddle Points - Good / Needs Work? Exercism

Hello rustafarians, I hope some of you might help review this code on finding saddle points. I go over the instructions, summarize my solution, and provide code. I include the code I write as src/lib.rs and the tests Exercism provides as tests/saddle-points.rs.

As is it passes all tests, and I am looking for suggestions to improve / refactor the already functional code. Any and all suggestions welcome, thanks for checking this out!

This is from an exercise on exercism.io, and the instructions define a saddle point as one which

  • is >= every element in row
  • is <= every element in column

The Instructions
The goal is to produce the saddle points of a given 2D vector from this function, which has a predetermined parameter and output. Any other functions may also be used, but these parameters may not be changed.

pub fn find_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {}

My Solution
Here is my approach:

  1. Turn the input from a 2D array of Vecs (I think that is what &[Vec<u64>] is) into a 1D Vec.
  2. Use a helper function to find the minimum values per column and the maximum values per row.
  3. Loop through 1D Vec and push to output all values which are == to their row's max and == their column's min.

My Code
src/lib.rs

// Find saddle points in a given 2d vector.
// Changes 2D vector input to 1D vector,
// finds max row values and min col values and puts in new vector,
// compares values in 1D vector to find saddle points.

// Questions for later:
// - Any way to reduce number of times vectors are made?
// - Is this more efficient than making another 2D vector by rotating?
// - Many `for` loops here, should any be replaced by iterators or
//   `while let` statements or something?
pub fn find_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
    let mut saddles: Vec<(usize, usize)> = Vec::new();

    // Early return if input is empty
    if input[0].len() == 0 || input.len() == 0 {
        return saddles;
    }

    let y_len = input.len();
    let x_len = input[0].len();

    let one_d_vec = two_d_to_one_d(input, y_len * x_len);

    let (max_row_vals, min_col_vals) = max_rows_min_cols(one_d_vec, x_len, y_len);

    for y_pos in 0..y_len {
        for x_pos in 0..x_len {
            let current_num = input[y_pos][x_pos];
            if current_num == max_row_vals[y_pos] && current_num == min_col_vals[x_pos] {
                saddles.push((y_pos, x_pos));
            }
        }
    }

    saddles
}

// Changes 2D input vector to 1D output vector
pub fn two_d_to_one_d(input: &[Vec<u64>], capacity: usize) -> Vec<u64> {
    let mut one_d_vec: Vec<u64> = Vec::with_capacity(capacity);

    for row in input {
        for num in row {
            one_d_vec.push(*num);
        }
    }

    one_d_vec
}

// Takes 1D input vector, finds max row values and min col values
fn max_rows_min_cols(one_d_vec: Vec<u64>, x_len: usize, y_len: usize) -> (Vec<u64>, Vec<u64>) {
    let mut min_col_vals: Vec<u64> = Vec::with_capacity(x_len);
    let mut max_row_vals: Vec<u64> = Vec::with_capacity(y_len);

    // Initializing min_col_vals. No need w/ max_row_vals.
    for _ in 0..x_len {
        min_col_vals.push(u64::max_value())
    }

    // Iterate through each value in vec to find mins and maxes.
    let mut max_x = u64::min_value();
    for (i, num) in one_d_vec.iter().enumerate() {
        // Getting min values in each column and insert/removing from vec
        for row in 0..x_len {
            if (i % x_len) == row && *num <= min_col_vals[row] {
                let _ = min_col_vals.remove(row);
                min_col_vals.insert(row, *num);
            }
        }

        // Getting max values in each row and pushing to vec
        for _col in 0..x_len {
            if *num >= max_x {
                max_x = *num;
            }
        }
        if (i + 1) % x_len == 0 {
            max_row_vals.push(max_x);
            max_x = u64::min_value();
        }
    }
    (max_row_vals, min_col_vals)
}

Tests
tests/saddle-points.rs

use saddle_points;

use saddle_points::find_saddle_points;

// We don't care about order
fn find_sorted_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
    let mut result = saddle_points::find_saddle_points(input);
    result.sort();
    result
}

#[test]
fn identify_single_saddle_point() {
    // 9, 8, 7
    // 5, 3, 2
    // 6, 6, 7
    let input = vec![vec![9, 8, 7], vec![5, 3, 2], vec![6, 6, 7]];
    assert_eq!(vec![(1, 0)], find_saddle_points(&input));
}

#[test]
#[ignore]
fn identify_empty_matrix() {
    let input = vec![vec![], vec![], vec![]];
    let expected: Vec<(usize, usize)> = Vec::new();
    assert_eq!(expected, find_saddle_points(&input));
}

#[test]
#[ignore]
fn identify_lack_of_saddle_point() {
    let input = vec![vec![1, 2, 3], vec![3, 1, 2], vec![2, 3, 1]];
    let expected: Vec<(usize, usize)> = Vec::new();
    assert_eq!(expected, find_saddle_points(&input));
}

#[test]
#[ignore]
fn multiple_saddle_points_in_col() {
    let input = vec![vec![4, 5, 4], vec![3, 5, 5], vec![1, 5, 4]];
    assert_eq!(
        vec![(0, 1), (1, 1), (2, 1)],
        find_sorted_saddle_points(&input)
    );
}

#[test]
#[ignore]
fn multiple_saddle_points_in_row() {
    let input = vec![vec![6, 7, 8], vec![5, 5, 5], vec![7, 5, 6]];
    assert_eq!(
        vec![(1, 0), (1, 1), (1, 2)],
        find_sorted_saddle_points(&input)
    );
}

#[test]
#[ignore]
fn identify_bottom_right_saddle_point() {
    let input = vec![vec![8, 7, 9], vec![6, 7, 6], vec![3, 2, 5]];
    assert_eq!(vec![(2, 2)], find_saddle_points(&input));
}

// track specific as of v1.3
#[test]
#[ignore]
fn non_square_matrix_high() {
    let input = vec![vec![1, 5], vec![3, 6], vec![2, 7], vec![3, 8]];
    assert_eq!(vec![(0, 1)], find_saddle_points(&input));
}

#[test]
#[ignore]
fn non_square_matrix_wide() {
    let input = vec![vec![3, 1, 3], vec![3, 2, 4]];
    assert_eq!(vec![(0, 0), (0, 2)], find_sorted_saddle_points(&input));
}

#[test]
#[ignore]
fn single_column_matrix() {
    let input = vec![vec![2], vec![1], vec![4], vec![1]];
    assert_eq!(vec![(1, 0), (3, 0)], find_sorted_saddle_points(&input));
}

#[test]
#[ignore]
fn single_row_matrix() {
    let input = vec![vec![2, 5, 3, 5]];
    assert_eq!(vec![(0, 1), (0, 3)], find_sorted_saddle_points(&input));
}

#[test]
#[ignore]
fn identify_all_saddle_points() {
    let input = vec![vec![5, 5, 5], vec![5, 5, 5], vec![5, 5, 5]];
    assert_eq!(
        vec![
            (0, 0),
            (0, 1),
            (0, 2),
            (1, 0),
            (1, 1),
            (1, 2),
            (2, 0),
            (2, 1),
            (2, 2)
        ],
        find_sorted_saddle_points(&input)
    );
}
  • Converting from 2D to 1D is unnecessary.

Why not just accessing input by 2D indexing?

let value = input[row_index][col_index];
  • max_rows_min_cols unnecessarily consumes argument one_d_vec.

  • max_rows_min_cols algorithm is needlessly complex and inefficient. It can be done in linear time of input size but yours is not.
    This is my biggest -1 point in your solution.

Iterator methods max and min are handy.

let max_in_rows = input.iter().map(|row| row.iter().copied().max().unwrap()).collect::<Vec<_>>();
// write your min_in_cols using iterators!
1 Like

Ah you are totally right, dunno quite what I was thinking.

Code below. This should have linear time for max_rows_min_cols.

I'm not sure if I can use the iterator method you show above for max_in_rows and have linear time for max_rows_min_cols. Wouldn't using the iterator method mean I'd have to loop again through the 2d vector values to get the minimum column values?

// Find saddle points in a given 2d vector.
pub fn find_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
    let mut output: Vec<(usize, usize)> = vec![];
    let col_height = input.len();
    let row_width = input[0].len();
    let (max_row_vals, min_col_vals) = 
        max_rows_min_cols(input, row_width, col_height);
    for row_index in 0..col_height {
        for col_index in 0..row_width {
            let value = input[row_index][col_index];
            if value == max_row_vals[row_index] && value == min_col_vals[col_index] {
                output.push((row_index, col_index));
            }
        }
    }
    output
}

fn max_rows_min_cols(input: &[Vec<u64>], row_width: usize, col_height: usize) -> (Vec<u64>, Vec<u64>) {
    // `insert` and `push` reallocate if len == capacity,
    // so capacity set to one more than needed.
    let mut max_row_vals: Vec<u64> = Vec::with_capacity(row_width + 1);
    let mut min_col_vals: Vec<u64> = Vec::with_capacity(col_height + 1);

    for _ in 0..row_width { min_col_vals.push(u64::max_value()) }
    let mut max_row: u64;

    for row_index in 0..col_height {
        max_row = u64::min_value();
        for col_index in 0..row_width {
            let value = input[row_index][col_index];

            if value < min_col_vals[col_index] {
                min_col_vals.remove(col_index);
                min_col_vals.insert(col_index, value);
            }

            if value > max_row {
                max_row = input[row_index][col_index];
            }
        }
        max_row_vals.push(max_row);
    }
    (max_row_vals, min_col_vals)
}

Code below. This should have linear time for max_rows_min_cols .

Unfortunately, it is not.
Vec::remove and Vec::insert has to move a linear number of elements and the time complexity of your implementation is Θ(h^2 w) worst case.
Just use indexing operation instead: min_col_vals[col_index] = value;.

I'm not sure if I can use the iterator method you show above for max_in_rows and have linear time for max_rows_min_cols . Wouldn't using the iterator method mean I'd have to loop again through the 2d vector values to get the minimum column values?

It is linear time of input size i.e. Θ(h*w) for h×w 2D array (slice of Vecs).
It is easy to see this is the best asymptotic complexity because each input element has to be read.

My code using iterators does the same loop as a 2D loop after compiled but it is clearer and more idiomatic.

Hey thanks for the suggestions about not using remove and insert, totally makes sense to just use indexing operation instead.

Maybe I don't understand what you are saying about using the iteration method. My understanding is that my current code can go through the whole array twice in total.

  1. Finding the max row values and min col values.
  2. Compare the values of the array to the max rows and min cols.

If I were to use the iteration method, it would be more like this:

  1. Use iterator to get max row vals
  2. Use some method to find min col vals
  3. Compare the values of the array to the max rows and min cols.

So the iterator method would have to go through the whole 2D array three times in total, but the for loop method goes through the array twice.

I don't really know much about big-O notation, but wouldn't it be faster to only go through the array twice rather than three times? Maybe if I could use the iter method on both max rows and min cols, and if going through the array twice as iter were faster than going through with the for loop once, then I could see the iter approach as better. Does that make sense?

// Find saddle points in a given 2d vector.
pub fn find_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
    let mut output: Vec<(usize, usize)> = vec![];
    let col_height = input.len();
    let row_width = input[0].len();
    let (max_row_vals, min_col_vals) = 
        max_rows_min_cols(input, row_width, col_height);
    for row_index in 0..col_height {
        for col_index in 0..row_width {
            let value = input[row_index][col_index];
            if value == max_row_vals[row_index] && value == min_col_vals[col_index] {
                output.push((row_index, col_index));
            }
        }
    }
    output
}

fn max_rows_min_cols(input: &[Vec<u64>], row_width: usize, col_height: usize) -> (Vec<u64>, Vec<u64>) {
    // `insert` and `push` reallocate if len == capacity,
    // so capacity set to one more than needed.
    let mut max_row_vals: Vec<u64> = Vec::with_capacity(row_width + 1);
    let mut min_col_vals: Vec<u64> = Vec::with_capacity(col_height + 1);

    for _ in 0..row_width { min_col_vals.push(u64::max_value()) }
    let mut max_row: u64;

    for row_index in 0..col_height {
        max_row = u64::min_value();
        for col_index in 0..row_width {
            let value = input[row_index][col_index];

            if value < min_col_vals[col_index] {
                min_col_vals[col_index] = value;
            }

            if value > max_row {
                max_row = input[row_index][col_index];
            }
        }
        max_row_vals.push(max_row);
    }
    (max_row_vals, min_col_vals)
}

Well, asymptotic complexity doesn't care about constant factors so Θ(c x) and Θ(x) are equal for any constant c. Read Wikipedia for the definition.

In practice, the content (how much computation it does) of the innermost loop is more important than the loop count (not to be confused by loop iteration count). We don't talk about performance here mainly anyway, I'm just pointing out your code was needlessly complex.

Yes and thanks for the advice! It helped to get some feedback and I was able to use it to improve. I think I'll leave it as is, because it seems simpler to go through the vector with a for loop and find the max rows and min cols with two ifs.

Thanks again!

The test should be reversed in case something like &[] is passed to input argument:

    if input.len() == 0 || input[0].len() == 0 {
        return saddles;
    }

(to avoid panic: 'index out of bounds: the len is 0 but the index is 0')

1 Like