Dining Philosophers: Deadlock-Free Resource Allocation

Problem Context

The classic Dining Philosophers Problem is a well-known concurrency thought experiment that illustrates deadlock and resource contention. In this problem, you are given a simulation of n philosophers sitting at a round table. Each philosopher needs two forks (left and right) to eat. Forks are shared between adjacent philosophers.

Your task is not to simulate threads, but rather to determine — given a sequence of fork-pickup requests — whether a deadlock would occur, and if so, return the minimum number of philosophers that must be restricted (i.e., allowed to pick up at most one fork at a time) to prevent the deadlock.

A deadlock occurs when every philosopher holds exactly one fork and is waiting for the other — forming a circular wait.

Input Format

A function preventDeadlock(n, requests) where:

• n — number of philosophers (and forks), numbered 0 to n-1
• requests — a list of [philosopher_id, fork_id] pairs representing the order in which philosophers attempt to pick up their first fork

Each philosopher i wants fork i (left) and fork (i+1) % n (right).

Output Format

Return an integer: the minimum number of philosophers to restrict to guarantee deadlock prevention. A philosopher is "restricted" if they must release any held fork before picking up a second one (effectively removing them from causing circular wait).

Approach Hints

• Think about what conditions must ALL be true simultaneously for a deadlock: mutual exclusion, hold and wait, no preemption, and circular wait.
• A circular wait among n philosophers holding one fork each only forms when ALL n philosophers have picked up their left fork.
• One classic prevention strategy: limit the number of philosophers allowed at the table to n-1 — this guarantees at least one philosopher can always get both forks.
• The answer is always 1 for any valid input with n >= 2, since removing just one philosopher from the "hold and wait" cycle breaks the circular dependency.
• For n = 1, no deadlock is possible (only one philosopher, no contention).

Examples

Example 1

Input: n = 5, requests = [[0,0],[1,1],[2,2],[3,3],[4,4]]
Output: 1

Example 2

Input: n = 2, requests = [[0,0],[1,1]]