CareerCup

Resort to simple graph algorithm. We have a forest and need to find all unique trees.

Solution summary: Memoize "visited" nodes (ie non-zero numbers), these nodes have been added to a graph and need not be observed again. We will traverse the matrix, and upon discovering a non-zero entity, non-visited entity, perform a DFS on it. Because we visit each space exactly once, O(m*n) time, where m * n is size of the matrix. Print as we go along, enforcing only a single pass.

/////////////////////////////////////////////////////////////
CODE:

using namespace std;

void PrintObject(unsigned int** matrix, bool** visited, unsigned& int n_rows, unsigned& int n_cols,
                                     size_t row, size_t col)
{
    cout<<matrix[row][col];
    visited[row][col] = true;
    //look DOWN
    if(row < n_rows - 1 && !visited[row + 1][col] && matrix[row + 1][col] > 0)
    {
       cout<<", ";
       PrintObject(matrix, visited, n_rows, n_cols, row+1, col);
    }
    //look UP
    if(row > 0 && !visited[row-1][col] && matrix[row - 1][col] > 0)
    {
        cout<<", ";
        PrintObject(matrix, visited, n_rows, n_cols, row-1, col);
    }
    //look RIGHT
    if(col < n_cols - 1 && !visited[row][col + 1] && matrix[row][col + 1] > 0)
    {
       cout<<", ";
       PrintObject(matrix, visited, n_rows, n_cols, row, col + 1);
    }
    //look LEFT
    if(col > 0 && !visited[row][col - 1] && matrix[row][col - 1] > 0)
    {
        cout<<", ";
        PrintObject(matrix, visited, n_rows, n_cols, row, col-1);
    }
}
void ProduceObjects(unsigned int** matrix, unsigned int n_rows, unsigned int n_cols)
{
    bool visited [rows][cols] = {0};
    for(size_t r = 0; r < n_rows; r++)
        for(size_t c = 0; c < n_cols; c++)
        {
            //Ignore it
            if(matrix[r][c] == 0)
           {
                continue;
           }
           //Already "added" to an object
           else if (visited[r][c])
               continue;
           else
           {
                cout<<"{";
                PrintObject(matrix, visited, n_rows, n_cols, r, c);
                cout<<"}";
                if(r < n_rows -1 || c < n_cols -1)
                    cout<<",";
           }
        }
      cout<<endl;
}

For further clarification, the matrix was arbitrary, you must be able to handle any input array up to 5000x5000.

Just want a bit more clarification why is {1} a object?

Disjoint sets.

can anyone plz clarify the problem? not clear to me..

This problem is a case of edge-detection. Think of the question like this:

Imagine if the array is a representation of an image. Each 0 represents empty or no detail. Each >0 represents a 'thing' present. 'Things' that share an edge are considered all the same thing. The goal of this exercise is to be able to detect the total number of 'things' in the image. This exercise is similar to 'flood fill' questions

My solution was like Austin's: search every node marking each one as visited and once you encounter a node > 0 perform a DFS on the node while marking each node > 0 as visited. As you perform DFS increment a counter representing the number of unique (arbitrarily shaped) objects you encounter.

public class DetectBio {
    public static void main(String[] args) {
        int[][] image = new int[][] {
                {0,1,0,0,3},
                {0,0,3,0,1},
                {0,1,0,0,2},
                {1,1,1,0,2},
                {0,0,0,0,0}
        };
        boolean [][] visited = new boolean[image.length][image[0].length];
        for(boolean[] visit : visited) {
            Arrays.fill(visit, false);
        }
        int totalBios = processMatrix(image, visited, 0, 0);
        System.out.println("Detected: " + totalBios);
    }
    private static int processMatrix(int[][] image, boolean[][] visited, int y, int x) {
        int totalDFS = 0;
        if(visited[y][x])
            return totalDFS;
        if(image[y][x] > 0) {
            //If we're here, DFS
            totalDFS++;
            processBio(image, visited, y, x);
        }
        visited[y][x] = true;

        if(y + 1 < image.length) {//Down
            totalDFS += processMatrix(image, visited, y + 1, x);
        }
        if(x + 1 < image[y].length) {//Right
            totalDFS += processMatrix(image, visited, y, x + 1);
        }
        if(x + 1 < image[y].length && y + 1 < image.length) {//Diagonal
            totalDFS += processMatrix(image, visited, y+1, x+1);
        }
        return totalDFS;
    }
    private static void processBio(int[][] image, boolean[][] visited, int y, int x) {
        if(visited[y][x])
            return;
        visited[y][x] = true;

        if(image[y][x] > 0) {
            if(x + 1 < image[y].length) {
                processBio(image, visited, y, x + 1);
            }
            if(x - 1 > 0) {
                processBio(image, visited, y, x - 1);
            }
            if(y + 1 < image.length) {
                processBio(image, visited, y + 1, x);
            }
            if(y - 1 > 0) {
                processBio(image, visited, y - 1, x);
            }

        }
    }
}

