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]]) ;
 }
}

Still need some work on memory 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
}

• Sugar: wrapping add not really the thing he wanted to do i think. it wraps size of integer (255+1 => 0 for u8 , for example) , but he adds point offsets, and it will not work, coz he checks image bounds, not an integer bounds.
• Sugar: also bfs and dfs not really different in this case, because he need to fill color field, not find path in it.
• Simson: dfs bfs is only if poping from the front or the back of the queue
• Simson: Thanks for feedback, auto format and while let Some(x) = cells.pop_front() are habits I will do more of. I try_from() instead of as i32 is also good however I think it is clearer to use a signed type for subtraction than using the wraparound trick - it is too similar to the abnormality we use in C all the time unsigned int = -1
• L. F.: @Simson You're welcome. The wraparound hack is indeed sub-optimal, so I tried to present it as an option only (as opposed to a recommendation). I don't like signedness conversion either, so I took this approach instead, but that's purely subjective.