Rearrange house numbers into sorted, duplicate-free neighborhoods: Frontier Interview's solution

Question: Rearrange house numbers into sorted, duplicate-free neighborhoods

Companies: Google

Difficulty: Medium

Problem statement

A city is a list of neighborhoods. Each neighborhood is a list of house numbers (integers), and numbers may repeat, both within a neighborhood and across the city.

Move houses between neighborhoods so that:

Every neighborhood keeps its original size (the number of houses in it does not change).
No neighborhood holds the same house number twice.
Each neighborhood is listed in ascending order.

The city as a whole must keep exactly the same house numbers with the same counts. You only move houses; you never add, remove or renumber them.

Implement:

def rearrange_houses(houses: list[list[int]]) -> list[list[int]]:
    ...

Return any arrangement that meets all three rules, or [] if none exists. Empty neighborhoods are allowed and must stay empty.

Constraints

0 <= len(houses) <= 10^5
Total number of houses N <= 2 * 10^5
House numbers fit in a 32-bit signed integer.

Example 1

Input:  [[4, 4, 7], [2, 4], [7, 2, 9]]
Output: [[2, 4, 7], [4, 7], [2, 4, 9]]   (one valid answer)

Sizes stay 3, 2, 3. The three 4s, two 7s and two 2s each land in different neighborhoods.

Example 2

Input:  [[1, 1, 2], [2]]
Output: []

The first neighborhood needs three different numbers, but the city only has two distinct numbers (1 and 2).

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

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.

Code

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)

Complexity

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.

Test cases

[[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.

Follow-ups

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).
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.
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.
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.
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.

Interviewer expectations

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.