Finding biggest negative submatrix in python

how to find submatrix of a matrix
maximum size square sub-matrix with all 1s
find all submatrix of a matrix python
how to find submatrix of a matrix in c
largest rectangular sub-matrix whose sum is 0
maximum size rectangle binary sub-matrix with all 1s
find maximum sum submatrix in a given matrix python
given an n x n square matrix, find sum of all sub-squares of size k x k

I want find the biggest submatrix which contains only negative numbers in a matrix, for example:

In

[[1,  -9, -2,   8,  6,  1],    
 [8,  -1,-11,  -7,  6,  4],    
 [10, 12, -1,  -9, -12, 14],    
 [8, 10, -3,  -5,  17,  8],    
 [6,  4, 10, -13, -16, 19]]

the biggest submatrix containing only negative numbers is

[[-11, -7],
 [-1, -9],
 [-3,-5]]

(left upper corner coordinates: 1,2, right lower corner coordinates: 3,3).

What's the most effective way to do it?

A brute force solution. Will work, but may be considered too slow for a bigger matrix:

mOrig = [[1,  -9, -2,   8,  6,  1],
    [8,  -1,-11,  -7,  6,  4],
    [10, 12, -1,  -9, -12, 14],
    [8, 10, -3,  -5,  17,  8],
    [6,  4, 10, -13, -16, 19]]

# reduce the problem
# now we have a matrix that contains only 0 and 1
# at the place where there was a negative number
# there is now a 1 and at the places where a positive
# number had been there is now a 0. 0s are considered
# to be negative numbers, if you want to change this,
# change the x < 0 to x <= 0.
m = [[1 if x < 0 else 0 for x in z] for z in mOrig]

# now we have the problem to find the biggest submatrix
# consisting only 1s.

# first a function that checks if a submatrix only contains 1s
def containsOnly1s(m, x1, y1, x2, y2):
    for i in range(x1, x2):
        for j in range(y1, y2):
            if m[i][j] == 0:
                return False
    return True

def calculateSize(x1, y1, x2, y2):
    return (x2 - x1) * (y2 - y1)

best = (-1, -1, -1, -1, -1)
for x1 in range(len(m)):
    for y1 in range(len(m[0])):
        for x2 in range(x1, len(m)):
            for y2 in range(y1, len(m[0])):
                if containsOnly1s(m, x1, y1, x2, y2):
                    sizeOfSolution = calculateSize(x1, y1, x2, y2)
                    if best[4] < sizeOfSolution:
                        best = (x1, y1, x2, y2, sizeOfSolution)

for x in range(best[0], best[2]):
    print("\t".join([str(mOrig[x][y]) for y in range(best[1], best[3])]))

Will output

-11 -7
-1  -9
-3  -5

In case something else is meant with "biggest submatrix", the only function that needs to get changed is the following:

def calculateSize(x1, y1, x2, y2):
    return (x2 - x1) * (y2 - y1)

which is calculating the size of a submatrix.

Edit 1 ... first speedup

best = (-1, -1, -1, -1, -1)
for x1 in range(len(m)):
    for y1 in range(len(m[0])):
        if m[x1][y1] == 1: # The starting point must contain a 1
            for x2 in range(x1 + 1, len(m)): # actually can start with x1 + 1 here
                for y2 in range(y1 + 1, len(m[0])):
                    if containsOnly1s(m, x1, y1, x2, y2):
                        sizeOfSolution = calculateSize(x1, y1, x2, y2)
                        if best[4] < sizeOfSolution:
                            best = (x1, y1, x2, y2, sizeOfSolution)
                    else:
                        # There is at least one 0 in the matrix, so every greater
                        # matrix will also contain this 0
                        break

Edit 2

