LeetCode: FloodFill Rust

Question

Hi I'm implementing a few leetcode examples in Rust. https://leetcode.com/problems/flood-fill/

(looks to be same question as LeetCode: FloodFill C#)

The input is one matrix, a position and its new colour. The output is the modified matrix

// Input: 
// image = [[1,1,1],[1,1,0],[1,0,1]]
// sr = 1, sc = 1, newColor = 2
// Output: [[2,2,2],[2,2,0],[2,0,1]]
// Explanation: 
// From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
// by a path of the same color as the starting pixel are colored with the new color.
// Note the bottom corner is not colored 2, because it is not 4-directionally connected
// to the starting pixel.

I use q.pop_front() to fill the neighbouring cells first. Is VecDeque the best data structure for this que?

I do a lot of casting from between i32 and usize as I want to be able to check if index is out of bounds by subtracting 1. Is there a better way?

Is if (0..image.len()).contains(x1) better than if x1>=0 && x1<image.len() for the range check?

use std::collections::VecDeque;

  fn flood_fill(mut image: Vec<Vec<i32>>, sr: i32, sc: i32, new_color: i32) -> Vec<Vec<i32>> {

      let mut q:VecDeque<(i32,i32)> = VecDeque::new();
      q.push_back((sr,sc));

      let c0 = image[sr as usize][sc as usize];
      if c0 != new_color {
          while ! q.is_empty() {
              if let Some((sr,sc))=q.pop_front() {  
                  if image[sr as usize][sc as usize] == c0 {
                      image[sr as usize][sc as usize] = new_color;
                      for delta in vec![(-1,0),(1,0),(0,-1),(0,1)] {
                          let new_r:i32 = sr+delta.0;
                          let new_c:i32 = sc+delta.1;
                          if (0..image.len() as i32).contains( &new_r ) && (0..image[0].len() as i32).contains( &new_c){
                              q.push_back((new_r,new_c));
                          }
                      }
                  }
              }
          }
      }
      image
  }

#[cfg(test)]
mod test{
#[test]
    fn test_lc_default(){
        assert_eq!(super::flood_fill(vec![vec![1 as i32 ,1,1],vec![1,1 as i32,0],vec![1,0,1]],1, 1, 2),vec![vec![2,2,2],vec![2,2,0],vec![2,0,1]]) ;
    }
}

It looks like I could use some memory optimization too.

Answer 1

Formatting

I assume the indentation to be a copy-paste error when removing the boilerplate struct Solution mandated by LeetCode.

Run cargo fmt on your code to conform to the standard Rust formatting guidelines.

Interface

LeetCode made a poor choice by using Vec<Vec<i32>> to represent a two-dimensional array, which is generally inefficient as it stores elements in multiple segmented allocations, incur double indirection costs, and fail to maintain proper structure (against jagged arrays). We can't do anything against this, though, so I'll ignore it for the rest of the post.

Similarly, i32 is not ideal for color representation — a dedicated type (e.g., struct Color(i32);) is clearly superior. At the very least, we can somehow improve readability by using a type alias and use it consistently for colors in the code:

type Color = i32;

i32 vs. usize

Generally, it is preferred to store and compute indexes in usize, which is the natural type for this purpose. One way you can avoid subtracting 1 is by using usize::MAX and wrapping_add.

To convert from the i32 values that the function receives, try_from is preferred over as, since the latter silently truncates invalid values. unwrap can be used here since it's for LeetCode; in real-world code, the error should be handled accordingly.

Is if (0..image.len()).contains(x1) better than if x1>=0 && x1<image.len() for the range check?

I'd say yes. It indicates the intent more clearly.

Simplifying control flow

Instead of wrapping everything in an if expression, check for image[sr][sc] == new_color and return early.

while let

This:

while !cells.is_empty() {
    if let Some((sr, sc)) = cells.pop_front() {

is just a convoluted way of saying

while let Some((sr, sc)) = cells.pop_front() {

---

Here's how I modified your implementation:

type Color = i32;

pub fn flood_fill(
    mut image: Vec<Vec<Color>>,
    sr: i32,
    sc: i32,
    new_color: Color,
) -> Vec<Vec<Color>> {
    use std::collections::VecDeque;
    use std::convert::TryFrom;

    let sr = usize::try_from(sr).unwrap();
    let sc = usize::try_from(sc).unwrap();

    let initial_color = image[sr][sc];

    if initial_color == new_color {
        return image;
    }

    let height = image.len();
    let width = image[0].len();

    let mut cells: VecDeque<(usize, usize)> = VecDeque::new();
    cells.push_back((sr, sc));

    while let Some((sr, sc)) = cells.pop_front() {
        let cell = &mut image[sr][sc];

        if *cell != initial_color {
            continue;
        }

        *cell = new_color;

        const OFFSETS: &[(usize, usize)] = &[(0, usize::MAX), (usize::MAX, 0), (0, 1), (1, 0)];

        for (delta_r, delta_c) in OFFSETS.iter().copied() {
            let new_r = sr.wrapping_add(delta_r);
            let new_c = sc.wrapping_add(delta_c);

            if new_r < height && new_c < width {
                cells.push_back((new_r, new_c));
            }
        }
    }

    image
}