2d array search optimization

Question

I wrote a code in order to find 3 repeated elements in a row/column in 2d array.

private static bool SearchInRows(int[,] matrix)
{
    int count = 1;
    int repeatElement = int.MaxValue;

    //Search in rows
    for (int i = 0; i < matrix.GetLength(0); i++)
    {
        repeatElement = matrix[i, 0];

        for (int j = 1; j < matrix.GetLength(1); j++)
        {
            if (repeatElement == matrix[i, j])
            {
                count++;
                if (count >= 3)
                {
                    Console.WriteLine($"Repeated elements are in positions i:{i}, j:{j - 2}, {j - 1}, {j}");
                    return true;
                }
            }
            else
            {
                repeatElement = matrix[i, j];
                count = 1;
            }
        }
    }
    return false;
}
private static bool SearchInCols(int[,] matrix)
{
    int count = 1;
    int repeatElement = int.MaxValue;

    //Search in cols
    for (int j = 0; j < matrix.GetLength(1); j++)
    {
        repeatElement = matrix[0, j];

        for (int i = 1; i < matrix.GetLength(0); i++)
        {
            if (repeatElement == matrix[i, j])
            {
                count++;
                if (count >= 3)
                {
                    Console.WriteLine($"Repeated elements are in positions j:{j}, i:{i-2}, {i-1}, {i}");
                    return true;
                }
            }
            else
            {
                repeatElement = matrix[i, j];
                count = 1;
            }
        }
    }
    return false;
}

It works fine, but I will do something like this:

while (!SearchInRows(matrix) && !SearchInCols(matrix))
{
    SearchInRows(matrix);
    SearchInCols(matrix);
    //modify the matrix
}

And I am wondering, if I can use something to improve the performance of my code, like adding the Task.Run on each method or something (I split the method in cols and rows for that).

Answer 1

There are more performant solutions to your problem, since your functions essentially require you to iterate twice over each element (once for the columns, once for the rows). And with the way you call your functions, you have even more iterations.

This is a more efficient solution I came up with, but there might be better ones. Basically, I only iterate once over each element and check if the next two elements in the column and row match. For example, lets look at the following 8x8 2d array. I iterate once over each element in the red box and check if the next two elements in the row/column match. This leaves me with two rows and two columns unchecked, which I have to check individually.

Here is the code:

private static void FindThreeRepeatedElements(int[,] matrix)
{
    // iterate once trough each element (red box) and check
    // if the next 2 elements in the row / column match
    for(int row = 0; row < matrix.GetLength(0) - 2; row++)
    {
        for (int column = 0; column < matrix.GetLength(1) - 2; column++)
        {
            CheckRow(matrix, row, column);
            CheckColumn(matrix, row, column);
        }
    }

    // check the last remaining 2 rows
    CheckRow(matrix, matrix.GetLength(0) - 2, matrix.GetLength(0) - 3);
    CheckRow(matrix, matrix.GetLength(0) - 1, matrix.GetLength(0) - 3);

    // check the last remaining 2 columns
    CheckColumn(matrix, matrix.GetLength(0) - 3, matrix.GetLength(0) - 2);
    CheckColumn(matrix, matrix.GetLength(0) - 3, matrix.GetLength(0) - 1);
}

private static void CheckRow(int[,] matrix, int row, int column)
{
    int element = matrix[row, column];
    if (element == matrix[row, column + 1] && element == matrix[row, column + 2])
    {
        Console.WriteLine($"Three repeated elements with value {element} are found in row {row} at the positions: [{row}, {column}], [{row}, {column + 1}], [{row}, {column + 2}]");
    }
}

private static void CheckColumn(int[,] matrix, int row, int column)
{
    int element = matrix[row, column];
    if(element == matrix[row + 1, column] && element == matrix[row + 2, column])
    {
        Console.WriteLine($"Three repeated elements with value {element} are found in column {column} at the positions: [{row}, {column}], [{row + 1}, {column}], [{row + 2}, {column}]");
    }
}

