#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'