Katkat
Back

Determine Balloon Popping Time

BloombergSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model a grid-based propagation process as a shortest-path problem on a weighted graph, requiring an understanding of Dijkstra's algorithm or Breadth-First Search variants.

Problem Statement

You are given an n x n grid representing a room filled with balloons. You are provided with a list of k starting positions (r, c) and the time t at which each balloon at that position is popped. When a balloon at (r, c) pops at time t, it causes all its adjacent (up, down, left, right) unpopped balloons to pop at time t + 1.

Write a function calculate_pop_times(n, starts) that returns an n x n matrix where each cell (r, c) contains the earliest time that the balloon at that location pops. If a balloon is never popped, store -1 in that cell.

Input

  • n: An integer representing the grid dimensions.
  • starts: A list of tuples (r, c) representing positions where balloons are initially popped at time 0.

Output

  • A 2D list of integers of size n x n.

Examples

Example 1:

  • n = 3, starts = [(0, 0)]
  • Output: [[0, 1, 2], [1, 2, 3], [2, 3, 4]]
  • Explanation: The balloon at (0,0) pops at 0, its neighbors at 1, and so on.

Example 2:

  • n = 2, starts = [(0, 0), (1, 1)]
  • Output: [[0, 1], [1, 0]]

Constraints

  • 1 <= n <= 500
  • 0 <= r, c < n
  • Time complexity should be no worse than O(n^2 log(n^2)).
  • The grid is fully connected (you do not need to handle isolated regions unless they are unreachable).

Hints

Hint 1

Treat the grid as a graph where each cell is a node and edges exist between adjacent cells with a weight of 1.

Hint 2

This is a multi-source shortest path problem, which can be solved efficiently using a modified Breadth-First Search (BFS).

Hint 3

Initialize the BFS queue with all starting positions at time 0 and process them in increasing order of time.

Follow-up questions

  • How would your solution change if popping a balloon at (r, c) took a different amount of time depending on the balloon's color?
  • If the grid contained obstacles that balloons could not pop through, how would you modify your approach?
  • How would you optimize the space complexity if you only needed to return the time a specific coordinate (r, c) pops?