As you pointed out in the comments a while ago, there are some cases where the checking of some elements can be skipped, since they already have been checked previously. For example, if we look at the 8x8 2d array again, after comparing the elements in the blue box, we see that the first two elements match (both have value 7), so we check if the third element also has value 7, which fails (it has value 4). Now we already know that we can skip the checks for the next three elements in the row (orange box), because when we get to the elements with value 7, 4 and 5 we already did the comparison of the first two elements in the previous iteration.

I modified the code from above to skip those comparisons, which leaves us with more code but technically less comparisons (not sure if it is actually much more performant). In this example, the bool _skipNextRowCheck would be true after doing the comparisons in the blue box, which would completely skip checking if the 3 elements in the orange box have equal values.

Here is the modified code:

private static bool _skipNextRowCheck = false;
private static bool _skipNextColumnCheck = false;

private static void FindThreeRepeatedElementsWithSkips(int[,] matrix)
{
    // iterate trough each element and check
    // if the next 2 elements in the row / column match
    for (int row = 0; row < matrix.GetLength(0) - 2; row++)
    {
        for (int column = 0; column < matrix.GetLength(1) - 2; column++)
        {
            CheckRowWithSkips(matrix, row, column);
            CheckColumnWithSkips(matrix, row, column);
        }
    }

    // check the last remaining 2 rows
    CheckRowWithSkips(matrix, matrix.GetLength(0) - 2, matrix.GetLength(0) - 3);
    CheckRowWithSkips(matrix, matrix.GetLength(0) - 1, matrix.GetLength(0) - 3);

    // check the last remaining 2 columns
    CheckColumnWithSkips(matrix, matrix.GetLength(0) - 3, matrix.GetLength(0) - 2);
    CheckColumnWithSkips(matrix, matrix.GetLength(0) - 3, matrix.GetLength(0) - 1);
}

private static void CheckRowWithSkips(int[,] matrix, int row, int column)
{
    if(_skipNextRowCheck)
    {
        _skipNextRowCheck = false;
        return;
    }

    int element = matrix[row, column];
    if (element == matrix[row, column + 1])
    {
        if(element == matrix[row, column + 2])
        {
            Console.WriteLine($"Three repeated elements with value {element} are found in row {row} at the positions: [{row}, {column}], [{row}, {column + 1}], [{row}, {column + 2}]");
        }
        else
        {
            _skipNextRowCheck = true;
        }
    }
}

private static void CheckColumnWithSkips(int[,] matrix, int row, int column)
{
    if (_skipNextColumnCheck)
    {
        _skipNextColumnCheck = false;
        return;
    }

    int element = matrix[row, column];
    if (element == matrix[row + 1, column])
    {
        if(element == matrix[row + 2, column])
        {
            Console.WriteLine($"Three repeated elements with value {element} are found in column {column} at the positions: [{row}, {column}], [{row + 1}, {column}], [{row + 2}, {column}]");
        }
        else
        {
            _skipNextColumnCheck = true;
        }
    }
}

And here is a main function with the pictured 2d array, simply copy the main function and all the other functions into one Program class to try it out:

static void Main(string[] args)
{
    int[,] matrix = new int[8, 8] 
    { 
        { 7, 7, 7, 4, 5, 6, 1, 8 },
        { 1, 4, 3, 4, 3, 9, 3, 8 },
        { 1, 2, 3, 4, 3, 6, 7, 8 },
        { 1, 4, 7, 4, 5, 4, 7, 8 },
        { 1, 2, 3, 4, 5, 5, 3, 5 },
        { 1, 1, 1, 7, 5, 9, 9, 9 },
        { 1, 2, 7, 6, 5, 9, 9, 9 },
        { 1, 2, 3, 4, 5, 9, 9, 9 },
    };

    Console.WriteLine("\nSearching for three repeated elements in the 2d array:");
    FindThreeRepeatedElements(matrix);

    Console.WriteLine("\nSearching for three repeated elements in the 2d array, and skipping unneccessary comparisons:");
    FindThreeRepeatedElementsWithSkips(matrix);
}