# Finding blocks in arrays

I was looking over some interview questions, and I stumbled onto this one:

There's an m x n array. A block in the array is denoted by a 1 and a 0 indicates no block. You are supposed to find the number of objects in the array. A object is nothing but a set of blocks that are connected horizontally and/or vertically.

eg

0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0

Answer: There are 2 objects in this array. The L shape object and the object in the last row.

I'm having trouble coming up with an algorithm that would catch a 'u' (as below) shape. How should i approach this?

0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 0

## Answers

This works in C#

static void Main() { int[][] array = { new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 1, 1 }, new int[] { 0, 0, 0, 0 }, new int[] { 0, 1, 1, 0 } }; Console.WriteLine(GetNumber(array)); Console.ReadKey(); } static int GetNumber(int[][] array) { int objects = 0; for (int i = 0; i < array.Length; i++) for (int j = 0; j < array[i].Length; j++) if (ClearObjects(array, i, j)) objects++; return objects; } static bool ClearObjects(int[][] array, int x, int y) { if (x < 0 || y < 0 || x >= array.Length || y >= array[x].Length) return false; if (array[x][y] == 1) { array[x][y] = 0; ClearObjects(array, x - 1, y); ClearObjects(array, x + 1, y); ClearObjects(array, x, y - 1); ClearObjects(array, x, y + 1); return true; } return false; }

One approach would use Flood Fill. The algorithm would be something like this:

for row in block_array: for block in row: if BLOCK IS A ONE and BLOCK NOT VISITED: FLOOD_FILL starting from BLOCK

You'd mark items visited during the flood fill process, and track shapes from there as well.

My two cents (slash) algorithm:

1. List only the 1's. 2. Group (collect connected ones).

In Haskell:

import Data.List (elemIndices, delete) example1 = [[0,1,0,0] ,[0,1,0,0] ,[0,1,1,0] ,[0,0,0,0] ,[0,1,1,0]] example2 = [[0,1,0,1] ,[0,1,0,1] ,[0,1,1,1] ,[0,0,0,0] ,[0,1,1,0]] objects a ws = solve (mapIndexes a) [] where mapIndexes s = concatMap (\(y,xs)-> map (\x->(y,x)) xs) $ zip [0..] (map (elemIndices s) ws) areConnected (y,x) (y',x') = (y == y' && abs (x-x') == 1) || (x == x' && abs (y-y') == 1) solve [] r = r solve (x:xs) r = let r' = solve' xs [x] in solve (foldr delete xs r') (r':r) solve' vs r = let ys = filter (\y -> any (areConnected y) r) vs in if null ys then r else solve' (foldr delete vs ys) (ys ++ r)

Output:

*Main> objects 1 example1 [[(4,2),(4,1)],[(2,2),(2,1),(1,1),(0,1)]] (0.01 secs, 1085360 bytes) *Main> objects 1 example2 [[(4,2),(4,1)],[(0,3),(1,3),(2,3),(2,2),(2,1),(1,1),(0,1)]] (0.01 secs, 1613356 bytes)