I decided to go through each element, and count it if it has a value and check the top and left of that element has a value. If the top and left has a value, and the current element has a value, skip it. If the top and left don't have a value, count it.

Here is what I have in C++:

#include <iostream>
#include <math.h>
using namespace std;

void printArray(int array[][5], int width, int height)
{
    
    for(int i=0; i<5; i++)
    {
        for(int j=0; j<5; j++)
        {
            cout << "[" << array[i][j] << "]";
        }
        cout << endl;
    }
    cout << endl;
}

int main(int argc, const char * argv[])
{
    // original image
    int image[5][5] = {
        {0, 1, 0, 0, 3},
        {0, 3, 3, 0, 0},
        {0, 0, 0, 0, 2},
        {0, 0, 1, 0, 2},
        {0, 0, 0, 0, 0},
    };
    printArray(image, 5, 5);

    // process
    int counter = 0;
    for(int i=0; i<5; i++)
    {
        for(int j=0; j<5; j++)
        {
            // correct the value in the image to 1
            if (image[i][j] > 0) image[i][j] = 1;
            int image_value = image[i][j];
            
            // get coordinates of the neighbors
            int top_value = ((i >= 0) && (j-1 >= 0)) ? image[i][j-1] : 0;
            int left_value = ((i-1 >= 0) && (j >= 0)) ? image[i-1][j] : 0;
            
            // calculate neighbor limits
            bool previouslyCounted = ((top_value + left_value) > 0);
            if ((image_value > 0) && (!previouslyCounted))
                counter++;
        }
    }
    
    // output
    printArray(image, 5, 5);
    cout << endl << "Number of Objects: " << counter << endl;
}

Here is my output

[0][1][0][0][3]
[0][3][3][0][0]
[0][0][0][0][2]
[0][0][1][0][2]
[0][0][0][0][0]

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


Number of Objects: 4

Here's my solution in C#. For each entry in the array, it recursively explores to the right and below the cell until it each component of the object has been visited. A set of visited cells is maintained for efficiency and so that subset objects are not counted twice.

/// <summary>
        ///  Given a multidimensional array like below
        ///  0 1 0 0 3
        ///  0 3 3 0 0
        ///  0 0 0 0 2 
        ///  0 0 1 0 2
        ///  0 0 0 0 0 
        /// "objects are considered groups of numbers that touch along top, left, right, or bottom edges. Find the 
        /// number of objects. ie cardinality of {{1,3,3}, {3}, {1}, {2,2}}
        /// </summary>
        /// <returns></returns>
        public static int getGroups (int[,] numbers)
        {
            HashSet<List<int>>  objects = new HashSet<List<int>>();
            HashSet<int> visited = new HashSet<int>();
            List<int> currentObject = new List<int>();
            int rowLength = numbers.GetLength(0);
            int colLength = numbers.Length / rowLength;

            for (int i = 0; i < rowLength; i++)
            { 
                for (int j = 0; j < colLength; j++ )
                {
                    visit(numbers, ref currentObject, ref visited, i, j);
                    if (currentObject.Count > 0)
                    {
                        objects.Add(new List<int>(currentObject));
                        currentObject.Clear();
                    }
                }
                }

            return objects.Count;
        }

        public static void visit (int[,] arr, ref List<int> obj, ref HashSet<int> visited,  int i, int j)
        {
            int rowLength = arr.GetLength(0);
            int colLength = arr.Length / rowLength;
      
            //base case - end of object
            if (arr[i, j] == 0 || visited.Contains((rowLength * i)+j))
            {
                return;
            }
            else
            {
                //add this number to the current object & mark array [i, j] as visited
                obj.Add(arr[i, j]);
                visited.Add((rowLength * i) + j);
                
                //explore right
                if (j + 1 < rowLength -1)
                    visit (arr, ref obj, ref visited, i, j + 1);

                //explore down
                if (i + 1 < colLength - 1)
                   visit(arr, ref obj, ref visited, i + 1, j);

                return;
            }
        }

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct coOrdinates
{
    int row;
	int col;
	
    coOrdinates(int i ,int j): row(i) , col(j){}
};

void printRegion(vector<vector<int> >& matrix , int row , int col)
{
	queue<coOrdinates> q;
	q.push(coOrdinates(row,col));
	int i, j;
	
	while(!q.empty())
	{
		i = q.front().row;
		j = q.front().col;

		q.pop();

		if(i >= 0 && i< matrix.size() &&
		   j >= 0 && j< matrix[0].size() &&
		   matrix[i][j] != 0)
		{
			cout<<matrix[i][j]<<" ";
            
            // Marking as visited
			matrix[i][j] = 0;
						
			// Top
			q.push(coOrdinates(i+1 , j  ));
			// bottom
			q.push(coOrdinates(i-1 , j  ));
			// Right
			q.push(coOrdinates(i   , j+1));
			// left
			q.push(coOrdinates(i   , j-1));
		}
	}	
}

