Problem: Find the length of the longest sequence in a 2D array

This was a problem that stumped me and stopped me from completing a coding competition in time. You can find the background story here. The solution is published in a subsequent post.

The Problem

(For an explanation in plain English, see the next section.)

You are given a 2D array A of N rows and M columns. There exists two arrays I and J, whose elements represent the row indices and column indices of A respectively. The following conditions must be met:

I and J are both of length L

I is non-decreasing. That is, I[p] ≤ I[p+1], for all o ≤ p < L-1

J is non-decreasing. That is, J[p] ≤ J[p+1], for all o ≤ p < L-1

Each element I[p] represents a row index of A, and each element J[p] represents a column index of A. In other words:

For all 0 ≤ p < L:

0 ≤ I[p] < N

0 ≤ J[p] < M

The row and column indices in I and J are used to form a subsequence of A. Essentially, this is an array of length L with indices 0 ≤ p < L, where each element is A [I[p]] [J[p]].

The subsequence is increasing.

So for all o ≤ p < L-1:

A [I[p]] [J[p]] < A [I[p+1]] [J[p+1]]

What is the length of the longest possible subsequence of A?

My Thinking Process

What are they asking for, in plain English?

Understanding the Problem

Whenever I see this kind of problem, I have no idea what it’s asking, so of course the first thing I do is to visualize it.

So let’s draw out the 2D array A, with N rows and M columns.

Looks simple enough.

Now what about arrays I and J? And that messy looking bunch of symbols, A [I[p]] [J[p]]? Let’s try to simplify that by looking at I and J first.

I and J are arrays of row and column indices of 2D array A. So what’s I[p] and J[p]? Those would be the pth row index, and the pth column index.

Let’s assume I[p] is 3 and J[p] is 3. So A [I[p]] [J[p]] is just referring to an element in A, in row 3 and column 3!

So how does that tie in to what we’re doing? Recall that we’re trying to find a subsequence of A. (In simpler terms, we’re picking out a bunch of different elements from A.) The subsequence is ordered, so A [I[p]] [J[p]] is another way of saying the pth element in that subsequence!

But obviously we can’t just pick a bunch of random elements and call it a day. So what are the conditions?

1. The subsequence has to be increasing, so each term has to be greater than the one before it.
2. The row indices and column indices have to be non-decreasing. The key distinction is that each term can be greater or the same as the previous one.

How to describe this in simpler terms? Turns out it’s quite easy to understand once you visualize it.

Here, we see that we’re picking elements from A, and there’s an obvious pattern — we can only go from left to right, and top to bottom.

Why can’t we go from right to left, or bottom to top? Because that would violate the requirement that I and J be non-decreasing.

Keep in mind that the elements in the subsequence have to be increasing (in ascending order).

As you can see, there can be more than one possible subsequence where its elements are increasing.

Our task is to find the length of the longest possible subsequence. (There may be more than one longest subsequence, but there is always only one possible length.)

The Solution

I saved the solution for a subsequent post, as I find that these posts (especially technical ones) take quite a long time to write! Stay tuned.