Search This Blog

Friday, October 15, 2010

Kadane's 2D Algorithm

Kadane's 2D Algorithm

Kadane's 2D algorithm uses Kadane's 1D algo. So i expect anyone to know Kadane's 1D algo.

Kadane's 1D algo, finds the maximum contigous sum in an 1D array in O(n) time complexity.

Now to the 2D algo. Lets consider the problem of finding a maximum sub-matrix from a matrix. Consider the below matrix 'm'-

1 2 -1
-3 -1 -4
1 -5 2

the maximum sub matrix in this example is - [1 2]

To do this programatically, do follow the steps below.

Step1
Create a temp matrix temp[3][3]. Any element in this matrix temp[i][j] is the sum of all temp[1][j], temp[2][j]...temp[i][j].

That's temp[i][j] = temp[1][j]+temp[2][j].+..+temp[i][j].

So our temp matrix is

1 2 -1
-2 1 -5
-1 -4 -3
This has a time complexity of n^2

Step2
Now in this 3 x 3 matrix, the row can be grouped as [1],[1,2],[1,2,3],[2],[2,3],[3].

We can find the sum of these above row combinations using the temp matrix we created as below.

[1] = Row 1 in temp matrix - [1,2,-1]
[1,2] =Row 2 in temp matrix - [-2,1,-5]
[1,2,3] = Row 3 in temp matrix - [-1,-4,-3]
[2] = Row 2 - Row 1 in temp matrix - [-3,-1,-4]
[2,3] = Row 3 - Row 1 in temp matrix - [-2,-6,-2]
[3] = Row 3 - Row 2 in temp matrix - [1,-5,2]

This has a time complexity of n^2

Step3
Now i provide each of the above row to Kadane's 1D algo to find the maximum contigous sub-sequence. After the algo processed all the rows the maximum we have is for row [1] - column 0 to column 1.

So the maximum sub matrix is from m[0][0] to m[0][1] thats [1 2].

The time complexity is n^3.
This solution will work for any matrix including positive and negative numbers.

5 comments:

  1. Nicely explained...

    when I read the problem for the first time,
    I did not know this algorithm..

    I also assumed that given NxN matrix,
    i have to find out the submtrix of size KxK where k<N

    I tried solving it myself and I came uptil Step 2,and (honestly)later had difficulty in coming till 3 and then I search it and landed to your blog...

    However the way i reached till step 2 was different...i was trying to solve it in N^2 LOL
    ;o)

    As in step 1 you created column sum matrix...
    along with that I also created row sum matrix...

    and later on an intersection matrix of both ..and answer was in front of my eyes(find the maximum sum in one dimension) and i could not see it...

    ReplyDelete
  2. How do I do this part?

    [2] = Row 2 - Row 1 in temp matrix - [-3,-1,-4]
    [2,3] = Row 3 - Row 1 in temp matrix - [-2,-6,-2]
    [3] = Row 3 - Row 2 in temp matrix - [1,-5,2]

    I'm having trouble getting past this part, any help would be good.

    ReplyDelete
  3. Thanks for clear explanation..:)

    ReplyDelete
  4. Excellent tutorial. Was scanning the net for something similar the entire day. Here's the code I wrote in python for it:

    import time

    def kadane(aSeq):
    transientTotal=aSeq[0]
    transientStartIndex=0
    total=aSeq[0]
    start=0
    end=0
    for i in range(1,len(aSeq)):
    transientTotal+=aSeq[i]
    if transientTotal<aSeq[i]:
    transientTotal=aSeq[i]
    transientStartIndex=i
    if total<transientTotal:
    total=transientTotal
    start=transientStartIndex
    end=i
    return (total,start,end)

    def maxSubMatrix(aSeq):
    rows=len(aSeq)
    cols=len(aSeq[0])
    prefix=[[i-i for i in range(0,cols)],
    [i-i for i in range(0,cols)],
    [i-i for i in range(0,cols)]]

    for i in range(0,rows):
    for j in range(0,cols):
    prefix[i][j]=aSeq[i][j]

    top=left=bottom=right=-1

    for i in range(0,cols):
    for j in range(1,rows):
    prefix[j][i]+=prefix[j-1][i]

    summer=-999999
    for i in range(0,rows):
    for j in range(i,rows):
    if i==0:
    temp=prefix[j]
    else:
    temp=[prefix[j][t]-prefix[i-1][t] for t in range(0,cols)]

    kadaneTuple=kadane(temp)
    if(summer<kadaneTuple[0]):
    summer=kadaneTuple[0]
    top=i
    left=kadaneTuple[1]
    bottom=j
    right=kadaneTuple[2]

    output=[]
    for i in range(top,bottom+1):
    x=[aSeq[i][j] for j in range(left,right+1)]
    output.append(x);
    print summer,output

    if __name__=="__main__":
    seq=[[-3,2,3],
    [-9,5,6],
    [-1,-2,-3]]
    start=time.time()
    maxSubMatrix(seq)
    print "%d (ms)" % ((time.time()-start)*1000)

    ReplyDelete
  5. good explanation ....really helped me a lot....

    ReplyDelete