Last active
August 28, 2022 18:11
-
-
Save K-C-DaCosta/8458b12dde87c97b09d1bf7da4a5a47e to your computer and use it in GitHub Desktop.
Stateless traversal of matrix in ZigZag fashion
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #[test] | |
| fn tests() { | |
| #[rustfmt::skip] | |
| let matrix = vec![ | |
| vec![1 , 2 , 3, 4 , 5], | |
| vec![6 , 7 , 8, 9 , 10], | |
| vec![11 , 12 , 13, 14 , 15], | |
| vec![16 , 17 , 18, 19 , 20], | |
| ]; | |
| let res = zigzag(&matrix); | |
| assert_eq!( | |
| res, | |
| vec![1, 2, 6, 11, 7, 3, 4, 8, 12, 16, 17, 13, 9, 5, 10, 14, 18, 19, 15, 20] | |
| ); | |
| } | |
| pub fn zigzag(matrix: &Vec<Vec<i32>>) -> Vec<i32> { | |
| let mut res = vec![]; | |
| let rows = matrix.len() as isize; | |
| let cols = matrix.get(0).map(|row| row.len()).unwrap_or(0) as isize; | |
| let num_elems = (rows * cols) as usize; | |
| //create virtual matrix size to be square but doubled | |
| let [vcols, _vrows] = [rows.max(cols) * 2; 2]; | |
| for j in 0..vcols { | |
| //mask based on column parity | |
| let mask = j % 2; | |
| // flips vector | |
| let sign = mask * -1 + (1 - mask) * 1; | |
| let direction = [-1 * sign, 1 * sign]; | |
| let mut pos = [0 * mask + (1 - mask) * j, j * mask + (1 - mask) * 0]; | |
| for _ in 0..j + 1 { | |
| if pos[0] < rows && pos[1] < cols { | |
| res.push(matrix[pos[0] as usize][pos[1] as usize]); | |
| } | |
| if res.len() >= num_elems { | |
| return res; | |
| } | |
| pos[0] += direction[0]; | |
| pos[1] += direction[1]; | |
| } | |
| } | |
| res | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment