Time Complexity · #36 · 2026-05-10
What's the Big-O?
Rust ·Difficulty 2/3
How to play
Read the code and pick its time complexity from four Big-O choices. Think about loops, recursion, and hidden costs. Press 1–4 or click to answer.
Grid has R rows and C columns. What is the worst-case SPACE complexity?
use std::collections::VecDeque;
fn bfs_grid(grid: &[Vec<bool>], start: (usize, usize)) -> usize {
let (rows, cols) = (grid.len(), grid[0].len());
let mut visited = vec![vec![false; cols]; rows];
let mut queue = VecDeque::new();
queue.push_back(start);
visited[start.0][start.1] = true;
let mut count = 0;
while let Some((r, c)) = queue.pop_front() {
count += 1;
for (dr, dc) in [(!0,0),(1,0),(0,!0),(0,1)] {
let nr = r.wrapping_add(dr);
let nc = c.wrapping_add(dc);
if nr < rows && nc < cols
&& grid[nr][nc] && !visited[nr][nc]
{
visited[nr][nc] = true;
queue.push_back((nr, nc));
}
}
}
count
}
Loading your progress...
Press 1 through 4, or tap a numbered choice, to answer. Back to hub