void printRegions(vector<vector<int> >& matrix)
{
    for(int i = 0 ; i < matrix.size() ; ++i)
	{
		for(int j = 0 ; j < matrix[0].size() ; ++j)
		{	
			if(matrix[i][j] != 0)
			{
                cout<<"{ ";
				printRegion(matrix , i , j);
                cout<<"} ";
			}
		}
	}
}

int main()
{
	vector<vector<int> >  matrix = {{0, 1, 0, 0, 3},
                                    {0, 3, 3, 0, 0},
                                    {0, 0, 0, 0, 2},
                                    {0, 0, 1, 0, 2},
                                    {0, 0, 0, 0, 0}};
	
    printRegions(matrix);
	
}

Here's another one in Java. Very similar to what other's have said:
pseudo code:

for each row
    for each column
        if element is not visited and not 0
            make a group
        else
            mark visited
       endif
    endfor
endfor

make a group: row, column
    create a new list and add the value at row,column to it
    mark row,column as visited
    
    append to group with right
    append to group with left
    append to group with down
    append to group with up

// recursively call this method
append to group: group, row, column
    if not visited and if not 0
        add to group
        mark row,column as visited
        append to group with right
        append to group with left
        append to group with down
        append to group with up
    else
        mark row,column as visited

Actual Code:

package com;

import java.util.ArrayList;
import java.util.List;

public class ObjectGroupFinder {

    public static void main(String... args) {
	Integer[][] matrix = new Integer[][] {
		{ 0, 1, 0, 0, 3 },
		{ 0, 3, 3, 0, 0 },
		{ 0, 0, 0, 0, 2 },
		{ 0, 0, 1, 0, 2 },
		{ 0, 0, 0, 0, 0 } };
	List<List<Integer>> listOfListOfItems = new ObjectGroupFinder()
		.findObjectGroups(matrix);
	for (List<Integer> items : listOfListOfItems) {
	    for (Integer item : items) {
		System.out.print(item + ",");
	    }
	    System.out.println("--");
	}

    }

    public List<List<Integer>> findObjectGroups(Integer[][] matrix) {
	int rows = matrix.length;
	int columns = matrix[0].length;
	// maintain marker array to mark the visited elements
	boolean[][] markers = new boolean[rows][columns];
	List<List<Integer>> result = new ArrayList<List<Integer>>();

	for (int row = 0; row < rows; row++) {
	    for (int column = 0; column < columns; column++) {
		int temp = matrix[row][column];
		if (!markers[row][column] && temp != 0) {
		    List<Integer> group = makeGroup(matrix, row, column, rows,
			    columns, markers);
		    result.add(group);
		} else {
		    markers[row][column] = true;
		}
	    }
	}

	return result;
    }

    private List<Integer> makeGroup(Integer[][] matrix, Integer row,
	    Integer column, Integer rows, Integer columns, boolean[][] markers) {
	List<Integer> group = new ArrayList<Integer>();
	group.add(matrix[row][column]);
	markers[row][column] = true;
	// check right index
	if (column < columns - 1)
	    // go right
	    appendToGroup(group, matrix, row, column + 1, rows, columns,
		    markers);
	// check left index
	if (column > 0)
	    // go left
	    appendToGroup(group, matrix, row, column - 1, rows, columns,
		    markers);
	// check down index
	if (row < rows - 1)
	    // go down
	    appendToGroup(group, matrix, row + 1, column, rows, columns,
		    markers);
	// check up index
	if (row > 0)
	    // go up
	    appendToGroup(group, matrix, row - 1, column, rows, columns,
		    markers);

	return group;
    }

    private void appendToGroup(List<Integer> group, Integer[][] matrix,
	    Integer row, Integer column, Integer rows, Integer columns,
	    boolean[][] markers) {
	Integer temp = matrix[row][column];
	if (!markers[row][column] && temp != 0) {
	    group.add(matrix[row][column]);
	    markers[row][column] = true;

	    // check right index
	    if (column < columns - 1)
		// go right
		appendToGroup(group, matrix, row, column + 1, rows, columns,
			markers);
	    // check left index
	    if (column > 0)
		// go left
		appendToGroup(group, matrix, row, column - 1, rows, columns,
			markers);
	    // check down index
	    if (row < rows - 1)
		// go down
		appendToGroup(group, matrix, row + 1, column, rows, columns,
			markers);
	    // check up index
	    if (row > 0)
		// go up
		appendToGroup(group, matrix, row - 1, column, rows, columns,
			markers);
	} else {
	    markers[row][column] = true;
	}

    }
}

