Shortest Path in Binary Matrix || Leetcode 1091 || 2 Variant Questions Big Tech Actually Asks

Discover the actual variants Meta asks on Leetcode problem 1091: Shortest Path in Binary Matrix.

Timestamps:
00:00 Leetcode Explanation
14:53 Leetcode Coding
18:20 Variant#1 Explanation (Shortest Path Coordinates)
24:07 Variant#1 Coding (Shortest Path Coordinates)
25:43 Variant#2 Explanation (Single Path Coordinates)
29:23 Variant#2 Coding (Single Path Coordinates)

Follow us on social media:

GitHub:

More Context:
FAANG, mid-sized companies, and startups are asking more LeetCode-style puzzle questions every day, making it harder to stand out as the competition grows. With an increasing number of new graduates entering the software market and tech companies laying off developers while overworking those who remain, it’s a tough landscape. Take Meta, for example: they expect 2-3 months of intense study time, only to likely ghost you afterward. But this doesn’t mean we should be unprepared.

While LeetCode is a valuable learning resource, many developers focus too much on rote memorization. Others find themselves stuck in a vicious cycle, where they don’t study as efficiently as they could because they’re juggling multiple responsibilities. They have full-time jobs, personal commitments, or other obligations that limit the time they can dedicate to solving problems. It’s a grind. Unfortunately, most companies introduce their own twists or "variants" of common problems (e.g., 6-sum instead of 2-sum), which throw candidates off. Rephrasings of problems and follow-up questions are also common, so recognizing these variations and curveballs is crucial.

For those who don’t have the time to revisit LeetCode problems multiple times to solidify concepts, this channel covers the most frequently asked variants, rephrasings, and follow-ups. If you've seen these before, you’ll have a significant edge over your competitors. Remember, time pressure — especially at Meta — is intense, so speed is essential. Even with thorough preparation, interviewers may be unpredictable, but knowing the variants beforehand can drastically increase your chances of success.

Take LeetCode 1091, Shortest Path in Binary Matrix, which is one of Meta’s most frequently asked questions (top 10 as of writing). Meta rarely sticks to the original problem. Variants - however - do exist, and with thousands of interviewers, it's hard to predict them all. We cover 2 key variants: one, what if you had to return the actual coordinates of the shortest path? Two, what if you had to return a single path?

We also walk through variants in mock interviews. Using the exact platform (CoderPad) that Meta uses, you’ll get familiar with the UI, settings, and overall experience. This is a 1-on-1 simulation of how Meta conducts and facilitates their interviews, so the goal is to avoid wasting time on the tool itself. Once again, time limits at Meta are a huge factor, so speed is critical.

That said, even with perfect preparation, interviewers might not always be in a good mood or may judge unfairly. The interview process has its power dynamics, but with insider knowledge, you’ll have done as much as you can on your end to secure a Strong Hire decision.

[jamesperaltaSWE]

ahh classic BFS!! Thanks for the great explantation!

[zhanibakin]

During my phone screen, I got this one, kind of a mix of both variants, I needed to return an array of any path. Also didn’t have to consider diagonals(which doesn’t change code a lot anyway). Did with BFS, cuz I understand it better and was sure I can code it faster. Managed to pass this stage.

[shubhamsrivastava]

For the variant where we want the path - we can reduce the complexity introduced as a result of copyig the path.

This can be done by copying just the direction that we can follow-back after the entire queueing loop is done .

Our queue will now have {row, column, distance, incoming direction}

[asanyal]

Great video. Just a correction - you mean doing variant 2 with DFS would have the same worst case TC as BFS. But the DFS solution doesn't need copying of the path, so it's TC would be O(n^2) as compared to the O(n^3) BFS solution

[moobs]

hey just want to add I think meta expects a parent map - path generation rather than storing a copy of the path for every single node. O(N) space vs O(N^2) space

[def_not_hoang]

Great video! Pretty neat insight for variant 2.

[aloktripathy]

Hi Minmer, great explantion! Just had a question. In the second variant, Won't the time complexity be O(N**4) instead of O(N**3) or am I missing something?

[t_min_o]

its weekend and time to spam all the minmer videos!

for the OG problem

what do you say, if we have the below condition inside the for loop? that is return step+1, as soon as we encounter the end...
if (row == grid.size() - 1 && col == grid[0].size() - 1)
return steps;

I understand there will not be much difference, but having the above condition in the for loop can be a couple of iterations faster, I believe. Minh/Summer, please let me know what you think!

[Ma-gn-cv]

Map solution for var2.

class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] ==1:
return []
directions = [(1, 0), (1, 1), (1, -1), (-1, 0), (-1, 1), (-1, -1), (0, 1), (0, -1)]
queue = deque()
queue.append((0, 0))
grid[0][0] = 1
parent_map = {}
while queue:
row, col = queue.popleft()
if row == n-1 and col == n-1 :
path = []
while (row, col) in parent_map:
path.append([row, col])
row, col = parent_map[(row, col)]
path.append([0, 0])
path.reverse()
return path
for d in directions:
new_row = row + d[0]
new_col = col +d[1]
if 0<= new_row< n and 0<=new_col<n and grid[new_row][new_col]==0:
grid[new_row][new_col] = 1
parent_map[(new_row, new_col)] = (row, col)
queue.append((new_row, new_col))
return []


sol = Solution()
grid = [[0, 1], [1, 0]]
grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]

[ayonmustafi]

For variant 1 of printing path, can't we do it in TC of N^2 and SC of N^2?
Everytime a cell gets pushed in queue, we keep a hash mapping of that cell to its earlier bfs parent/earlier cell. Once we reach the destination, we use this hash mapping to back track to the original starting point giving us the path

[vahidsaber]

Hi Minmer,
First, thank
Next, are these statements correct?
For OG:
SC: The queue holds upto the total number of cells which is N^N not just N. Right?
For variant 1,
If we need to copy traversed paths to the next step, this means it generalizes to copy every cell at each step of traversal, right? Copying each cell is N*N(or N^2) right?
We already had calculated the first N^2 for traversal, so multiplying N^2 * N^2 should be N^4 ?

[qinxue]

For Meta E4 on-site coding round, do we really need to go through your leetcode hard questions? Or just easy and medium?

[rocky]

for the variant where we print path, would it be a memory optimization to create a parent mapping during bfs, then traverse that mapping + reverse the traversed path to get the print order? because that way we are not keeping paths in the queue. would be additional O(path length) time since we need to do the traverse and reverse at the end. want to confirm this tradeoff with yall in case they ask "can we sacrifice run time/memory"

[SD-vkko]

Hey Minmer If we choose to go with HashMap Solution will it work for third variant?

[amruthamishra]

Minh, i could not follow the line 23 and 24 from the second variant, as usual thanks a lot for the videos .

[nisargthakkar]

For path printing variant 1, time complexity is really O(n3), path could be O(n2) and we could do this for all n2 cells, making TC:O(n4)? Even chatgpt is now agreeing with O(n3) TC. Can someone help with TC and SC of this variant?

[codewiz]

For some reason leetcode thinks having local variables - int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[] = {0, 0, 1, -1, 1, -1, -1, 1}; and doing a for loop is a better way to go over directions than the vector<vector>>. 260 ms -> 16 ms