Index page fetches
A reporting engine answers each query through an unclustered secondary index. The index hands back one pointer per matching row, in index key order, and a pointer names the heap page that row lives on. The engine holds exactly one heap page at a time, so walking the pointers in index order fetches a page whenever the next pointer names a page other than the one it is already holding, and a page left behind can be fetched again later. A bitmap scan instead gathers all the pointers first, sorts them, and fetches each distinct page exactly once. Each entry of queries is one query's pointer list, in index order. Return a list holding, for each query in input order, how many page fetches the bitmap scan saves. A query that matched nothing saves 0. Return an empty list when no queries are given.
bitmap_scan_savings(queries: list[list[int]]) → list[int][[[4,4,7,7,4],[9],[2,5,2,5]]]out[1,0,2][[[11,11,11,12,12,13]]]out[0][[[3,8,3,8,3,8,3]]]out[5]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.
[[[4,4,7,7,4],[9],[2,5,2,5]]][1,0,2]not run yetsample[[[11,11,11,12,12,13]]][0]not run yetsample[[[3,8,3,8,3,8,3]]][5]not run yetsample