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/
Overview: 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
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.
Community answers
Answer by ubinexy
from typing import List
class Board:
def init(self, rows, cols):
self.cols = cols
self.rows = rows
self.board = list(map(lambda x: [0] * self.rows, range(self.cols)))
def drop(self, player, col):
row = len(list(filter(lambda x: x != 0, self.board[col])))
self.board[col][row] = player
def row_line(self, row, col) -> List[int]:
o
0 1 2 3 4 5 6
line = []
for i in range(0, self.cols):
print(f"self.board[{i}][{row}] = {self.board[i][row]}")
line.append(self.board[i][row])
return line
def rows_(self, row, col, k) -> List[List[int]]:
if col < k-1:
c_start = 0
c_end = col+1
else:
c_start = col-(k-1)
c_end = self.cols-(k-1)
line = self.row_line(row, col)
result = []
print(f"c_start:{c_start}, c_end:{c_end}")
if c_start <= c_end:
for i in range(c_start, c_end):
result.append(line[i:i+k])
return result
def cols_(self, row, col, k) -> List[List[int]]:
result = []
if 0 <= row-(k-1):
result.append(self.board[col][row-(k-1):row+1])
return result
def diag_line(self, row, col):
o (2, 0)
0 1 2 3 4 5 6
line = [0] * self.cols
for c in range(0, self.cols):
if 0 <= c - col + row < self.rows:
line[c] = self.board[c][c - col + row]
return line
def diags(self, row, col, k) -> List[List[int]]:
if row < col:
c_start = max(0, col - (k-1))
c_end = min(col+1, self.cols-(k-1))
else:
c_start = max(0, row - col - k)
c_end = min(col+1, self.cols-(k-1))
line = self.diag_line(row, col)
result = []
print(f"c_start:{c_start}, c_end:{c_end}")
print(f"diag_line:{line}")
if c_start <= c_end:
for i in range(c_start,
Answer by leni
class ConnectN:
_DIRECTIONS = [(1,0), (0,1), (1,1), (1, -1)]
def init(self, rows, cols, k):
self.rows = rows
self.cols = cols
self.k = k
self.openCells = self.rows * self.cols
self.board = [[0] * self.cols for _ in range(self.rows)]
self.nextCell = [0] * self.cols
def checkDirection(self, row, col, direc, player):
total = 0
while row >= 0 and row < self.rows and col >= 0 and col < self.cols and self.board[row][col] == player:
total += 1
row += direc[0]
col += direc[1]
return total
def checkWinner(self, row, col, player) -> bool:
for d in self._DIRECTIONS:
dr, dc = d
total = 1 + self.checkDirection(row + dr, col + dc, (dr, dc), player) + self.checkDirection(row - dr, col - dc, (-dr, -dc), player)
if total >= self.k:
return True
return False
def move(self, col, player) -> bool:
if self.openCells <= 0:
return False
row = self.nextCell[col]
self.board[row][col] = player
self.nextCell[col] += 1
self.openCells -= 1
return self.checkWinner(row, col, player)
def connect_n_winner(rows, cols, k, moves):
game = ConnectN(rows, cols, k)
res = []
for move in moves:
col, player = move
res.append(game.move(col, player))
return res