You are holding a hand of numbered cards. You want to lay all of them down as groups of exactly k cards, where the values in each group are k consecutive integers (for k = 3, a group could be 5, 6, 7, but not 5, 6, 8 or 5, 5, 6).
Write can_split_into_runs(hand: list[int], k: int) -> bool that returns True if the whole hand can be split this way, and False otherwise. The cards arrive in no particular order, and the same value may appear many times.
can_split_into_runs([1, 2, 3, 6, 2, 3, 4, 7, 8], 3) # True (1 2 3) (2 3 4) (6 7 8)
can_split_into_runs([3, 3, 4, 4, 5, 5], 3) # True (3 4 5) twice
can_split_into_runs([1, 2, 3, 4, 5], 4) # False (5 cards can't make groups of 4)
can_split_into_runs([1, 1, 2, 3], 2) # False (both 1s need a 2 as partner)
can_split_into_runs([10, 30, 20], 1) # True (every card is its own group)
Constraints:
1 <= len(hand) <= 2 * 10^50 <= hand[i] <= 10^91 <= k <= len(hand)
Repeatedly searching the hand and removing cards one by one is O(n²), too slow at this size. Aim for O(n log n).
Show hint
look at the smallest card still in your hand. There is only one group it could possibly belong to.