#Ruby, Leetcode, Challenge π¬π§
[Leetcode] Find sqare matrix
Dario Chuquilla
Dario Chuquilla
3 min read
This is the first in a series of articles about leetcode exercises, expect a new one every week.
I wrote this article to help new programmers find and memorize a solution.
I wrote this article to help new programmers find and memorize a solution.
To find a maximum identity square matrix of size `n*n` within a binary square matrix `N*N`, the method should return `n` indicating the size of the maximum identity matrix.
1st Iteration
Keep in mind that both N*N and n*n are quadratic matrices, I tried to go the route of working with diagonals that only have 1s, since the maximum diagonal is N, but this does not ensure that the matrix of said diagonal is complete with 1s .
2nd Iteration
I also thought about the option of flattening the matrix and generating a complicated process of indexes until I found something that would fit.
Solution
Finally, I googled the case and found a process that generates a suitable solution.
For the moment I am not going to go into the issue of how he arrived at that solution.
Flow
Below I present the flow that follows to implement the solution.
- Create an N+1 * N+1 matrix
- Fill the first row and first column with 0
- Take the elements of the N*N Matrix one by one row by row from left to right from top to bottom.
- For each element n: compare the left, left diagonal, and top cells to determine the smallest of the 3, which I will call n'.
- Add n' with the current element n in the analysis.
- Repeat 4 and 5 with all the elements.
- Obtain the maximum n' that will be the searched value.
Implement
The following code written in Ruby language shows how to iterate the elements of the array, obtain the equivalent value in each element, and capture the maximum value.
class SquareMatrix
attr_reader :matrix
def initialize(matrix)
@matrix = matrix
end
def find_square_matrix
return 0 if @matrix.empty?
row = @matrix.size
col = @matrix[0].size
max = 0
(0...row).each do |i|
(0...col).each do |j|
next if @matrix[i][j].zero?
if i.positive? && j.positive?
@matrix[i][j] = 1 + min_value(i, j)
end
max = @matrix[i][j] if @matrix[i][j] > max
end
end
max
end
private
def min_value(i, j)
[@matrix[i - 1][j], @matrix[i][j - 1], @matrix[i - 1][j - 1]].min
end
end
min_value, es el mΓ©todo para obtener el valor de 'm'
max es el valor de 'n', dato que @matrix[i][j] if @matrix[i][j] > max es el valor de n'