← Snapchat Interview Insights

Snapchat·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Snapchat SWE interview with a grid-based pathfinding problem that's trickier than it looks on the surface. The fire spread mechanic adds a layer that makes naive BFS not quite enough.

Questions Asked (1)

Q1

You're given a 2D grid where cells are either land, wall, or on fire. Fire spreads each minute to adjacent land cells. You start top-left and need to reach bottom-right. What's the maximum number of minutes you can wait at the start before moving and still make it safely? Return -1 if it's impossible, or 10^9 if you can wait indefinitely.

Algorithms & Data Structures
Author's notes

The edge case about passing through the destination at the same minute fire arrives tripped me up for a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a time-expanded graph where each cell has a fire arrival time. Use multi-source BFS from all initial fire cells to compute the earliest time fire reaches each cell, then binary search on the waiting time W to check if a path exists from start to goal where you arrive at each cell before the fire. The check uses BFS on the grid with the constraint that your arrival time at a cell must be strictly less than the fire arrival time.

Pro tip: Clarify edge cases upfront: if the start or goal is initially on fire, return -1; if the goal is unreachable by fire (e.g., surrounded by walls), return 10^9. Also, mention that you can wait at the start only, not en route, which simplifies the problem.

1. Preprocess fire spread times

Run multi-source BFS from all initially burning cells to compute the earliest time each cell catches fire. Use a 2D array fireTime initialized to infinity, and update with BFS level order.

2. Define feasibility check

For a given waiting time W, determine if there exists a path from start to goal such that you arrive at each cell strictly before the fire. Use BFS where you can only move to cells where your arrival time < fireTime[cell].

3. Binary search on waiting time

Binary search W in the range [0, maxPossibleTime]. The maximum possible time is bounded by the maximum fireTime or grid size. If W=0 is infeasible, return -1. If W can be arbitrarily large (goal never catches fire), return 10^9.

4. Handle special cases

Check if start or goal is initially on fire: if so, return -1. If goal is unreachable by fire (fireTime[goal] = infinity), return 10^9. Also, if start equals goal, return 10^9 if not on fire, else -1.

5. Optimize and analyze complexity

The fire BFS is O(R*C). Each feasibility check is O(R*C). Binary search adds a log factor, so overall O(R*C log(R*C)). Mention that you can also use a single BFS with time as a dimension, but binary search is simpler.

Key Points to Mention

  • Multi-source BFS to compute fire arrival times for all cells.
  • Binary search on the waiting time W, with a BFS feasibility check that enforces arrival time < fire time.
  • Strict inequality: you must arrive before the fire, not at the same time.
  • Edge cases: start/goal on fire, goal unreachable by fire, start equals goal.
  • Time complexity: O(R*C log(R*C)) with binary search, or O(R*C) with a single BFS if using a time-expanded approach.
  • You can only wait at the start; once you move, you cannot wait.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.