CODEWITHSUNDEEP
arraysalgorithm
epon
epon

Reputation: 43

Algorithm for finding saddle-points in a 2-dimensional array

I'm looking for an algorithm to find the positions of all saddle points in an NxN matrix.

Searching through other answers on StackOverflow, as well as other sites in general, I've only found solutions regarding saddle points that operate in one direction. That is, I want to find a saddle point that can be a maximum in its row and minimum in its column, or a minimum in its row and maximum in its column.

For example, given:

array = {
{ 10, 15, 20, 15, 10 } 
{ 5, 10, 15, 10, 5 }
{ 0, 5, 10, 5, 0 }
{ 5, 10, 15, 10, 5 }
{ 10, 15, 20, 15, 10 } },

the saddle points are the 10's in the corners and the 10 in the middle.

I can find them naively fairly easily, but I wanted something more efficient. I've been told it can be done in O(n^2).

I thought perhaps I could fix the x-coordinate and iterate through the y-coordinate to find all maximums and minimums, then reverse the process by fixing the y-coordinate and iterating through the x-coordinate, but I can't quite visualize it well enough to implement the idea.

Any help would be greatly appreciated.

Upvotes: 3

Views: 5482

Answers (2)

Amir Touitou
Amir Touitou

Reputation: 3451

O(n^2)

#include <stdio.h>

#define N 8
#define M 10

int arr[N][M] =
{ {1,2,0,3,9,4,5,3,6,7},
  {2,4,3,5,9,0,2,3,4,1},
  {5,3,4,7,6,1,9,0,4,2},
  {6,9,7,8,6,7,7,4,5,6},
  {8,3,1,9,2,0,6,2,8,2},
  {2,7,3,0,3,6,3,1,5,3},
  {8,2,5,9,7,7,8,3,7,3},
  {1,7,4,8,5,8,5,0,0,6} };

int FindSaddlePoints(int arr[N][M])
{
    int l_result = 0;

    int l_row[M], l_column[N], i, j, index;

    //find the min
    for (i = 0; i < N; i++)
    {
        index = 0;
        for (j = 1; j < M; j++)
        {
            if (arr[i][j] < arr[i][index])
            {
                index = j;
            }
        }
        l_column[i] = index;
    }

    for (j = 0; j < M; j++)
    {
        index = 0;

        //find the max
        for (i = 1; i < N; i++)
        {
            if (arr[i][j] > arr[index][j])
            {
                index = i;
            }
        }
        l_row[j] = index;
    }

    for (i = 0; i < N; i++)
    {
        for (j = 0; j < M; j++)
        {
            if (l_row[j] == i && l_column[i] == j && i != N && j != M)
            {
                //printf("found in row = %d column = %d", i, j);
                l_result++;
            }
        }
    }

    return l_result;
}
void main()
{
    int number = FindSaddlePoints(arr);

    printf("%d", number);
}

Upvotes: 1

nhahtdh
nhahtdh

Reputation: 56819

Notice that in the naive implementation O(n3), you are recalculating the maximum value and minimum value for every element of a row/column you go through.

To eliminate this inefficiency, the idea is to loop through every row and column, and mark all positions with the maximum and minimum value in a separate N x N array. Each element of this separate array contains 2 pieces of boolean information: isMax and isMin (which can be encoded as bit if you want to). If all elements in a row/column are the same (i.e. maximum value = minimum value), then you might not want to mark any element.

For each row/column, this can be done in O(n) time. Use an n-element array to record the indices where the current maximum (minimum) value, and clear the array if there is a bigger (smaller) value than the current maximum (minimum). After you have finished looping through, use the information from the maximum (minimum) indices array to mark the corresponding isMax (isMin) field in the N x N array.

Since there are n rows and n columns, the complexity of this step is O(n2)

Then the rest is to loop through the N x N array which you have marked to search for any position with both isMax and isMin set.

Upvotes: 1

Related Questions