888. The Weakest k Rows

A grid has r rows and c columns. Each cell is 1 for a soldier or 0 for a civilian, and in every row the soldiers come FIRST, so a row looks like some ones followed by some zeros.

Row i is weaker than row j when it has fewer soldiers, or when they have the same number of soldiers and i < j. Print the indices of the k weakest rows, weakest first, using 0-based indices.

1 1 0 0 0 1 1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 k = 3 -> 2 0 3

The soldier counts are 2, 4, 1, 2, 5. The smallest is row 2 with one soldier. Then rows 0 and 3 are tied at two, and row 0 comes first because its index is smaller.

## What most people try first

Counting the ones in every row by scanning it, then sorting all r rows. That is O(rc) to count and O(r log r) to sort, and at r = c = 1000 it is a million cell reads. It works. It also ignores two things the statement has handed over.

## The first gift: the rows are sorted

Because the ones come first, the number of soldiers is the position of the first zero, and that can be found by binary search in O(log c) instead of O(c).

lo = 0, hi = c while lo < hi: mid = (lo + hi) / 2 if row[mid] == 1: lo = mid + 1 else: hi = mid count = lo

That turns a million reads into about ten thousand. The invariant is the standard lower-bound one: everything below lo is a one and everything at or above hi is a zero, so when they meet, lo is the first zero, and an all-ones row lands on lo = c without ever reading out of bounds.

## The second gift: only k rows are wanted

Sorting orders all r rows to report k. A bounded heap of size k keeps only the survivors, as in problem 880, and the same direction argument applies: the WEAKEST are wanted, so the survivor to evict is the STRONGEST of them, so the heap is a MAX-heap.

## The key is a pair, and the second half is the index

The order is by (soldiers, index). Both halves have to be in the heap key, in that order, for two separate reasons:

· the tie rule needs the index, or rows with equal counts come out in an order that depends on the library · the ANSWER is the index, so it has to be carried anyway

This is the derived-key pattern again, with the twist that the thing being reported is the second component of the key rather than something extra hanging off it.

h = empty max-heap ordered by (soldiers, index) for each row i: key = (count(i), i) if size(h) < k: push key else if key < top(h): pop, push key sort the survivors increasing by (soldiers, index) and print the indices

## The boundary that breaks a careless implementation

A row of all zeros. Its count is 0, and a binary search that assumes at least one soldier reads row[0], sees a zero, and must return 0 rather than looping. The all-zero grid test is there for this.

A row of all ones. The first zero does not exist and the count is c. A search written to return an INDEX rather than a COUNT has to special-case it; the lower-bound form above does not.

Forgetting to sort the survivors. A heap is not a sorted list. Popping a max-heap gives the strongest survivor first, which is the answer backwards.

## What is NOT an overflow here

Counts are at most c, which is 1000, and indices are at most r, which is 1000. Nothing here comes close to a 32-bit limit and nothing is summed.

## Related problems

Problem 880 is the same bounded heap with the value as its own key. Problem 881 is the same bounded heap with a computed key. This one is both at once, and it is the binary search inside the key computation that makes it worth doing separately.

## Cost

Time O(r (log c + log k)). Space O(k).

Constraints - `1 ≤ k ≤ r ≤ 1000` - `1 ≤ c ≤ 1000` - Every cell is `0` or `1`, and in each row every `1` comes before every `0`.