Enumerate Disjoint Pairs of Target-Sum Subrectangles

Given a two-dimensional array of nonnegative values and an integer `k`, find every unordered pair of nonempty axis-aligned subrectangles such that each rectangle's entries sum to `k` and the two rectangles do not overlap. For this practice formulation, use nonnegative integer entries, contiguous row and column ranges, and define overlap as sharing at least one array cell. The report does not provide matrix-dimension or element upper bounds. A solution should avoid comparing every possible rectangle against every other rectangle and should account for the size of the required output. ### Input and Output Use zero-based inclusive coordinates to describe a rectangle as `(top, left, bottom, right)`. Return all distinct unordered pairs of qualifying rectangles. Coordinate representation and output ordering are interface conventions for practice: put the lexicographically smaller rectangle first within each pair and sort the final list of pairs lexicographically. Do not return only the number of pairs. If no pair exists, return an empty list. ### Constraints & Assumptions - The input is a nonempty rectangular matrix of nonnegative integers; no numerical dimension limit was reported. - `k` is an integer. A negative target cannot be reached with nonnegative entries. - Rectangles contain at least one cell. - Rectangles next to each other may form a pair if they share no cell. - Different coordinates describe different rectangles, even if their values are identical. - Zero-valued cells may produce several different rectangles with the same sum. ### Reported Example ```text matrix = [ [0, 1, 1, 0], [0, 1, 1, 0] ] k = 4 Output: [] ``` The rectangle containing the middle two columns has sum `4`. Extending it into the right zero column produces another target-sum rectangle, but they overlap. Every target-sum rectangle in this matrix contains the four `1` cells, so no disjoint pair exists. ### Clarifying Questions to Ask - Must all pairs be returned, or only their count? All pairs are required. - What constitutes overlap? In this formulation, sharing an array cell. - Are dimensions or output size bounded? They were not supplied, so state complexity in terms of both the matrix and the number of results. ```hint Two cell-disjoint axis-aligned rectangles must be separated by their row ranges or by their column ranges. A pair can satisfy both conditions, so combining two sweeps needs a duplicate rule. ``` ### What a Strong Answer Covers The solution should find all target-sum rectangles without losing alternatives created by zeros, report disjoint pairs without a blind quadratic comparison over candidates, and emit each unordered pair exactly once. It should separate search work from unavoidable output work and explain the cost of the chosen canonical ordering. ### Follow-up Questions - How would the approach change if only the number of pairs were requested? - Why can a single sliding-window endpoint miss target-sum rectangles when zeros are present? - How would you stream results if storing the complete output were impractical?