A node may act as leader during a partition only when its reachable side contains a strict majority of the configured voters. Silence from the other side does not reduce the configured quorum size.
Design a PartitionLeaderElector class:
PartitionLeaderElector() creates a stateless elector.int elect(int[] ids, int[] alive, int[][] links, int observer) returns the leader visible from observer, or -1 when that side cannot elect safely.
ids[i] is node i's unique election ID. alive[i] is 1 for an alive voter and 0 for a failed voter. Every [u, v] row in links is a working bidirectional connection.
Starting from observer, find nodes reachable through paths containing only alive nodes. Failed nodes cannot vote or relay traffic. The component has a safe quorum only when its alive-node count is strictly greater than ids.length / 2. The denominator always includes every configured voter.
If the component has a majority, return its greatest node ID. Return -1 when observer is failed or its component lacks a majority.
Example 1:
Input:
Output:
Explanation: Observer 0 can reach three of the five voters through node 1. That is a majority, and ID 30 is greatest on that side.
Example 2:
Input:
Output:
Explanation: Two of four configured voters are reachable. Exactly half is not a strict majority.
Constraints
1 <= ids.length == alive.length <= 10^5- Node IDs are unique and satisfy
0 <= ids[i] <= 10^9. alive[i] is 0 or 1.0 <= observer < ids.length0 <= links.length <= 2 * 10^5- Every link contains two valid, distinct node indices.
- Duplicate links may appear.
- At most
100 calls are made to elect.
Elect a Leader on the Majority Sidemedium