Output:

1,3,3,--
3,--
2,2,--
1,--

public static void FindSubGraphs(int[][] input, int rows, int cols)
{
    bool[,] visited = new bool[rows, cols];
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            visited[i, j] = false;

    List<List<Point>> subgraphSet = new List<List<Point>>();
    Queue q = new Queue();
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            if (input[i][j] != 0 && !visited[i, j])
            {
                Point point = new Point(i, j);
                q.Enqueue(point);
            }

            List<Point> subgraph = new List<Point>();
            while (q.Count != 0)
            {
                Point point = (Point)q.Dequeue();
                visited[point.x, point.y] = true;
                subgraph.Add(point);

                if (point.x + 1 < rows && input[point.x + 1][point.y] != 0 && !visited[point.x + 1, point.y])
                {
                    Point point1 = new Point(point.x + 1, point.y);
                    q.Enqueue(point1);
                }
                if (point.x - 1 >= 0 && input[point.x - 1][point.y] != 0 && !visited[point.x - 1, point.y])
                {
                    Point point1 = new Point(point.x - 1, point.y);
                    q.Enqueue(point1);
                }
                if (point.y + 1 < cols && input[point.x][point.y + 1] != 0 && !visited[point.x, point.y + 1])
                {
                    Point point1 = new Point(point.x, point.y + 1);
                    q.Enqueue(point1);
                }
                if (point.y - 1 >= 0 && input[point.x][point.y - 1] != 0 && !visited[point.x, point.y - 1])
                {
                    Point point1 = new Point(point.x, point.y - 1);
                    q.Enqueue(point1);
                }
            }
            if (subgraph.Count != 0)
                subgraphSet.Add(subgraph);
        }
    }
}

#!/usr/local/bin/python2.7
    
print "Hello World!\n";
list1=[[0, 1, 0, 0, 3],
[0, 3, 3, 0, 0],
[0, 0, 0, 0, 2],
[0, 0, 1, 0, 2],
[0, 0, 0, 0, 0]]
list2=[]
for i in range(0,len(list1)):
  for j in range(0,len(list1[i])):
    if list1[i][j]!=0:
      list2+=[[i,j]]
list3=[]
list3+=[[list2[0]]]
del list2[0]
x=0
while len(list2)!=0:
  p=len(list3[x])
  for y in range(0,p):
    for i in range(0,len(list2)):
      try:
        if (list2[i][0]==list3[x][y][0]+1 and list2[i][1]==list3[x][y][1]) or (list2[i][1]==list3[x][y][1]+1 and list2[i][0]==list3[x][y][0]) or (list2[i][0]==list3[x][y][0]-1 and list2[i][1]==list3[x][y][1]) or (list2[i][1]==list3[x][y][1]-1 and list2[i][0]==list3[x][y][0]):
          list3[x]+=[list2[i]]
          del list2[i]
      except:
        continue
  q=len(list3[x])
  if p==q and len(list2)!=0:
    x+=1
    list3+=[[list2[0]]]
    del list2[0]
for i in range(0,len(list3)):
  print ""
  for j in range(0,len(list3[i])):
    print list1[list3[i][j][0]][list3[i][j][1]],

#!/usr/local/bin/python2.7
    
print "Hello World!\n";
list1=[[0, 1, 0, 0, 3],
[0, 3, 3, 0, 0],
[0, 0, 0, 0, 2],
[0, 0, 1, 0, 2],
[0, 0, 0, 0, 0]]
list2=[]
for i in range(0,len(list1)):
  for j in range(0,len(list1[i])):
    if list1[i][j]!=0:
      list2+=[[i,j]]
list3=[]
list3+=[[list2[0]]]
del list2[0]
x=0
while len(list2)!=0:
  p=len(list3[x])
  for y in range(0,p):
    for i in range(0,len(list2)):
      try:
        if (list2[i][0]==list3[x][y][0]+1 and list2[i][1]==list3[x][y][1]) or (list2[i][1]==list3[x][y][1]+1 and list2[i][0]==list3[x][y][0]) or (list2[i][0]==list3[x][y][0]-1 and list2[i][1]==list3[x][y][1]) or (list2[i][1]==list3[x][y][1]-1 and list2[i][0]==list3[x][y][0]):
          list3[x]+=[list2[i]]
          del list2[i]
      except:
        continue
  q=len(list3[x])
  if p==q and len(list2)!=0:
    x+=1
    list3+=[[list2[0]]]
    del list2[0]
for i in range(0,len(list3)):
  print ""
  for j in range(0,len(list3[i])):
    print list1[list3[i][j][0]][list3[i][j][1]],