1

Let's say I have a 2d array 100x100 in size, each cell in that array has a number from 1 to 50 randomly.

How do I find the biggest subarray in a rectangle size in that array that has only n different numbers?

Small example:

array: 1 2 3 3 3 2 2
       7 4 3 3 4 9 8
       1 2 3 3 3 4 2
       7 6 1 9 9 4 2
In this case the biggest sub rectangle with only 1 number allowed would be 
       3 3
       3 3
With 2 numbers allowed it would be
       3 3 3
       3 3 4
       3 3 3

Does something for this exist?

2
  • 2
    There is nothing fancy here. You simply need to cycle through each nxn subarray and score each one. Grab the one with the lowest amount of differences and you're done.
    – Neil
    Mar 2 '15 at 13:14
  • Each a x b subarray. There are 4,950 x 4,950 of those. And you'd have to check whether there are only n different numbers for each of those, which is a bit of work.
    – gnasher729
    Apr 4 '15 at 17:07
2

If the array has a size of n x m, then there are roughly n^2 m^2 / 4 subarrays. If there are k different values, then we can represent each as a bit array with k bits. This takes for example k' := ceil (k / 64) 64 bit words.

It's quite easy to calculate each of the sets of values for n^2 m^2 / 4 subarray in a total of n^2 m^2 k' / 4 steps. The number of bits can be counted in log2 (k) steps, so we have a total of n^2 m^2 k' log2 (k) / 4 operations. In this case, 10,000 * 10,000 * 1 * 6 / 4 = 150 million steps. So no big deal. It gets more interesting if the values are larger.

However, this brute force search would be quite inefficient in this case (where each cell contains a random number). We can reasonably easy calculate the probabibility that a rectangle of n numbers contains k or fewer different numbers, and that probability will go down rapidly if n gets larger than k. So we would want to avoid checking really large rectangles. Here's how I would suggest to proceed, for an array of n rows and m columns, looking for the largest rectangle with at most k different numbers:

We handle trivial cases: k ≤ 0 means no solution, k ≥ number of different numbers means (1:n, 1:m) is the solution. Then find the largest trivial solution, which is just the largest rectangle with an area ≤ k. (For example, if the array is 5x5 and k = 7, we can trivially find a rectangle of size 6 but not of size 7). Let the size of the rectangle be s ≤ k. Let maxc (r) = "largest c where we haven't proved that a rectangle with r rows and c columns and less than k different numbers cannot exist".

Given a record s, we then need to find a rectangle which is larger or prove that it doesn't exist. We find a pair (r, c) with the smallest product rc such that c ≤ maxc (r) and rc > s. If such a pair doesn't exist then we have the optimal solution. Otherwise, we look for a rectangle of size r x c with k or fewer different numbers. If none is found, then we set maxc (i) = min (maxc (i), c - 1) for all i ≥ r (there cannot be a rectangle with r rows or more, and with c-1 columns or more) and try again. If a rectangle is found, then we record it, increase s, and also try again.

0

You could try something like:

  1. Grab the whole 2d array
  2. Remove first column / first row / last column / last row
  3. Stack each of the four resulting subarrays.
  4. Store the biggest one that meets the condition, if it's bigger than the biggest one that currently does (if any).
  5. Repeat procedure for each subarray in the stack

By doing this you would have checked every possible subarray you can take form the starting array, and made sure you got the biggest possible. If you want it a bit faster you can return early when no more arrays bigger than the current biggest one are left

0

I can think of one auxiliary technique that may be sometimes useful for a related question.

Note that this auxiliary technique doesn't solve the main question. One shouldn't use this technique if the goal is to solve a given puzzle where the solution is guaranteed to exist.

This auxiliary technique is used to prove the contrary: that given an M-by-N array, for any possible A-by-B subarrays, no fewer than C different labels will be found. This technique solves C when given A and B.

In other words, it tries to solve a lower-bound for C.

The utility in this technique is that one can return a negative result if someone makes an impossible query, or simply as a heuristic rule to be used within some other solving techniques.


  1. Numbers A and B are given.
    • If one uses this technique as a heuristic, one can try subarray sizes that are square-shaped, such as (3, 3), (5, 5), (7, 7), etc.
    • if one uses this technique to check for a negative result for a given query, use the (A, B) from that query.
  2. Convert each number into a length-N bitvector. (For example, N = 50 if at most 50 different numbers can occur in the whole array.)
  3. Define an associative operator "☀" to be the bitwise-OR of these bitvectors.
  4. Define a horizontal (row-wise) "blur" (convolution) using the associative operator as follows, which operates over a subarray of 1-by-B.
    • Output(row, column) = Input(row, column) ☀ Input(row, column + 1) ☀ Input(row, column + 2) ☀ ... ☀ Input(row, column + B - 1)
    • Note: when this filter is applied to the input array of size M-by-N, the result will have size M-by-(N-B+1).
  5. Likewise, define a vertical (column-wise) "blur" (convolution), this time operating over a subarray of A-by-1.
    • Note: when the vertical filter is applied to an intermediate array of size M-by-(N-B+1), the result will have size (M-A+1)-by-(N-B+1).
  6. Generate the "filtered" whole array as follows.
    • Let IntermediateArray = HorizontalBlur(InputArray)
    • Let FilteredArray = VerticalBlur(IntermediateArray)
  7. Now, scan the FilteredArray to find the element (bitvector) that has the least number of bits set.
    • This number is the solution for C, for the given values of A and B.

As I cautioned above, this technique isn't a solution to the puzzle. It is a kind of performance optimization technique when one needs to solve the puzzle repeatedly, or on large arrays, or on some practical applications (not for personal entertainment, learning or programming competitions).

The technique is based on a bunch of image processing / 2D pattern recognition techniques such as Image morphological operation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.