Rearrange house numbers into sorted, duplicate-free neighborhoods

Only two things about the input matter: the capacity of each
neighborhood (its row length) and how many times each house number
appears across the whole city. Sorting a row is free at the end, so the
real problem is: put each copy of a number into a different row, without
overfilling any row.

When is it impossible? A number that appears f times needs f
different rows. If f is larger than the number of rows, there is no
answer. That check is necessary but not sufficient: with capacities
[3, 1] and numbers {1, 1, 2, 2}, every number appears only twice, yet
the 1-slot row can hold only one of them.

Brute force. Backtrack: take the numbers one by one and try each row
that has space and does not already hold that number. It is correct and
exponential. It is still worth naming, and keeping as a test oracle.

Greedy (optimal). Process numbers from most frequent to least frequent.
Put the f copies of the current number into the f rows with the most
remaining space. If fewer than f rows still have space, report failure.

Why it works (exchange argument, the same one behind the Gale–Ryser
theorem for 0/1 matrices):

• Suppose some valid arrangement puts a copy of v in row A while row
  B has more remaining space and does not get v. Since B has more
  space left, B gets some number w later that A does not. Move v
  to B and w to A. Both rows keep their size and stay duplicate-free,
  so the arrangement is still valid. Repeating the swap turns any valid
  arrangement into the greedy one, so the greedy fails only when no answer
  exists.
• Going from most frequent to least frequent matters. The numbers that
  need the most distinct rows are placed while the most rows still have
  space.

A max-heap keyed on remaining capacity gives the f emptiest rows in
O(f log R). Each number is placed at most once in a given row, so no row
gets a duplicate. Sort every row at the end.

Invariants:

• The heap holds exactly the rows with remaining capacity > 0, keyed by
  that capacity.
• Each row receives a given number at most once, because the f rows for
  one number are popped together before any is pushed back.
• The total number placed equals the total number of houses, so every row
  ends exactly full.

import heapq
from collections import Counter


def rearrange_houses(houses: list[list[int]]) -> list[list[int]]:
    """Return neighborhoods with the same sizes, each strictly increasing,
    holding exactly the same multiset of house numbers. [] if impossible."""
    caps = [len(row) for row in houses]
    counts = Counter(x for row in houses for x in row)
    if not counts:
        return [[] for _ in houses]

    # Max-heap of (remaining capacity, row index) for rows with space left.
    heap = [(-c, i) for i, c in enumerate(caps) if c > 0]
    heapq.heapify(heap)
    result: list[list[int]] = [[] for _ in houses]

    # Most constrained numbers first: they need the most distinct rows.
    for value, freq in sorted(counts.items(), key=lambda kv: (-kv[1], kv[0])):
        if freq > len(heap):
            return []  # not enough distinct rows with space left
        taken = [heapq.heappop(heap) for _ in range(freq)]
        for neg_cap, i in taken:
            result[i].append(value)
            if neg_cap + 1 < 0:  # row still has space
                heapq.heappush(heap, (neg_cap + 1, i))

    for row in result:
        row.sort()
    return result


def is_valid(original: list[list[int]], arranged: list[list[int]]) -> bool:
    if [len(r) for r in original] != [len(r) for r in arranged]:
        return False
    if Counter(x for r in original for x in r) != Counter(x for r in arranged for x in r):
        return False
    return all(all(a < b for a, b in zip(r, r[1:])) for r in arranged)


if __name__ == "__main__":
    city = [[4, 4, 7], [2, 4], [7, 2, 9]]
    arranged = rearrange_houses(city)
    assert is_valid(city, arranged)
    assert rearrange_houses([[5, 5], [5]]) == []      # 5 needs three rows
    assert rearrange_houses([[1, 1, 1], [2, 2]]) == []
    assert rearrange_houses([[3, 1, 2]]) == [[1, 2, 3]]
    assert rearrange_houses([[], []]) == [[], []]
    print(arranged)

Let N be the total number of houses, R the number of neighborhoods and
U the number of distinct house numbers.

• Counting: O(N) time, O(U) space.
• Ordering numbers by frequency: O(U log U).
• Placement: each house causes one heap pop and at most one push, so
  O(N log R).
• Final sort of the rows: O(N log N) overall in the worst case.
• Total: O(N log N) time, O(N + R) space for the output and heap.

• [[4, 4, 7], [2, 4], [7, 2, 9]]: valid output, for example
  [[2, 4, 7], [4, 7], [2, 4, 9]]. Sizes stay 3, 2, 3, and every row is
  strictly increasing.
• [[3, 1, 2]]: [[1, 2, 3]] (one row, already distinct).
• [[5, 5], [5]]: [] (5 appears three times, but there are only two
  rows).
• [[1, 1, 1], [2, 2]]: [] (1 needs three rows).
• [[1, 1], [1, 2], [], [3]]: valid, for example [[1, 2], [1, 3], [], [1]].
  An empty neighborhood stays empty.
• Capacities [3, 1] with numbers {1, 1, 2, 2}, for example
  [[1, 1, 2], [2]]: []. Every number appears only twice, but the
  1-slot row cannot take both 1 and 2.
• [[], []]: [[], []]. [] (no neighborhoods): [].
• Randomized check: compare against the backtracking oracle on small
  inputs (rows ≤ 4, values ≤ 4). Feasibility must agree, and every
  non-empty answer must pass is_valid.

1. Report why it fails. Return the first number that could not be
   placed and how many rows it needed against how many had space. The
   greedy already knows this when freq > len(heap).
2. Minimize the number of houses that move. A house "stays" if its
   number remains in its original row. Model it as min-cost flow:
   number → row edges with capacity 1, cost 0 if that number was already in
   the row and 1 otherwise, row → sink edges with the row's capacity.
   The min-cost max flow gives the arrangement with the fewest moves.
   The greedy cannot do this, because it ignores where houses started.
3. Neighborhoods may grow or shrink by at most k. Row → sink
   capacities become ranges. Use flow with lower bounds, or, if only an
   upper bound changes, keep the greedy with the larger capacities and
   check that the totals still match.
4. A number may appear at most d times per neighborhood. Each number
   now needs at least ceil(f / d) rows. Use flow with number → row
   capacity d. The greedy generalizes if you pop rows and place up to
   min(d, remaining space) copies in each, but the exchange argument has
   to be redone, so flow is the safer answer.
5. Streaming houses. Houses arrive one at a time and must be placed
   immediately. Online placement can get stuck where the offline greedy
   would not. Discuss keeping the heap and a per-row set, and where you
   would need to allow re-shuffles.

Mid-level (L4)

• Restates the problem as "each copy of a number goes to a different row,
  and row sizes are fixed", and sees that the final sort is free.
• Finds the freq > rows impossibility check and gives a working
  solution, even if it is backtracking or a greedy without a proof.
• Writes clean code and tests duplicates, empty rows and the impossible
  case.

Senior (L5)

• Shows that freq ≤ rows is not enough, with a small counterexample.
• Uses the "most frequent number into the emptiest rows" greedy with a
  heap and states O(N log N).
• Gives an exchange-argument sketch for why the greedy is correct, and
  adds a validator or brute-force oracle to test it.

Staff (L6+)

• Recognizes the problem as bipartite b-matching / max flow, or as the
  Gale–Ryser condition, and explains why the special structure allows a
  greedy.
• Moves to min-cost flow for "fewest moves" and explains why the greedy
  breaks under that objective.
• Talks about the shape of the output: how impossibility is reported, and
  whether the API returns one valid arrangement or a canonical one.