Skip to main content

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