Find the Corrupted and Missing Shard IDs

Problem Statement

A distributed storage system splits data into N shards, each assigned a unique ID from 1 to N. Due to a replication bug, one shard's ID got duplicated (overwriting another), so now exactly one ID appears twice and one ID is missing.

You are given the array of N shard IDs. Return [duplicatedId, missingId].

Constraints make it spicy: O(n) time, O(1) extra space — no HashSet, no sorting library.

Constraints

• 1 <= N <= 10^5
• Each value is in the range [1, N]
• Exactly one duplicate and one missing value
• O(1) extra space

Example

Input: shards = [3, 1, 2, 5, 3]

Output: [3, 4]

Explanation: Shard ID 3 appears twice; shard ID 4 is missing.

The Insight — Cyclic Sort

Because every value is in the range 1..N, the value v "belongs" at index v-1. This is the signature of cyclic sort.

Approach:

1. Walk the array. For each position, if the element v is not already at index v-1, swap it there. Repeat until each slot either holds its correct value or a duplicate blocks the swap.
2. After placing everything, scan again: the first index i where arr[i] != i+1 reveals both answers — arr[i] is the duplicate, and i+1 is the missing value.

Placing each number in its "home slot" in-place is the trick that gives O(1) space. Once you see the range is 1..N, cyclic sort should light up in your head.

Follow-ups

1. What if TWO shards are missing and TWO are duplicated?
2. What if IDs are in range 0..N-1 instead of 1..N? How does the home-index change?
3. Could you solve it with XOR + math instead? What are the trade-offs vs cyclic sort?
4. What if the array is read-only (can't swap in place)?