How should I practice Count Non-Overlapping Pairs of Rectangles That Sum to K?

Start by reading the full statement, solve the visible examples, then compare the pattern against related WisdomAI phone screen problems in FastPrep.

Is Count Non-Overlapping Pairs of Rectangles That Sum to K associated with WisdomAI?

FastPrep tags this as a WisdomAI phone screen coding practice problem when the problem catalog has that company and stage context.

Count Non-Overlapping Pairs of Rectangles That Sum to K

WisdomAI● HardFULLTIMEPHONE SCREEN

Problem statement

You are given a grid grid of non-negative integers with m rows and n columns, and an integer k. A rectangle is any block of cells from row r1 to row r2 and from column c1 to column c2, where r1 <= r2 and c1 <= c2. Call a rectangle a match if the numbers inside it add up to exactly k.

Two different matches form a pair when they do not overlap, which means they share no cell. Matches that only touch along an edge or at a corner share no cell, so they form a pair.

Return the number of pairs. A pair is unordered, so matches A and B count once, not twice. If no two matches form a pair, return 0.

The answer can be larger than 2^31 - 1, so use a 64-bit integer.

Function

countNonOverlappingPairs(grid: int[][], k: int) → long

Examples

Example 1

grid = [[0,1,1,0],[0,1,1,0]]k = 4return = 0

This is the example from the report. The whole grid adds up to 4, so a match must contain all four 1s, which sit in columns 1 and 2. Four rectangles do this, each covering both rows: columns 1 to 2, 0 to 2, 1 to 3, and 0 to 3. All four contain the same 2 x 2 block of 1s, so every two of them overlap. There is no pair, and the answer is 0.

Example 2

grid = [[1,0,1]]k = 1return = 3

Four rectangles add up to 1: column 0 alone, columns 0 to 1, columns 1 to 2, and column 2 alone. Three pairs share no cell: column 0 with columns 1 to 2, column 0 with column 2, and columns 0 to 1 with column 2. Two of these pairs only touch, which is allowed. Columns 0 to 1 and columns 1 to 2 both use column 1, so they overlap. The answer is 3.

Example 3

grid = [[2,1],[1,2]]k = 3return = 2

Four rectangles add up to 3: the top row, the bottom row, the left column, and the right column. The two rows share no cell, and neither do the two columns. A row and a column always share one corner cell, so those pairs overlap. The answer is 2.

Constraints

1 <= m == grid.length <= 60
1 <= n == grid[i].length <= 60
All rows have the same length.
0 <= grid[i][j] <= 1000
0 <= k <= 3600000

See WisdomAI hiring insights