Finding saddle points in a matrix

gistfile1.rb

arr1 = [[39, 43, 49, 29, 18], [30, 47, 24, 29, 15], [49, 50, 39, 20, 33], [18, 38, 35, 32, 35], [29, 44, 18, 34, 44]]
arr2 = [[50, 27, 36, 43, 39], [36, 14, 35, 40, 19], [20, 33, 48, 32, 40], [41, 40, 15, 22, 19], [21, 24, 24, 31, 18]]
arr3 = [[39, 43, 49, 29, 18], [30, 47, 24, 29, 15], [49, 50, 39, 20, 33], [18, 38, 35, 32, 38], [29, 44, 18, 34, 44]]


# The simple solution: excluding the transpose, is O(3n) ==> O(n).
[arr1, arr2, arr3].each do |matrix|

  saddle_points = []
  
  row_maxs = matrix.map{|row| row.max }
  # if there are tons of columns, forgo the elegance of transpose for something more efficient
  col_mins = matrix.transpose.map{|col| col.min } 
  
  matrix.each_with_index do |row, i|
    row.each_with_index do |value, j|
      saddle_points << [i, j] if value == row_maxs[i] && value == col_mins[j]
    end
  end
  
  puts saddle_points.any? ? saddle_points.to_s : "No saddle points found"

end


# The efficient solution: still O(n), but faster for extremely large matrices.
[arr1, arr2, arr3].each do |matrix|
  
  saddle_points = []
  
  col_mins = [1073741823] * matrix.first.length # assuming 64-bit integers
  
  matrix.each_with_index do |row, i|
    row_max = -1073741824 # assuming 64-bit integers

    row.each_with_index do |value, j|
      if value > row_max
        row_max = value
        # linear search is likely optimal, unless the matrix has tons of saddle points
        saddle_points.reject!{|p_i, p_j| p_i == i }
      end
      
      if value < col_mins[j]
        col_mins[j] = value
        # linear search is likely optimal, unless the matrix has tons of saddle points
        saddle_points.reject!{|p_i, p_j| p_j == j }
      end
      
      if value == row_max && value == col_mins[j]
        saddle_points << [i, j]
      end
    end
  end
  
  puts saddle_points.any? ? saddle_points.to_s : "No saddle points found"

end


# OUTPUT:
#  [[3, 1]]
#  No saddle points found
#  [[3, 1]]