Design Connect-N winner detector
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
Design a data structure for the Connect-N game: pieces are dropped into a column (occupying the lowest empty cell). Implement move(column, player) that returns true if, after the move, the player has n consecutive pieces horizontally, vertically, or diagonally. Optimize the per-move time complexity and explain the algorithm.
https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/description/
Quick Answer: This question evaluates data structure design and algorithmic optimization for grid-based game state management, including spatial reasoning required to detect n-in-a-row after a move.
You are given an empty rows-by-cols grid for a Connect-N style game and a sequence of moves. Each move is (column, player). A piece drops into the specified column and occupies the lowest empty cell in that column. After each move, determine whether the just-moved player has at least k consecutive pieces in any direction: horizontal, vertical, main diagonal (r - c constant), or anti-diagonal (r + c constant). Return a list of booleans of the same length as moves, where the i-th value is true if move i results in a win for that player, otherwise false.
Constraints
- 1 <= rows, cols <= 2000
- 1 <= k <= max(rows, cols)
- 1 <= len(moves) <= rows * cols
- 0 <= column < cols
- Players are positive integers (more than two players allowed)
- All moves are valid; no column is overfilled
Solution
def connect_n_winner(rows, cols, k, moves):
class LineUnion:
__slots__ = ('start_to_end', 'end_to_start')
def __init__(self):
self.start_to_end = {}
self.end_to_start = {}
def add(self, x):
left_exists = (x - 1) in self.end_to_start
right_exists = (x + 1) in self.start_to_end
if left_exists and right_exists:
left_start = self.end_to_start.pop(x - 1)
# remove corresponding start endpoint for left segment
del self.start_to_end[left_start]
right_end = self.start_to_end.pop(x + 1)
# remove corresponding end endpoint for right segment
del self.end_to_start[right_end]
new_start, new_end = left_start, right_end
elif left_exists:
left_start = self.end_to_start.pop(x - 1)
del self.start_to_end[left_start]
new_start, new_end = left_start, x
elif right_exists:
right_end = self.start_to_end.pop(x + 1)
del self.end_to_start[right_end]
new_start, new_end = x, right_end
else:
new_start, new_end = x, x
self.start_to_end[new_start] = new_end
self.end_to_start[new_end] = new_start
return new_end - new_start + 1
heights = [0] * cols # current filled height for each column
top_player = [0] * cols # player id of the current column top segment
top_count = [0] * cols # length of the current column top segment
horizontals = {} # key: (player, row) -> LineUnion; coordinate: col
diag_main = {} # key: (player, r_minus_c) -> LineUnion; coordinate: col
diag_anti = {} # key: (player, r_plus_c) -> LineUnion; coordinate: col
def get_line(store, key):
ln = store.get(key)
if ln is None:
ln = LineUnion()
store[key] = ln
return ln
res = []
for col, player in moves:
r = heights[col]
heights[col] += 1
# Vertical: only the top segment matters (piece is always placed on top)
if top_player[col] == player:
top_count[col] += 1
else:
top_player[col] = player
top_count[col] = 1
win = (top_count[col] >= k)
# Horizontal
h_len = get_line(horizontals, (player, r)).add(col)
if h_len >= k:
win = True
# Main diagonal (r - c constant)
d1_len = get_line(diag_main, (player, r - col)).add(col)
if d1_len >= k:
win = True
# Anti-diagonal (r + c constant)
d2_len = get_line(diag_anti, (player, r + col)).add(col)
if d2_len >= k:
win = True
res.append(win)
return res
Explanation
Maintain per-column height to place each piece in O(1). Vertical detection is O(1) by tracking, for each column, the top run: the player at the top and its consecutive count; inserting a new piece either extends that run or starts a new run of length 1. For horizontal and diagonal directions, model each line as a 1D number line and maintain merged intervals of occupied indices for each (player, line-id) using two hash maps: start_to_end and end_to_start. When inserting index x, you only need to check whether there is a segment ending at x-1 and/or starting at x+1; merge them with x accordingly, which is O(1) average time. Line identifiers are: row for horizontal, r - c for main diagonals, and r + c for anti-diagonals. Using column as the coordinate along a line makes adjacency checks simple. If any direction reaches length k after a move, that move is a winning move.
Time complexity: O(1) average per move. Space complexity: O(M), where M is the number of moves.
Hints
- Track the height of each column to compute the landing row in O(1).
- Vertical check can be O(1) by maintaining, per column, the current top player's consecutive count.
- For horizontal and both diagonals, treat each line as a 1D set and maintain merged intervals of occupied indices for each (player, line-id).
- Use r - c as the key for main diagonals and r + c for anti-diagonals; use column index as the 1D coordinate.
- On each insertion, merge at most two adjacent intervals and track their lengths to detect k in O(1) average time.