Greatest Distance between Equal Numbers in Array

Question

let's say I have a matrix (array) like this example, but much larger:

0 0 5 0 3 6 6 4 0 3 0 8 0 1 1
9 4 0 6 0 0 0 4 1 0 6 0 7 0 0
3 1 6 1 5 0 8 0 8 0 3 2 6 4 8
1 0 2 2 8 5 8 1 8 7 4 1 0 3 0
6 3 8 1 0 0 4 0 0 3 1 5 2 0 0
0 0 5 0 3 6 6 4 0 3 0 8 0 1 1
9 4 0 6 0 0 0 4 1 0 6 0 7 0 0
3 1 6 1 5 0 8 0 8 0 3 2 6 4 8
1 0 2 2 8 5 8 1 8 7 4 1 0 3 0
6 3 8 1 0 0 4 0 9 4 1 5 2 0 0

I'm trying to determine the position of two equal numbers with greatest distance between them in the array in a diagonal, horizontal or vertical straight line, with the distance calculated as the count of numbers between them (distance d >= 0).

Other Constraints:

• The straight line as described above may not contain the same number that is marking its beginning and end, so you can't have 6 0 4 5 6 1 7 3 5 6 and say distance 6..6 is 8 as there is a 6 in the sequence.
• The numbers to look for are not given but must be determined dynamically.

In the example the result (considering the array as a regular X|Y coord system with 0, 0 in the lower left) it should determine P1(0, 8), P2(8, 0) with d = 7 (number: 9).

Any good ideas on how to do this efficiently? I'm using C# but examples/ideas in other languages are appreciated too.

In case you wonder where this question comes from, I've been thinking about various math related challenges that I believe are tough to solve (for myself) and hope to get a better handle on such problems by seeing how others solve such issues. Thank you!

Answer 1

Algorithm:

Simplify the problem. It is equivalent to solving the 1-dimensional version (find largest gap between equal values in a list) once per row, column and diagonal then returning the maximum.

Simplify more. The 1-dimensional version is pretty easy. You just build a Dictionary which maps values to a list of their positions, solve the trivial problem of 'what is the largest delta in this list of positions' for each value, and return the maximum.

Analysis:

The trivial problem takes linear time in the size of the position list (because the list is sorted [by the natural insertion order]). Therefore the 1-dim gap problem takes linear time in the size of the value list (because there is one position per value). Therefore the 2-dim gap problem takes linear time in the size of the matrix (because each value is included in exactly four 1-dim sub-problems).

So if the matrix is nm, the solution will take O(nm) time. It requires O(n+m) space (to store the value->positions dictionary during each 1-dim phase). I really doubt you'll do better (the time is clearly optimal, not so sure about the size).

Answer 2

I don't see how you can do this really any faster besides just iterating through each row, each column, and each diagonal (you can tell if something's on the same diagonal by taking the absolute value of the difference of its X and Y coordinates, of course) and keeping track of the most recent coordinates of each number you see, and the greatest observed separation.