how to find the element which is greater than or equal to its row and smaller or equal to its column in a matrix

Hi everyone; I am going to find the saddle points of a matrix M. The question is given below...

Write a function called saddle that finds saddle points in the input matrix M. For the purposes of this problem, a saddle point is defined as an element whose value is greater than or equal to every element in its row, and less than or equal to every element in its column. Note that there may be more than one saddle point in M. Return a matrix indices that has exactly two columns. Each row of indices corresponds to one saddle point with the first element of the row containing the row index of the saddle point and the second column containing the column index. The saddle points are provided in indices in the same order they are located in M according to column-major ordering. If there is no saddle point in M, then indices is the empty array.

I am trying that code:

function indices = saddle(M)
[ rows,cols ] = size(M);
[valR,posR] = max(M,[],2);
[valC,posC] = min(M,[],1);
indices= [];
for i = 1:length(posR)
    if i == posC(posR(i))
        indices= [indices; i, posR(i)];
    end
end
end

It is running fine. But when i test my code for

>> mat=zeros(5,3)

mat =

       0     0     0
       0     0     0
       0     0     0
       0     0     0
       0     0     0
I am getting wrong output :

saddle(mat)

ans =

       1     1

the correct output must be

saddle(mat)
ans =
     1     1
     2     1
     3     1
     4     1
     5     1
     1     2
     2     2
     3     2
     4     2
     5     2
     1     3
     2     3
     3     3
     4     3
     5     3

What i am doing wrong?? Thanks in advance

[Sanket khullr]

function indices = saddle(M)
X = (max(M,[],2))';  % operation on row arranged in a column i.e maximum of each row arranged in a column and then transpose gives the row vector of  the same
Y = min(M,[],1); %operation on column arranged in  row i.e. minimun of each column arranged in a row
count=0;
for i=1:size(X,2)
    for j=1:size(Y,2)
        if X(i)==Y(j)
            count = count+1;
            indices(count,:) = [i,j];
        end
    end
end
if count==0
    indices = double.empty;
end


            

[Jack Crespo]

I have an issue for returning an empty matrix if there are no saddle points. I dont know where to put the statement in my code. I currently have it under the check if a point is a saddle point, but whenever a point is not, it returns the empty matrix. If i delete the else statement, the code works for matrices with saddle points.

function indices = saddle(M)
row = size(M,1);
col = size(M,2);
if row==1
    maximum = max(M);
    [first, second]= find(M==maximum);
    indices=[first;second]';
else 
    maximums = max(M,[],2)';
    minimums = min(M,[],1);
    for i=1
        for j=1:col
            for x=1
                for y=1:col
                   if maximums(i,j)==minimums(x,y)       %check if a point is a saddle point
                     [first,second]= find(M==maximums(i,j));
                     indices=[first second];             %returns the indices of the saddle points
                     
                   else                                  %else statement if a matrix has no saddle points
                       indices=[];
                       break
                   end
                end
            end
        end
    end
end

[Xenium Adil]

hey budies i am still stuck at sparse2matrix and have almost completed the course help me out solving that......... trying this code

function [matrix]=sparse2matrix(incell)
S=size(incell);
q=S(2)-2;
msize=incell{1};
mdef=incell{2};
matrix=repmat(mdef,msize);
    while q>0
    matrix(incell{q+2}(1), incell{q+2}(2)) = incell{q+2}(3);
    q = q-1;
    end
    

but failing for random cases help me out...

[Sri Sai Nomula]

function matrix=sparse2matrix(cellvec)
matrix=cellvec{2}*ones(cellvec{1}(1),cellvec{1}(2));
for i=3:size(cellvec,2)
    matrix(cellvec{i}(1),cellvec{i}(2))=cellvec{i}(3);
end
end

[SIVA SAI AKULA]

function indices = saddle(M)
    row_max = max(M,[],2);

    col_min = min(M,[],1);
    
    [row,col]=find((M == row_max).*(M == col_min));
    
    if isempty(col) || isempty(row)
    indices=[]
else

    for i=1:length(row)
        indices(i,:)=[row(i),col(i)];
       
    end
    end
end

[Hicham Satti]

