Route a request along diagonal server redirects

Every diagonal move keeps one quantity fixed:

• Northeast (1) and southwest (4) keep x - y fixed. The server lands on the same main diagonal.
• Southeast (2) and northwest (3) keep x + y fixed. The server lands on the same anti-diagonal.

So "the nearest unvisited server in direction d" means: on the current server's diagonal, the closest unvisited server on the correct side, ordered by x. The side is larger x for directions 1 and 2, and smaller x for 3 and 4.

Brute force. For each instruction, scan all servers, keep the ones on the right diagonal and side that are not yet visited, and take the one with the smallest |dx|. That costs O(n) per instruction, so O(n·m) overall. It is fine as a first answer, but too slow when n and m both reach 10^5.

Optimal: sorted diagonals as doubly linked lists.

1. Group server indices by x - y and by x + y. Sort each group by x.
2. Link each group into a doubly linked list. Keep next/prev arrays per family, so each server has four pointers.
3. The current server is always still in both of its lists. Its direct neighbour on the right side of the right list is the nearest unvisited server in that direction, because every visited server has already been unlinked.
4. When the request moves, unlink the server it leaves from both lists in O(1). It is now visited and can never be chosen again.
5. If the neighbour does not exist, skip the instruction. The request stays put and nothing is unlinked.

Invariant: the linked lists hold exactly the unvisited servers plus the current server, in x order along each diagonal. So neighbour lookup equals "nearest unvisited in that direction".

from collections import defaultdict
from typing import Dict, List


def final_server(locations: List[List[int]], redirect_records: List[int]) -> List[int]:
    n = len(locations)
    # Family 0: main diagonals (x - y fixed). Family 1: anti-diagonals (x + y fixed).
    nxt = [[-1] * n, [-1] * n]
    prv = [[-1] * n, [-1] * n]

    for fam, key in ((0, lambda p: p[0] - p[1]), (1, lambda p: p[0] + p[1])):
        groups: Dict[int, List[int]] = defaultdict(list)
        for i, p in enumerate(locations):
            groups[key(p)].append(i)
        for members in groups.values():
            members.sort(key=lambda i: locations[i][0])
            for a, b in zip(members, members[1:]):
                nxt[fam][a] = b
                prv[fam][b] = a

    def unlink(i: int) -> None:
        for fam in (0, 1):
            p, q = prv[fam][i], nxt[fam][i]
            if p != -1:
                nxt[fam][p] = q
            if q != -1:
                prv[fam][q] = p
            prv[fam][i] = nxt[fam][i] = -1

    # direction -> (family, use next pointer?)
    moves = {1: (0, True), 4: (0, False), 2: (1, True), 3: (1, False)}

    cur = 0
    for d in redirect_records:
        fam, forward = moves[d]
        target = nxt[fam][cur] if forward else prv[fam][cur]
        if target == -1:
            continue  # no unvisited server that way: skip
        unlink(cur)  # the server we leave is now visited
        cur = target
    return list(locations[cur])


if __name__ == "__main__":
    pts = [[0, 0], [2, 2], [5, 5], [3, -3], [1, 1], [-2, 2]]
    assert final_server(pts, [1]) == [1, 1]
    assert final_server(pts, [1, 1, 1]) == [5, 5]
    # Back southwest from (5,5): (2,2) and (1,1) are visited, (0,0) too -> skip.
    assert final_server(pts, [1, 1, 1, 4]) == [5, 5]
    assert final_server(pts, [2]) == [3, -3]
    assert final_server(pts, [3]) == [-2, 2]
    assert final_server(pts, [3, 2]) == [3, -3]  # jumps over the visited (0,0)
    assert final_server([[0, 0], [1, 1]], [4, 2, 3]) == [0, 0]
    assert final_server([[7, 7]], [1, 2, 3, 4]) == [7, 7]
    print("ok")

• Preprocessing: O(n log n) to group and sort the diagonals. O(n) space for four pointer arrays and the groups.
• Each redirect: O(1). One pointer lookup, plus an O(1) unlink when the request moves.
• Total: O(n log n + m) time, O(n) space. The brute force is O(n·m).

• locations = [[0,0],[2,2],[5,5],[3,-3],[1,1],[-2,2]], [1] → [1,1]. The nearest northeast is (1,1), not (2,2).
• Same, [1,1,1] → [5,5].
• Same, [1,1,1,4] → [5,5]. Everything southwest is visited, so the last redirect is skipped.
• Same, [2] → [3,-3]. Same, [3] → [-2,2].
• Same, [3,2] → [3,-3]. The visited start (0,0) is jumped over.
• [[0,0],[1,1]], [4,2,3] → [0,0]. Every instruction is skipped.
• A single server with any instructions → that server.
• Empty redirect_records → locations[0].
• Large coordinates (±10^9) and negative values work, because keys are plain integers in a dict.

1. Return the full path or the number of skips. Append to a list or bump a counter inside the loop. The cost is unchanged.
2. Revisiting allowed (only the nearest server counts, visited or not). Drop the unlinking. Each diagonal becomes a static sorted array, and the neighbour is the adjacent index. Store each server's position in its two arrays.
3. Jump to the k-th nearest unvisited server. Linked lists no longer give O(1). Use a Fenwick tree per diagonal over the sorted positions, with 1 = unvisited, and find the k-th one after the current rank in O(log n).
4. Servers added or removed while requests run. Replace each diagonal's list with a sorted container (balanced BST or SortedList) keyed by x. Neighbour queries and updates become O(log n).
5. Eight directions (add horizontal and vertical). Add two more families keyed by y (sorted by x) and by x (sorted by y). Unlink from all four families when leaving a server.

Mid-level (L4)

• Sees that a diagonal move fixes x - y or x + y, and maps all four directions correctly.
• Gets a working solution, even a brute force or sorted lists with a visited set and linear skipping.
• Handles skipped redirects and the visited start server.

Senior (L5)

• Reaches O(n log n + m) with doubly linked lists, and explains why the neighbour is the nearest unvisited server.
• Notices the worst case of "sorted list + skip visited", where long runs of visited servers make it quadratic.
• Tests edge cases on their own: one server, all skips, negative coordinates.

Staff (L6+)

• States the invariant precisely and argues correctness from it.
• Covers the dynamic and k-th variants with the right structures (balanced BST, Fenwick tree) and their trade-offs.
• Discusses the input sizes that force the optimal version, and keeps the code small and reviewable.