Reach Every Target Position from One Chosen Start Using Repeatable Trades
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of target positions and a list of trades. A position is a point `(x, y)` with integer coordinates, and a trade `(dx, dy)` moves a position from `(x, y)` to `(x + dx, y + dy)`. Pick a starting position, then decide whether every target position can be reached from it using the trades. Return `True` if some starting position reaches all of the targets, and `False` otherwise.
### Function Signature
```python
def can_reach_all(positions: list[list[int]], trades: list[list[int]]) -> bool:
```
### Rules
- The original statement was one sentence plus the first example below; these rules fix its semantics.
- `positions[i] = [x, y]` is a target position, and `trades[j] = [dx, dy]` is a trade.
- Each trade can be executed any number of times, including zero, in any order. A trade is executed only as given: it cannot be run in reverse to subtract `(dx, dy)`.
- A position `P` is reachable from a start `S` if some finite sequence of trades, possibly empty, moves `S` to `P`. Each target is reached separately from `S`; no single path has to pass through all of them.
- You choose the start `S`: any point with integer coordinates. It does not have to be one of the targets, and its coordinates are not bounded by the constraints below.
- Return `True` if there is a start from which every target is reachable, otherwise `False`. Targets may repeat, and a trade `[0, 0]` changes nothing.
### Constraints
- `1 <= len(positions) <= 10^4`
- `0 <= len(trades) <= 10^4`
- `-10^6 <= x, y, dx, dy <= 10^6` for every position and every trade
- All input values fit in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: positions = [[-10, 10], [-20, 20]], trades = [[-1, 1], [-5, 5]]
Output: True
```
Start at `(-10, 10)`. The first target is the start itself (zero trades), and executing `[-1, 1]` ten times reaches `(-20, 20)`.
**Example 2**
```text
Input: positions = [[0, 0], [3, 1]], trades = [[2, 0], [0, 1]]
Output: False
```
Every trade changes the first coordinate by an even amount, so every position reachable from a start has a first coordinate with the same parity as the start's. The targets' first coordinates, `0` and `3`, have different parities, so no start reaches both.
**Example 3**
```text
Input: positions = [[0, 0], [1, 0]], trades = [[3, 0], [5, 0]]
Output: True
```
Start at `(-5, 0)`. One `[5, 0]` trade reaches `(0, 0)`, and two `[3, 0]` trades reach `(1, 0)`.
Overview: Given target positions and trade vectors on a two-dimensional integer grid, decide whether some starting position can reach every target when each trade may be executed any number of times. It tests modeling reachability precisely, reasoning about the offsets that combinations of trades can produce, and handling edge cases such as no trades.
You are given a list of target positions and a list of trades. A position is a point `(x, y)` with integer coordinates, and a trade `(dx, dy)` moves a position from `(x, y)` to `(x + dx, y + dy)`. Choose a starting position, then decide whether every target position can be reached from it using the trades. Return `True` if some starting position reaches all of the targets, and `False` otherwise.
Implement `can_reach_all(positions, trades)`.
### Rules
- `positions[i] = [x, y]` is a target position, and `trades[j] = [dx, dy]` is a trade.
- Each trade can be executed any number of times, including zero, in any order. A trade is executed only as given: it cannot be run in reverse to subtract `(dx, dy)`.
- A position `P` is reachable from a start `S` if some finite sequence of trades, possibly empty, moves `S` to `P`. Each target is reached separately from `S`; no single path has to pass through all of them.
- You choose the start `S`: any point with integer coordinates. It does not have to be one of the targets, and its coordinates are not bounded by the constraints below.
- Return `True` if there is a start from which every target is reachable, otherwise `False` (`true` / `false` in JavaScript, Java and C++). Targets may repeat, and a trade `[0, 0]` changes nothing.
### Example 1
```text
Input: positions = [[0, 0], [3, 1]], trades = [[2, 0], [0, 1]]
Output: False
```
Every trade changes the first coordinate by an even amount, so every position reachable from a start has a first coordinate with the same parity as the start's. The targets' first coordinates, `0` and `3`, have different parities, so no start reaches both.
### Example 2
```text
Input: positions = [[0, 0], [1, 0]], trades = [[3, 0], [5, 0]]
Output: True
```
Start at `(-5, 0)`. One `[5, 0]` trade reaches `(0, 0)`, and two `[3, 0]` trades reach `(1, 0)`.
### Constraints
- `1 <= len(positions) <= 10^4`
- `0 <= len(trades) <= 10^4`
- `positions[i] = [x, y]` and `trades[j] = [dx, dy]` each hold exactly two integers.
- `-10^6 <= x, y, dx, dy <= 10^6` for every position and every trade
- All input values fit in a 32-bit signed integer. The answer is a boolean, but intermediate arithmetic on these values can exceed `2^31 - 1`, so use 64-bit integers (`long` in Java, `long long` in C++) where needed.
Constraints
- 1 <= len(positions) <= 10^4
- 0 <= len(trades) <= 10^4
- positions[i] = [x, y] and trades[j] = [dx, dy] each hold exactly two integers
- -10^6 <= x, y, dx, dy <= 10^6 for every position and every trade
- All input values fit in a 32-bit signed integer; intermediate arithmetic on them can exceed 2^31 - 1
- The start S is any integer point and is not bounded by these constraints
Examples
Input: ([[0, 0]], [])
Expected Output: True
Explanation: Minimum valid input: one target and no trades. Start on the target and use zero trades.
Input: ([[5, -7]], [[1, 2], [-3, 4]])
Expected Output: True
Explanation: A single target with trades is always reachable: start on it and execute nothing.
Hints
- Example 1 argues with a quantity that no trade can change. Ask what every pair of targets must have in common, regardless of where the start is.
- The start is unbounded and need not be a target (Example 2). Consider how much room a start placed far away gives every target.