Solution: Find the length of the longest sequence in a 2D array
This was a problem I failed to solve in time. In my last post, I outlined the problem and described it in easier-to-understand terms. Now let’s see how to solve it.
The Problem
In summary, we’re given a 2D array with N rows and M columns, and we are asked to find the length of the longest possible increasing subsequence.
Conditions
- We are only allowed to go in two directions— right and/or down.
- The elements picked have to be in increasing order.
Here’s what it looks like when I draw it out:
The Solution
Here, we use a method called dynamic programming to solve it. We can break down a problem into many smaller parts, and solve them just once, instead of having to compute them multiple times.
Let’s look at the rightmost element in the bottom row.
What’s the length of the longest subsequence we can form if we start with this element? Obviously, we can’t move right or down any further, so we can only include this element. The length is just 1. We’ll record that result in another array called longest.
Now let’s look at this arrangement. What’s the length of the longest subsequence I can form if I start with the number outlined in blue (7)? It’s not smaller than the next number, 7, so that’s the only number we can include in any subsequence starting there. Thus, the longest possible subsequence is also of length 1.
And what about here? What is the longest possible subsequence I can form, if I start with this element? In this case, we can go from 0 to either 7, or 7, as both elements are greater than 0.
But what we’re interested in is not really what number we’re jumping to, but rather, the longest possible subsequence length we can achieve. And we already know the maximum length of subsequences that can be formed with each element that is to the right and/or below the current element (as we’ve recorded it in the longest table).
Here, we determine that the maximum length of a subsequence starting at 0 would be 1 plus the maximum length of the subsequence starting at the next valid element.
To illustrate this further, see below.
For the element 1, the maximum length of the subsequence starting at 1 is 2.
Why? Because 1 can go to either 7 or 7, and both of them have a maximum length of 1. So we add 1+1 to the corresponding entry in our table longest.
We continue doing this, row by row. But it gets more interesting as there are more elements to the right and/or below the current element.
I’m going to skip a few steps and go to the second row. Notice that we’re only interested in the elements to the right and below our target element, as those are the only ones that we can go to.
The longest subsequence starting at 5 is of length 2. Because 5 < 7, the length is determined by taking the maximum length starting at 7, and then adding 1 to that.
Now it starts getting interesting. We’re starting to look at elements both to the right and below the current element. We need to look at all the elements highlighted in red. Here, 0 is smaller than any of the numbers and can “jump” to any of them. But remember that we’re only interested in the maximum subsequence length.
So which one of these should I pick if I want the longest possible subsequence? That would be element 5, as it is already the beginning of a subsequence of length 2. Adding 1 to that would give us 3.
Starting at element 0, we’d be able to form a subsequence of length 1 + 2 = 3, so we record that in longest.
So let’s fast forward and see what we end up with.
Now that we’ve filled out longest accordingly, what does it tell us?
We can see that the longest subsequence length is 5, and it starts at A[0][1].
Just to confirm that it’s right:
And there you have it!
Keep in mind that when implementing it, it’s important to keep track of the largest length you see, so you don’t have to do another search to find out what the longest possible length is.
Efficiency
Let’s look at the worst case time complexity and space complexity of this solution.
Time complexity
Worst Case Time complexity: O( N² M² )
Regarding time complexity, the number of comparisons we do is always (M(M+1)/2) x (N(N+1)/2).
How did we get this number?
If there was only one row, i.e., N = 1, then we would go through the row starting at the last element, looking at just itself. (one operation)
Next, we would be at the second last element, looking at itself and the one to its right. (two operations)
Then we would be at the third element, comparing it to itself and to the two elements to its right. (three operations)
And so forth, until we’re at the beginning of the row, and doing comparisons against all the other elements to the right of it. (M operations)
So in total, we’d do 1+2+…+M operations. We can simplify this to (M(M+1)/2), as Gauss had discovered.
Now, if there are multiple rows, then for the second row, the number of operations would be 2 x (1+2+…+M).
The third row would require 3 x (1+2+…+M) operations.
For N rows, the number of operations required would be
(1+2+…+N) x (1+2+…+M)
We can simplify it using Gauss’s method, leaving us with
(M(M+1)/2) x (N(N+1)/2)
We can simplify this to (1/2) M N (MN + M + N + 1) (I’ll let you work out the steps yourself!)
(1/2) (M²N² + M²N + MN² + 1)
Big O notation is a representation of how quickly the time required will increase (as a function of the size of input). Usually, when we deal with big O notation, we care only about the fastest growing term, so we can remove constants and other lower order polynomials. Here, M²N² is the fastest growing term, so we can discard everything else.
Thus, the solution’s time complexity is O( N² M² ).
Space complexity
Worst Case Space complexity: O( N M ) (excluding the space required for storage of input)
For each element, we keep track of the maximum possible length of a subsequence starting from it. There are N x M elements, so the space complexity is O(N M).
Implementation
Here’s my implementation of the solution in Java.
If you can think of a more efficient solution, I’d love to hear it. Feel free to leave a comment below!
