Measuring areas in a 2d array — code challenge

Last week I wrote about a problem from a code challenge I did recently. This is the other problem from that challenge.

In the intervening time I got a rejection letter from the firm in question. Oh well.

The second question on the test was more challenging, and I had a tough time tackling it. Often, like with the previous question, you can start with a sort of brute-force method, and then rethink it as you go; with this one I had to sit and think and do some research first.

The Problem

Write a function that, when given an input that is a square matrix of binary values of any size, finds the size of the largest subsquare of “1”s.

What does that mean?

“A square matrix”

So our input data is going to be a matrix, otherwise known as an array of arrays, or a 2-dimensional array. It’s an array where the members are themselves arrays. For example:

[['Apple, Banana', 'Carrot'], ['Allspice', 'Basil', 'Coriander'], ['Allosaurus', 'Brachiosaurus', 'Coloradisaurus']]

The reason this is called a matrix or 2d array is because it acts as a two-dimensional coordinate system. We can imagine each of the subarrays as being rows in a table:

[
  [ 'Apple',       'Banana',         'Carrot'         ],
  [ 'Allspice',    'Basil',          'Coriander'      ],
  [ 'Allosaurus',  'Brachiosaurus',  'Coloradisaurus' ]
]

Think about how you would access, for example, ‘Coriander’ here. It’s at position 3 in array 2 — it’s a coordinate system!

Finally, it’s specified that it’s a “square matrix”, meaning there are n subarrays of length n. Our example is a square matrix, since it has 3 subarrays of length 3.

“of binary values”

Alright, so our input isn’t going to be alphabetical fruits, spices or dinosaurs, but rather binary values. So it might look more like this:

[[1, 0, 1], [1, 1, 0], [1, 1, 1]]

Not as fun.

“of any size”

Our examples have stuck to a single, small size (3x3), but our answer needs to account for anything — 1x1, 3000x3000, anything.

“finds the size of the largest subsquare of ‘1’s.”

If we format our previous example:

[
  [  1, 0, 1  ], 
  [  1, 1, 0  ], 
  [  1, 1, 1  ]
]

You’ll see that in the lower left-hand corner there’s a square of 1s. So the largest subsquare of 1s in this matrix has a size of 2 (2x2). Our function should output “2” when given this matrix as input.

Solving

This one was tough to get an initial handle on. I hadn’t done anything like it before. But once I figured out the principle of the solution, it came together in a very satisfying manner.

You could imagine a brute-forcing method — take the first cell, check the three cells that would make a square with it, if they make a square then check the five squares that would make a square one bigger, etc., and then do this with every cell — but it’s unbearably messy and scales terribly. We are going to have to do SOMETHING along those lines, but it has to be bit cleverer.

In the previous question, linked at the start of this post, the key was that instead of iterating through each item and checking its connections to the other items, we could create a frequency hash and then go through it just once, collecting runs as we go. This solution has a similar vibe.

We’re going to create a second matrix, of the same size as the input. (I’m working in Ruby.)

def largestSubarray(inputMatrix)
  dataSize = inputMatrix.length
  sizeMatrix = Array.new(dataSize){Array.new(dataSize)}
  sizeMatrix
end

That middle line is a concise way to create a square matrix of empty values in Ruby. I didn’t know that before I started working on this problem.

(new example data)

Each cell in sizeMatrix is going to record the size of the subsquare of 1s that ends (i.e. has its bottom-right corner) in that square. So we’re going to make sizeMatrix look like this in the end:

This would be a good time to pause reading and try and find an algorithm to reach that goal.

There are a few things we can notice here about what we care about and how we can get to our goal. Two of them in particular constitute our solution: (I) If we go in order, each cell only needs to check its (-1,0), (0,-1) and (-1,-1) cells to find its own value; and (II) the first row and the first column will necessarily be the same as the input matrix.

Let’s start with (II).

def largestSubarray(inputMatrix)
  dataSize = inputMatrix.length
  sizeMatrix = Array.new(dataSize){Array.new(dataSize)}
  dataSize.times{|i|
    sizeMatrix[i][0] = inputMatrix[i][0]
    sizeMatrix[0][i] = inputMatrix[0][i]
  }
end

Now, all remaining cells can populate according to the following rules:

• If the corresponding inputMatrix cell is a 0, it’s a 0
• Otherwise, look at the (-1,0), (0,-1) and (-1,-1) cells, take the smallest value, and add 1.

The first rule maps all 0s from inputMatrix into 0s in the sizeMatrix, since they are not parts of subsquares.

The second rule (which only applies to inputMatrix 1s) gives a result of 1 (single-cell subsquare) if there are any 0s among the three relative cells, 2 (2x2 subsquare) is there are no 0s but some 1s, 3 (3x3 subsquare) if there are no 0s or 1s but some 2s, etc.

def largestSubarray(inputMatrix)
  dataSize = inputMatrix.length
  sizeMatrix = Array.new(dataSize){Array.new(dataSize)}
  dataSize.times{|i|
    sizeMatrix[i][0] = samples[i][0]
    sizeMatrix[0][i] = samples[0][i]
  }
  inputMatrix.each.with_index{|row, rowindex|
    row.each.with_index{|cell, cellindex|
      if (cellindex != 0 && rowindex != 0)
        cell == 1 ? sizeMatrix[rowindex][cellindex] = [sizeMatrix[rowindex][cellindex - 1], sizeMatrix[rowindex-1][cellindex], sizeMatrix[rowindex-1][cellindex-1]].min + 1 : sizeMatrix[rowindex][cellindex] = 0
      end
    }
  }
end

And there’s our algorithm. Now we just have to return the answer.

Solution

def largestSubarray(inputMatrix)
  dataSize = inputMatrix.length
  sizeMatrix = Array.new(dataSize){Array.new(dataSize)}
  ans = 0
  dataSize.times{|i|
    sizeMatrix[i][0] = samples[i][0]
    sizeMatrix[0][i] = samples[0][i]
  }
  inputMatrix.each.with_index{|row, rowindex|
    row.each.with_index{|cell, cellindex|
      if (cellindex != 0 && rowindex != 0)
        cell == 1 ? sizeMatrix[rowindex][cellindex] = [sizeMatrix[rowindex][cellindex - 1], sizeMatrix[rowindex-1][cellindex], sizeMatrix[rowindex-1][cellindex-1]].min + 1 : sizeMatrix[rowindex][cellindex] = 0
      end
      ans = [sizeMatrix[rowindex][cellindex], ans].max
    }
  }
  ans
end

Please let me know in the comments if you can come up with any improvements.