Member Avatar for Rik30

Hello!

I'm trying to find the longest sequence of equal elements in a matrix M x N. I use two nested for-loops to search into the rows and compare the cells - same thing for the columns. When two adjacent elements are equal, I increment a counter. If the counter is greater than the previous one, I save the new counter value and the current element.

Now I should search in the diagonal directions. How can I do? If i and j are the indexes of a cell, the main diagonal (from left to right) has i == j. But for the secondary diagonals (from left to right and from right to left)? I also have a problem to reach the border of the matrix to avoid the IndexOutOfRangeException... Any help is appreciated.

Edited by Rik30
  • 2 Contributors
  • 10 Replies
  • 243 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by Rik30

Dani AI

Generated

Short answer: treat every direction as a set of 1-D lines and walk each line while staying inside bounds. That removes index errors and makes the diagonal case the same pattern you used for rows/columns. already noted the anti‑diagonal trick (i + j constant); for main diagonals use i - j constant. An easy, robust implementation is to generate the correct starting cells for each direction (top row + left column for top-left→bottom-right, top row + right column for top-right→bottom-left) and then step with a fixed delta until you leave the matrix.

Example (Python) — a compact, reusable scanner that works for rows, columns and both diagonal directions:

def longest_equal_sequence(mat):
    if not mat or not mat[0]:
        return 0, None
    R, C = len(mat), len(mat[0])

    def scan(starts, di, dj):
        best_len, best_val = 0, None
        for i0, j0 in starts:
            i, j = i0, j0
            prev, run = None, 0
            while 0 <= i < R and 0 <= j < C:
                v = mat[i][j]
                if v == prev:
                    run += 1
                else:
                    prev, run = v, 1
                if run > best_len:
                    best_len, best_val = run, v
                i += di; j += dj
        return best_len, best_val

    directions = [
        ([(r, 0) for r in range(R)], 0, 1),                      # rows
        ([(0, c) for c in range(C)], 1, 0),                      # cols
        ([(0, c) for c in range(C)] + [(r, 0) for r in range(1, R)], 1, 1),   # TL->BR
        ([(0, c) for c in range(C)] + [(r, C-1) for r in range(1, R)], 1, -1) # TR->BL
    ]

    best = (0, None)
    for starts, di, dj in directions:
        length, val = scan(starts, di, dj)
        if length > best[0]:
            best = (length, val)
    return best

Troubleshooting notes: the common IndexOutOfRange in 's snippet comes from not initializing per-diagonal indexes (j in the while loop) or not guarding the while condition. Always set the start (i0,j0) for each diagonal and use a loop condition like 0 <= i < R and 0 <= j < C. Complexity is O(R*C) overall because each cell is visited a constant number of times across the four direction scans. This same pattern maps cleanly back to C# by replacing the Python loops and bounds checks with equivalent C# code.

Recommended Answers

All 10 Replies

Member Avatar for ddanbe

Hi Rik30, welcome at DaniWeb. :)
Could you show us the method you're having trouble with?

Member Avatar for Rik30

Sure! :) I have written the following code:

for (int i=0; i<arr.Length(0)-1; i++) // check rows
{
    for (int j=0; j<arr.Length(1)-1; j++)
    {
        if(arr[i,j]==arr[i,j+1])
            k++;

        if(k > temp)
        {
            temp = k;
            value = arr[i,j];
        }
    }

    k = 0;
}

for (int i=(arr.GetLength(0)-2); i>=0; i--) // check diagonals (left to right) ?
{
    while (!border) // border ??
    {
        if (arr[i,j] == arr[i+1,j+1])
        {
            k++;
        }

        if (k > temp)
        {
            temp = k;
            value = arr[i,j];
        }

        j++; // ?
    }

      counter = 0;
 }

But I cannot imagine a method for the diagonal directions... I also did some sketches on a sheet of paper to find a solution...

Edited by Rik30
Member Avatar for ddanbe

You say you have IndexOutOfRangeExceptions could you explain what your Length method is doing?
And to traverse diagonal, do you mean
1 2 3
4 5 6
7 8 9
[3] [2,6] [1,5,9] [4,8] [7] ?

Member Avatar for Rik30

Yes, I mean it. The matrix can be of any size N x M.

I'd start from the penultimate row, first column (the corners cannot be a sequence). Then, I'd compare the cell with another that has indexes i+1 and j+1 (as temporary values?), and so on... until the border is reached. But how can I be sure that I have reached the border? When the row is 0 (after decrements), I should increment the column... (?)

Edited by Rik30
Member Avatar for ddanbe

OK, Took me awhile but this code will print out the diagonal values of a MxN array.

for (int i = 0; i < M; i++)
            {
                int j = 0;
                int k = i;

                Console.WriteLine("Diagonal nr {0}", diagCnt);
                diagCnt++;
                while (j < N && k >= 0)
                {
                    Console.WriteLine(">> {0}", R[j, k]);
                    k--;
                    j++;
                }               
            }
            for (int i = 1; i < M; i++)
            {
                int j = M - 1;
                int k = i;

                Console.WriteLine("Diagonal nr {0}", diagCnt);
                diagCnt++;
                while (j >= 0 && k < N)
                {
                    Console.WriteLine(">> {0}", R[k, j]);
                    k++;
                    j--;
                }               
            }   
            Console.ReadKey();
Member Avatar for Rik30

Thank you! :)

It was quite tricky for me

Member Avatar for Rik30

Hmm... there is an issue. I solved it by noting that the sum of the indexes is the same (from right to left).

Example:
1 2 3
4 5 6
7 8 9

[2,4] has i + j = 1
[3,5,7] has i + j = 2
[6,8] has i + j = 3

But for the other diagonals (left-to-right)?

Edited by Rik30
Member Avatar for ddanbe

Still working on a solution in all directions. Been in hospital lately, I'll keep in touch.

Member Avatar for Rik30

No problem, thank you once again for your time :)

PS: I'm not English... I have written "issue" instead of "problem" thinking it is a synonym. I'm sorry for the misunderstanding

Edited by Rik30
Member Avatar for Rik30

Resolved.

To find the right-to-left diagonals I have split the problem in two sub-problems: the lower left and the upper right of the matrix.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.