Ok, after converting the matrix into a matrix of 0 and 1 (as I do via the line m = [[1 if x < 0 else 0 for x in z] for z in mOrig] the problem is the same as what is called the maximal rectangle problem in literature. So I googled a bit about known algorithms for this kind of problem and came across this site here http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529 which is describing a very fast algorithm to solve this kind of problem. To summarize the points of this website, the algorithm is exploiting the structure. This can be done by using a stack in order to remember the structure profile which allows us to recalculate the width in case a narrow rectangle gets reused when an wider one gets closed.

Maximum size square sub-matrix with all 1s, Using the maximum value and its coordinates, we can find out the required sub- matrix. C++; C; Java; Python3; C#; PHP. C++. Finding biggest negative submatrix in python. 1. Get the coordinates of the largest submatrix. Hot Network Questions How bad is 1. e4 c5 2. Nf3 d6 3. a3?

Here is my pretty fast solution using convolutions from OpenCV. Usage of float32 is required as it is much faster than integers. Takes 135 ms for 1000 x 1000 matrix on my 2 cores. There's space for further code optimization though.

import cv2
import numpy as np

data = """1 -9 -2 8 6 1
8 -1 -11 -7 6 4
10 12 -1 -9 -12 14
8 10 -3 -5 17 8
6 4 10 -13 -16 19"""

# matrix = np.random.randint(-128, 128, (1000, 1000), dtype=np.int32)
matrix = np.int32([line.split() for line in data.splitlines()])

def find_max_kernel(matrix, border=cv2.BORDER_ISOLATED):
    max_area = 0
    mask = np.float32(matrix < 0)
    ones = np.ones_like(mask)
    conv_x = np.zeros_like(mask)
    conv_y = np.zeros_like(mask)
    max_h, max_w = mask.shape
    for h in range(1, max_h + 1):
        cv2.filter2D(mask, -1, ones[:h, None, 0], conv_y, (0, 0), 0, border)
        for w in range(1, max_w + 1):
            area = h * w
            if area > max_area:
                cv2.filter2D(conv_y, -1, ones[None, 0, :w], conv_x, (0, 0), 0, border)
                if conv_x.max() == area:
                    max_area, shape = area, (h, w)
                else:
                    if w == 1:
                        max_h = h - 1
                    if h == 1:
                        max_w = w - 1
                    break
        if h >= max_h:
            break
    cv2.filter2D(mask, -1, np.ones(shape, np.float32), conv_x, (0, 0), 0, border)
    p1 = np.array(np.unravel_index(conv_x.argmax(), conv_x.shape))
    p2 = p1 + shape - 1            
    return p1, p2

print(*find_max_kernel(matrix), sep='\n')

Largest rectangular sub-matrix whose sum is 0, To find the top and bottom row numbers, calculate sum of elements in every row from left to right and store these sums in an array say temp[]. So� Print maximum sum square sub-matrix of given size Given an N x N matrix, find a k x k submatrix where k <= N and k >= 1, such that sum of all the elements in submatrix is maximum. The input matrix can contain zero, positive and negative numbers. For example consider below matrix, if k = 3, then output should print the sub-matrix enclosed in blue.

Below is a function that executes in much less than a second for a 5000x5000 matrix. It relies only on basic np-functions.

It could be improved by returning the first index instead of all indices. Several other optimizations can be done but for many uses it is fast enough.

from numpy import roll, where
def gidx(X):
    Wl = X & roll(X, 1, axis=1)
    T = X & Wl & roll(X, -1, axis=1)
    if T[1:-1][1:-1].any():
        N = T & roll(T, -1, axis=0) & roll(T, 1, axis=0)
        if N.any(): return gidx(N)
    W = Wl & roll(Wl, 1, axis=0)
    if W.any(): return where(W)
    return where(X)

#%% Example
import numpy as np
#np.random.seed(0)
M = 100
X = np.random.randn(M, M) - 2

X0 = (X < 0)
X0[[0, -1]], X0[:, [0, -1]] = False, False
jx, kx = gidx(X0)

Find maximum sum K x K sub-matrix in a given M x N matrix, Finally, we print the sub-matrix that has maximum sum. The algorithm can be implemented as follows in C++, Java and Python: C++; Java; Python� Method I ( Naive approach ) We can easily find all the square submatrices in O(n 3) time and check whether each submatrix contains equal elements or not in O(n 2) time Which makes the total running time of the algorithm as O(n 5).

Maximum subarray problem, In computer science, the maximum sum subarray problem is the task of finding a contiguous Each number in the input array A could be positive, negative, or zero. In Python, arrays are indexed starting from 0, and the end index is typically excluded, so that the subarray [22, 33] in the array [-11, 22, 33, -44] would start at� If I have a large matrix, say a = zeros( (20,20) ) and a small matrix b = ones( 3,4 ) and a list of row indices and a list of col indices rind = [2,4,9,15] cind = [1,4,12] what is the best way to assign the submatrix to a[rind,cind].

Maximum Sum Rectangular Submatrix in Matrix dynamic , Find maximum sum rectangle in 2D matrix. https://www.facebook.com/ tusharroy25�Duration: 13:54 Posted: May 4, 2015 Python Program to find Largest Number in a List Example 2. This python program for the maximum list number is the same as above. But this time, we are allowing the user to enter the length of a List.

Programming Interview: Maximum Sub-Matrix Sum (Dynamic , Given a m x n matrix, find k x k sub-matrix that has maximum sum. For example 1 0 2 4 3 7 1 Duration: 8:43 Posted: Aug 12, 2012 Python Program to Find the Largest Among Three Numbers In this program, you'll learn to find the largest among three numbers using if else and display it. To understand this example, you should have the knowledge of the following Python programming topics:

Comments
  • Can the solution matrix contain zeros? Since 0 can be seen as both a positive and a negative number ...
  • No, in this case 0 is seen as a positive number.
  • What does "biggest" mean here?
  • @slider Probably the biggest subarea.
  • A brute-force algorithm would be quite easy to write - however I guess that there are smarter algorithms for this problem. Does the solution have to be fast?
  • This works perfectly, but too slow for bigger matrix.
  • We're talking about matrix of dimensions 5000x5000... and optimal time of solution would be less than 60 seconds. Though, I know.
  • @IvanHlivan From my understanding of the problem this should be possible. I know of a very fast algorithm that is doing something similar in 1d not in 2d. So I only need to twist my head how I can do the same in 2d ...
  • @IvanHlivan Can you provide one 5000x5000 matrix, so that I can check the time on my computer?
  • @IvanHlivan The algorithm mentioned in Edit 2 should be fast enough, you only need to convert it from pseudo code into the programming language of your choice.