Could you advice on how to optimize the code style in rus

impl Solution {
    pub fn longest_line(mat: Vec<Vec<i32>>) -> i32 {
        let mut res = 0;
        for (x, row) in mat.iter().enumerate() {
            for (y, y_item) in row.iter().enumerate() {
                if *y_item == 0 {continue;}
                for (x_dir, y_dir) in vec!((0,1), (1,0), (1,1), (1, -1)) {
                    let mut cnt = 0;
                    let mut i = x as i32;
                    let mut j = y as i32;
                    while i >=0 && i < mat.len() as i32 && j >=0 && j < mat[0].len() as i32 && mat[i as usize][j as usize] == 1 {
                        i += x_dir;
                        j += y_dir;
                        cnt += 1;
                    res = std::cmp::max(cnt, res);
        return res;

I thought Rust is preferring functional way for iterator, ex. to avoid ugly cast between i32 and usize indexing. In my case, I have to traversal not only vertical/horizonal but diagonal/anti-diagonal, Any functional way to tune code better looking ?

Addressing your literal question -- instead of managing the stepping of indices yourself, you could calculate the minimum and maximum x and y values of a given line or ray, turn that into a pair of ranges, and then zip them (reversing the iteration if needed). With this approach, you don't need negative step values / non-usizes.

Or perhaps even better, use that data to make iterators over the matrix itself.

As a rough sketch (untested), something like...

// Perhaps make a helper function to create these iterators
let right = mat[0].len() - y;
let down = mat.len() - x;
let down_right = down.min(right); // max cells down and right until border
let down_left = down.min(x + 1); // max cells down and left until border
let dr_ys = y..y+down_right;
let dl_ys = (y-down_left..y).rev(); // No negatives needed

let iter_right = mat[x][y..].iter().copied();
let iter_down = mat[x..].iter().map(|row| row[y]);
let iter_down_right = mat[x..].zip(dr_ys).map(|row, idx| row[idx]);
let iter_down_left = mat[x..].zip(dl_ys).map(|row, idx| row[idx]);

for iter in (iter_right, iter_down, iter_down_right, iter_down_left) {
    let cnt = iter.take_while(|x| x == 1).count();
    // ...

However, let's also consider your algorithm. For every cell in your matrix, you're looking at the rays of contiguous 1s going right, down, down and right, or down and left. You find the longest such ray in the whole matrix. But this means if the longest line looks like so, starting at the upper-left-most 1:

. . . . . .
. 1 . . . .
. . 1 . . .
. . . 1 . .
. . . . 1 .

You're going to traverse portions of that line four times (four different rays), once for every 1 in the line. That's 4+3+2+1 = 10 cell visits. Each line of L 1s results in visiting L(L+1)/2 cells.

So the first thing I would actually do is modify the algorithm to find the longest line in each row, column, and diagonal. This will take your algorithm from something like O(RRC + CCR) to O(RC).

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.