7

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
oleksii
  • 35,458
  • 16
  • 93
  • 163
Lg102
  • 4,733
  • 3
  • 38
  • 61

7 Answers7

3

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.

thegrinner
  • 11,546
  • 5
  • 41
  • 64
  • what will the running time for this algorithm? – Nitish Upreti Oct 29 '13 at 04:42
  • @Myth17 The not-quite flood fill I posted would be `O(mn)`. I'm not sure for actual flood fill - it would obviously be dependent on the underlying implementation, and there are some clever things that can be done to improve it. – thegrinner Oct 29 '13 at 14:13
2

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;
    }
Jean-Bernard Pellerin
  • 12,556
  • 10
  • 57
  • 79
1

I would use Disjoint sets (connected components).

At the begining, each (i,j) matrix element with value 1 is one element set itself.

Then you can iterate over each matrix element and for each element (i,j) you should join each adjacent position set {(i+1,j),(i-1,j),(i,j+1),(i,j-1)} to (i,j) set if its value is 1.

You can find an implementation of disjoint sets at Disjoint Sets in Python

At the end, the number of diffrent sets is the number of objects.

Pablo Francisco Pérez Hidalgo
  • 27,044
  • 8
  • 36
  • 62
1

I would use a disjoint-set datastructure (otherwise known as union-find).

Briefly: for each connected component, build an "inverse tree" using a single link per element as a "parent" pointer. Following the parent pointers will eventually find the root of the tree, which is used for component identification (as it is the same for every member of the connected component). To merge neighboring components, make the root of one component the parent of the other (which will no longer be a root, as it now has a parent).

Two simple optimizations make this datastructure very efficient. One is, make all root queries "collapse" their paths to point directly to the root -- that way, the next query will only need one step. The other is, always use the "deeper" of the two trees as the new root; this requires a maintaining a "rank" score for each root.

In addition, in order to make evaluating neighbors more efficient, you might consider preprocessing your input on a row-by-row basis. That way, a contiguous segment of 1's on the same row can start life as a single connected component, and you can efficiently scan the segments of the previous row based on your neighbor criterion.

comingstorm
  • 25,557
  • 3
  • 43
  • 67
1

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)
גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
0

Why not just look at all the adjacent cells of a given block? Start at some cell that has a 1 in it, keep track of the cells you have visited before, and keep looking through adjacent cells until you cannot find a 1 anymore. Then move onto cells that you have not looked yet and repeat the process.

masotann
  • 901
  • 10
  • 29
0

Something like this should work:

  1. while array has a 1 that's not marked:
    1. Create a new object
    2. Create a Queue
    3. Add the 1 to the queue
    4. While the queue is not empty:
      1. get the 1 on top of the queue
      2. Mark it
      3. Add it to current object
      4. look for its 4 neighbors
      5. if any of them is a 1 and not marked yet, add it to queue
iluxa
  • 6,941
  • 18
  • 36