%Hope it will help you!!
function indices = saddle(M)
M;
%[row col] = size(M);
indices=[];
ind_row_col = [];
for i=1:row
    for j=1:col
            if ( M(i,j) >= M(i,:) & M(i,j) <= M(:,j) )
                ind_row_col = [ind_row_col M(i,j)];
                indices = [indices ; i,j];
            end
    end
end

[Ahmet Burhan Baglar]

hello, can I ask why did u use ind_row_col array ?

Actually I used smilar code but I got an error message :( can you pls explain?

I generally got error at if line statement

function indices = saddle(M)
%saddle point is defined as an element whose 
% value is greater than or equal to every element in its row,
% and less than or equal to every element in its column
indices = [];
[row, col] = size(M)
for ii = 1:row
    for jj = 1:col
        if M(ii,jj) >= M(ii,:) && M(ii,jj) <= M(:,jj)
            indices = [indices ; ii,jj];
        end     
    end
end

[KRISH BHANDARI]

@Ahmet Burhan Baglar you are using the wrong logical operator . use single& not doubles .

Answer 1

[Stephen23]

Copying code from the internet is not always a good way to learn best-practice coding: Solving this problem using loops misses using MATLAB's excellent code vectorization abilities. It would be much neater and faster to use bsxfun instead, like this:

function idx = saddle(mat)
row_mx = bsxfun(@ge,mat,max(mat,[],2));
col_mn = bsxfun(@le,mat,min(mat,[],1));
[R,C] = find(row_mx & col_mn);
idx = [R,C];
end

Which gives this:

>> saddle(zeros(5,3))
ans =
   1     1
   2     1
   3     1
   4     1
   5     1
   1     2
   2     2
   3     2
   4     2
   5     2
   1     3
   2     3
   3     3
   4     3
   5     3

[Ravi kumar]

your code is not working,but thanks for the hint.

[Stephen23]

@Ravi kumar: if you provide example data for which it does not work then I could fix my answer.

The original question defines "For the purposes of this problem, a saddle point is defined as an element whose value is greater than or equal to every element in its row, and less than or equal to every element in its column". Lets test it on some random data:

>> mat = randi(9,4,4)
mat =
   4   8   6   7
   4   7   6   2
   5   7   1   4
   7   8   6   6
>> row_mx = bsxfun(@ge,mat,max(mat,[],2));
>> col_mn = bsxfun(@le,mat,min(mat,[],1));
>> [R,C] = find(row_mx & col_mn);
>> idx = [R,C]
idx =
   2   2
   3   2

Can you tell me why this is "not working" ?

[Akshay Padti]

@Stephen It gives wrong result for row vectors.

Above code answer :

>> saddle([1 2 3 4 4 3 2 1])

ans =

1 1 4 5

Expected answer :

>> saddle([1 2 3 4 4 3 2 1])

ans =

1 4

1 5

Corrected code :

function indices = saddle(mat)
[row, ~] = size(mat);
row_mx = bsxfun(@ge, mat, max(mat, [], 2));
col_mn = bsxfun(@le, mat, min(mat, [], 1));
[R, C] = find(row_mx & col_mn);
if row == 1
    indices = [R; C]';
else
    indices = [R, C];
end
end

[Stephen23]

@Akshay Padti: a simpler approach is to just replace the last line with this:

idx = [R(:),C(:)];

For example, using your test data:

saddle([1,2,3,4,4,3,2,1])

ans = 2×2

1 4 1 5

function idx = saddle(mat)
row_mx = bsxfun(@ge,mat,max(mat,[],2));
col_mn = bsxfun(@le,mat,min(mat,[],1));
[R,C] = find(row_mx & col_mn);
idx = [R(:),C(:)];
end

Answer 2

[vaishak p nair]

Write a function called saddle that finds saddle points in the input matrix M. For the purposes of this problem, a saddle point is defined as an element whose value is greater than or equal to every element in its row, and less than or equal to every element in its column. Note that there may be more than one saddle point in M. Return a matrix called indices that has exactly two columns. Each row of indices corresponds to one saddle point with the first element of the row containing the row index of the saddle point and the second element containing the column index. If there is no saddle point in M, then indices is the empty array.

solution :

function indices=saddle(M)
indices=[];
[a b]=size(M);
q=1;
for i=1:a
    for j=1:b
        x=M(i,:);
        y=M(:,j);
        c=M(i,j)>=x;
        d=M(i,j)<=y;
        if ~ismember(0,c) && ~ismember(0,d)
            indices(q,1)=i;
            indices(q,2)=j;
            q=q+1;
        end
    end
end
end

[Travis Ha]

I get everything except for c and d. How does it go through each row and column to find the saddle point? Can you just thoroughly explain how c and d works please?

Answer 3

[Tejas Sabu]

function indices=saddle(M)
[m,n] = size (M);
indices=[];%we want an empty matrix if there r no saddle points
for i=1:m; %going thru all the rows and each element of the row.
    maxi=max(M(i,:));% finding the max of the elements of the specific row.
    for j=1:n;% running thru all the coloumns and each element of the column .
        mini=min(M(:,j));% finding the min of the elements of each column.
        if maxi==mini%checking if the max of a row is same as the min of a column, if yes then 
            indices=[indices;i j];% indices will give null matrix in first column and i and j in the next row 
        end
    end
end

hope this helps...try to understand the code instead of copying.

[Farhan Gony]

can you kindly help to understand why we need to use the null matrix, indices in the 10th line. Why can't we just write :

indices= [i,j];

thank you in advance.

[Rik]

If you do that, what would happen with the next iteration? indices will get overwritten.

[THIERNO AMADOU MOUCTAR BALDE]

working

[Mert Yalcinoz]

i didnt understand completly. when i wrote indices=[ii jj] in my code (i have extracted indices in the first row) it failed while testing row vector. why exactly??

Answer 4

[Konstantinos Sofos]

Dear Muhammad,

You know it's very unfair continuously to ask the forum to solve your exercises/homework. I can understand you because also I was student and I wanted to solve my exercise to proceed but just as a friendly recommendation "Try to understand your exercises!". It's the only way to go one step further without cheating most of all yourself. The code that you posted has been posted before 4 days also to another programming forum Find saddle points in Matlab.

Now to your exercise. Your problem is very simple.

1. Take a piece of white paper and write down a matrix

2. Try to write down an algorithm

3. Write your own function

In my opinion this the way to learn programming. Good luck!

Regards,

[Marcos Mariano]

I am totally agree with Konstantinos Sofos. Look at the forum of your course, you may find the help you need. But I am giving you a hint, try this:

   etc..
  saddle_mat = [ ]; 
for jj = 
  for ii = 
     if ...
        saddle_mat = %add ii jj to the saddle points list as a new row
    end
  end
end

[Muhammad Usman Saleem]

@Marco thank for your hint

[Revant Shah]

@Marco I tried this man, but somehow the code is not working. Its showing an error which says that && operator should be convertible to scalar logical value.

[Jobin Geevarghese Thampi]

what is saddle point?what should be the answer after we execute the code?

Answer 5

[the cyclist]

The reason your code doesn't give your expected result can be summarized by this sentence from the documentation for max: If the maximum value occurs more than once, then max returns the index corresponding to the first occurrence.

I think you were expecting it to return the indices of all the maxima.

[Muhammad Usman Saleem]

@the cyclist thanks for contributions... But i hope the refer link is not solution of my problem?? I am getting 1 1 for mat(5,3)?????

Answer 6

[Jaimin Motavar]

I hope this answer is helpful to you.

function indices = saddle(M)
[m,n]=size(M);
a=[];
for i=1:m
    for j=1:n
        if prod(M(i,j)>=M(i,:))==1 && prod(M(i,j)<=M(:,j))==1
            a=[i,j;a];
        end
    end
end
indices=a;
end

[Faria Sultana]

Hello, I'm learning MATLAB from the very beginning nowadays. So, I didn't understand the approach using prod function. Would you please tell me what is going on inside the built-in function 'prod'?

[Naga]

Prod is the keyword for product. So, here it is going to multiply the elements in that matrix.

Answer 7

[Divya Ratna]

i think anyone should try their own first rather than looking for answers in the community.

my attempt was this.

this passes all the test cases...

function indices = saddle (M)
s = size (M);
indices = [];
    for ii = 1 : s(1)
        maxy = max ( M(ii,:) );
        for jj = 1 : s(2)
            if M(ii,jj) == maxy;
                miny = min (M(:,jj));
                if M(ii,jj) == miny;
                    indices = [indices; ii jj];
                end
             end
        end
    end
end

[Garvit Kukreja]

can you help me with this.

Thankyou

function [indices] = saddle(z)
    [ii jj ]= size(z)
    indices = [];
    for i=1:ii
        
        for j=1:jj
            x(i ,j)= [ z(i,j)] 
        end
        
        [p,q]= max(x(i,:)) %max value in a row. p give  max value, q gives column
       
        
         for k=1:ii
               y(k,q)= [z(k,q)]
         end
         [m,n]= min(y(:,q))   %min value in a row. m give  min value, n gives column
         
         if p==m
         indices = [indices; i q]
         end
             
         
    end 
    
   
end

Answer 8

[Muhammad Qaisar Ali]

another approch

function indices = saddle(Z)
    indices=[];
    for r=1:size((Z),1)     % going through Rows
        for c=1:size((Z),2)     % going through Cols             
             if sum((Z(r,c)>=(Z(r,:))))>=size((Z),2) && sum((Z(r,c)<=(Z(:,c))))>=size((Z),1)   % then saddle point
                 indices=[indices;[r,c]];
             end             
        end  
    end
end

[Avinav Ayushman]

Thanks man, it works and i got the main point also

[Muhammad Qaisar Ali]

I glad that it helped someone.

Answer 9

[SIVA SAI AKULA]

function indices = saddle(M)
    row_max = max(M,[],2);

    col_min = min(M,[],1);
    
    [row,col]=find((M == row_max).*(M == col_min));
    
    if isempty(col) || isempty(row)
        indices=[]
    else
    
        for i=1:length(row)
            indices(i,:)=[row(i),col(i)];
           
        end
    end
end

Answer 10

[Hicham Satti]

%Hope it will help you!!
function indices = saddle(M)
M;
%[row col] = size(M);
indices=[];
ind_row_col = [];
for i=1:row
    for j=1:col
            if ( M(i,j) >= M(i,:) & M(i,j) <= M(:,j) )
                ind_row_col = [ind_row_col M(i,j)];
                indices = [indices ; i,j];
            end
    end
end

[Rik]

Why did you post this? What does it teach? What makes it different from the other solutions in this thread?

[Hicham Satti]

This work is a explicit code using basic tools like if loops and logical tools but most of the other codes are implicit codes using advenced MATLAB tools.

[Jake Armitage]

This is very close to what I was working on. Can you explain the empty array and the use of them in the "if" statement please?

I'm trying to place why the necessary syntax is "x = [x M(a, b)]" and "y = [y ; a,b]".

[Image Analyst]

If you say

x = [x M(a, b)]

then x must exist in advance otherwise it won't know what to concatenate M onto. Even though x is an empty array, that's enough for it to exist and allow stuff to be stitched onto it.

Answer 11

[charu sharma]

You should use two for loops to check for each element of a row and a column. Refer this for much simpler code: http://farzicoders.blogspot.in/2015/08/write-function-called-saddle-that-finds.html

Answer 12

[Jos (10584)]

function out = saddle(M)
[r, c] = ind2sub(size(M), 1:numel(M)) ;
tf = arrayfun(@(r, c) all(M(r, c) >= A(:, c)) && all(M(r, c) <= M(r, :)), r, c)
out = [r(tf) ; c(tf)].'

Answer 13

[MADDINENI REVANTH SAI]

function s = saddle(M) 
[r, c] = size(M);
s = [];
if r > 1 
   cols = min(M); 
else
   cols = M;
end 
if c > 1 
   rows = max(M');    
else
   rows = M;
end
for ii = 1:c
     for jj = 1:r
          ifM(jj,ii) = cols(ii)&&M(jj)==rows(jj)
            s = [s;jj ii];
   end
 end
end

Answer 14

[Shiladittya Debnath]

For Function :

function id = saddle(M)
[a,b]=size(M);
id = zeros(a+b,2);
count = 0;
for i = 1:a
    mah = max(M(i,:));
    [c1,c2] = find(M(i,:) == mah);
    for k = 1:length(c1)
        c1k = c1(k); c2k = c2(k);
        mic = min(M(:,c2k));
        if M(i,c2k)==mic
            count = count+1;
            id(count,:) = [i,c2k];
        end
    end
end
id = id(1:count,:);
end 

Answer 15

[Shiladittya Debnath]

And for Code to Call your Function :

% create an interesting surface
[X,Y] = meshgrid(-15:0.5:10,-10:0.5:10);
Z = (X.^2-Y.^2)';
% find saddle points
indices = saddle(Z)
% plot surface
surf(Z);
hold on
% mark saddle points with red dots in the same figure
for ii = 1:size(indices,1)
    h = scatter3(indices(ii,2),indices(ii,1),Z(indices(ii,1),indices(ii,2)),'red','filled');
    h.SizeData = 120;
end
% adjust viewpoint
view(-115,14);
hold off

Answer 16

[Abdul Quadir Khan]

function indices = saddle(M)
    row_max = max(M,[],2);

    col_min = min(M,[],1);
    
    [row,col]=find((M == row_max).*(M == col_min));
    
    if isempty(col) || isempty(row)
    indices=[]
else

    for i=1:length(row)
        indices(i,:)=[row(i),col(i)];
       
    end
    end
end

Answer 17

[Mohamed El Nageeb]

this is my answer to this problem....it works fine but i feel like I complicated it. any tips for improvement?

function indices = saddle(M)
[r, c] = size(M);
indices=[];

for ii = 1 : r
    for jj = 1 : c
        req=0;
        for k = 1 : c
            if M(ii,jj) >= M(ii,k)
                req = req +1;
            end
        end
        for d = 1 : r
            if M(ii,jj) <= M(d,jj)
                req = req +1;
            end
        end
        if req == (r+c)
            indices = vertcat(indices,[ii,jj]);
        end
    end
end

[Rik]

If you're looking for code improvements: have you read the other solutions in this thread?

If not, why do you think others will read your answer and learn from it?

Answer 18

[VIGNESH B S]

function indices = saddle(Z)
indices1 = [];   %Creating a temporary matrix..
[r c] = size(Z);
for i = 1:r
    row_sum = sum(Z(i,:));   %To obtain the sum of row
    row_max = max(Z(i,:));   %To obtain max of row
    for j = 1:c
        col_sum = sum(Z(:,j));   %To obtain cum of column
        col_min = min(Z(:,j));   %To obtain minimum of column.
        
        if Z(i,j)>=row_max && Z(i,j)<=col_min   %The logic -> matrix element should be greatest in row or more than the sum 
                                                %and also should be least of column.
            
            mat = [i j];%a TEMPORARY to form a matrix with row and column of the saddle element.
            indices1 = [indices1;mat];  %Now we just add it to the empty matrix.
        end
        end
    end

indices = indices1; 
end

Answer 19

[Salim Maharjan]

This code worked for me.

Function:

function indices=saddle(M)
[row,col]=size(M);
indices=[]; % Initializing the saddle points to an empty matrix
for ii=1:row
    for jj=1:col
% Check if the element is greater than or equal to every element in its row
% and return its sum
        A=sum(M(ii,jj)>=M(ii,:));
% Check if the element is less than or equal to every element in its column
% and return its sum
        B=sum(M(ii,jj)<=M(:,jj));
%Provided than an element is saddle point, the following condition must hold
        if isequal(A,col) && isequal(B,row)
            indices=[indices,[ii,jj]]; %Adding the row index and column index of saddle point in matrix indices
        end
    end
end
end

Answer 20

[YUWEI LI]

function s = saddle(M) % Create logical vector that are true for each saddle condition separately minLocs = M <= min(M, [], 1); maxLocs = M >= max(M, [], 2); % Find the indices where both conditions are true! [row, col] = find(minLocs & maxLocs); % If the input is a row vector, row and col returned from the find % function need to be transposed to fit the output format if isrow(M) s = [row', col']; else s = [row, col]; end end

Answer 21

[Yifan He]

function indices = saddle(M)

m = size(M,1);

n = size(M,2);

indices = [];

for i = 1:m

for j = 1:n

if (sum(M(i,j) >= M(i,1:end)) == n) & (sum(M(i,j) <= M(1:end,j)) == m)

indices = [indices;[i,j]];

end

end

end