'Computational complexity of finding (not necessarily contiguous) longest zero 'subarray'
I understand that there are efficient algorithms to find contiguous zero subarrays of any given 2-dimensional array of numbers. Is there an algorithm for finding zero 'subarrays' which are not necessarily contiguous? If so, the details of the algorithm and its computational complexity of such an algorithm would be helpful. (Here, 'subarrays' is included in quotes, as in general, the definition of subarrays itself requires the smaller array to be contiguous.) A simple example: Consider an n X n array with 1 in its (2,3)th entry and 0 elsewhere. Then it contains a zero 'subarray' of size (n-1) X (n-1). Thanks in advance.
Added later: The time complexity for finding a contiguous 2-dimensional subarray is O(n^2). Is it possible to get a solution for non-contiguous 'subarray' with same time complexity?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|