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.

Josephus Problem

Josephus Problem

In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.

There are people standing in a circle waiting to be executed. After the first person is executed, certain number of people are skipped and one person is executed. Then again, people are skipped and a person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

Lets consider 'n' as the number of people and i execute every 'k'th person. What will be the initial position of the survivor?

There are multiple solutions to this. Lets start with the easy on of using a linked list.

Naive solution

1. Create a circular linked list with 'n' nodes each having info about their position in the list.
2. Start at first element.
3. from current element keep moving to next element until you reach 'k'th element.
4. Remove the 'k'th element from the list.
5. Now 'k + 1'th is current element. Repeat steps 3, 4 and 5 until there is only one element in the list.

Now the space complexity is O(n).

You will walk the list 'k' times to one node delete node. Hence the time complexity is O(nk).

More Efficient Solution

A more efficient solution is to use dynamic programming.

We have the recurrence here

f(n,k) = (f(n-1,k) + k)%n with f(1,k) = 0

How does this recurrence work?

Lets consider that i know the survivor position is 's' for a given number of people 'n' and skip count 'k' where i start counting from position 1.

so if the list is as below

1 2 3.......s.....n-1 n

now i want to find the survivor position for n + 1 elements with same skip 'k'.
So let me introduce one more person 'n + 1' as below.

1 2 3.......s.....n-1 n n+1

If i eliminate the 'n + 1'th person first, then, the next time i start counting 'k' from position '1', which would give me the same result when i had only 'n' persons to count - that's 's'.

But here we are starting at position (n + 1 - k). So if i have to start at position '1' then the result will be (s + k)%n.

Thats how we get the above recurrence.

Hope i am clear in explaining this.
You can also have a look at dicussion on Problem - Kidsgame at TopCoder SRM 315 for different solutions to this problem.

I havent yet decided

I did not know what my blog should be about and that confusion became the name of my blog. Long after creating this blog i have decided to post something technical here. Let me see how long i can write...Lots of chances that this wont even take off :)