LSM-tree compaction
Implement LSM-tree compaction. You are given 'runs', a list of sorted runs ordered oldest-first to newest-last; each run is a list of [key, seq, value] entries sorted ascending by key, where value is a string or the literal string '__TOMBSTONE__' for a delete. Higher seq means newer. Merge all runs into one sorted output keeping, for each key, only the entry with the largest seq; if that winning entry is a tombstone, the key is dropped entirely (deleted). Return the compacted run as a list of [key, seq, value] sorted ascending by key, excluding deleted keys.
lsm_compact(runs: list[list[list]]) → list[list][[[["a",1,"x"],["b",2,"y"]],[["a",5,"x2"],["c",3,"z"]]]]out[["a",5,"x2"],["b",2,"y"],["c",3,"z"]]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[[["a",1,"x"],["b",2,"y"]],[["a",5,"x2"],["c",3,"z"]]]][["a",5,"x2"],["b",2,"y"],["c",3,"z"]]not run yetsample