1706. Where Will the Ball Fall

[jason89521]

Practice Dates

• 2024/05/15

Description

Link: https://leetcode.com/problems/where-will-the-ball-fall/description/

Solution

For each ball, we check whether it encounters a V diagonal or a wall. If it does, we set the corresponding index in the result to -1 and don't check this ball in the next iteration. We repeat this process until we reach the end of the rows.

impl Solution {
    pub fn find_ball(grid: Vec<Vec<i32>>) -> Vec<i32> {
        let rows = grid.len();
        let cols = grid[0].len();
        let mut result = Vec::with_capacity(cols);
        for i in 0..cols {
            result.push(i as i32);
        }

        for row in 0..rows {
            for col in 0..cols {
                let current_col = result[col];
                if current_col == -1 {
                    continue;
                }

                let current_col = current_col as usize;
                let dir = grid[row][current_col];
                if dir == 1 {
                    if current_col == cols - 1 || grid[row][current_col+1] == -1 {
                        result[col] = -1;
                    } else {
                        result[col] += 1;
                    }
                } else {
                    if current_col == 0 || grid[row][current_col-1] == 1 {
                        result[col] = -1;
                    } else {
                        result[col] -= 1;
                    }
                }

            }
        }

        result
    }
}

Performance

Time complexity: