Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````@Test public void testFoo() {
int[][] arr = {{1, 0, 0},
{1, 0, 1},
{0, 0, 0}};

System.out.println("COUNT: " + count(arr));
}

int count (int[][] arr) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
count += (mark(arr, i, j) > 1) ? 1 : 0;
}
}
return count;
}

int mark(int[][] arr, int i, int j) {
int count = 0;
if (i >= 0 && j >= 0 && i < arr.length && j < arr[i].length && arr[i][j] == 1) {
count++;
arr[i][j] = -1;
count += mark(arr, i + 1, j);
count += mark(arr, i - 1, j);
count += mark(arr, i, j + 1);
count += mark(arr, i, j - 1);
}
return count;
}``````

Comment hidden because of low score. Click to expand.
0

minor bug in the count method. It only works for squares. I should check for j < arr[i].length, not arr.length

Comment hidden because of low score. Click to expand.
0

Also change count += (mark(arr, i, j) > 1) ? 1 : 0; to check >= 1

Comment hidden because of low score. Click to expand.
2
of 2 vote

Similar questions :

careercup.com/question?id=14428676

In this question, it is considered as 8 connected component.

Comment hidden because of low score. Click to expand.
1
of 3 vote

Idea:
iterate over each element in the matrix and
Do for each element that is 1
if all of its neighbors are 0, count=count+1,
otherwise, overwrite the value in current index by 0 and move to next index in the matrix.

count is the desired result.
Should work in O(n*m) time.

Comment hidden because of low score. Click to expand.
0

do you mean for each element that is 1?
i think we don't need to overwrite the value in the current index by 0. instead of checking all neighbors, we just need to check the left one and the above one.

Comment hidden because of low score. Click to expand.
0

Sorry, I meant for each element that is 1. And yes, If we are scanning from left to right, we just need to check the right and bottom neighbor.

Comment hidden because of low score. Click to expand.
0

You have two votes, but I think there is a bug. Correct me if I am wrong.

In the following case:

0 1 1 0
0 1 0 0

In the first step you ll change the matrix to be
0 0 1 0
0 1 0 0.
and the answer would be 2 for your algorithm, which is not correct.

Is that rite?

Comment hidden because of low score. Click to expand.
0

You are right vincent, here is the modified approach:
iterate over each element in the matrix and
Do for each element that is 1
if none of the neighbors is 2, count=count+1 and overwrite the value in current index by 2
if at least one of the neighbors is 2 , overwrite the value in current index by 2 and move to next index

If we are scanning from left to right we just need to check right and bottom neighbor.

count is the desired result.
Should work in O(n*m) time.

Comment hidden because of low score. Click to expand.
0

e.g.

101
101
111

You'll be counting two groups since the bottom row doesn't get processed until after you've incrememted the count. Or am I missing something?

Comment hidden because of low score. Click to expand.
0

^^ You are right.

For making this to work, we'll have to flip all the 1s in a group when we find the first 1 in a group. A recursive function could be written to keep flipping all the neighbor ones. So,

Do for each element that is 1
--if all of its neighbors are 0, count=count+1,
--otherwise, count=count+1 and call flipbits()

flipbits() would flip all the 1s in a group when we find the first 1 in the group.
flipbits(i,j){
bit(i,j)=0;
if(bit(i+1,j)==1) flipbits(i+1,j);
if(bit(i,j+1)==1) flipbits(i,j+1);
if(bit(i,j-1)==1) flipbits(i,j-1);
if(bit(i-1,j)==1) flipbits(i-1,j);
return;
}

count is the result.

I think it's still O(n*m)

Comment hidden because of low score. Click to expand.
0

I don't understand why we need to flip. why just scan in top-down left-right way and check the upper and left one is 1 or not when it is 1 itself, if it is not, count++. And we can prove it.
Suppose we get the group information of last line already, for every "1" element in the current line, we first check the left one, if it is also 1,then they are in the same group, we do not need to create a new group; then we check the upper one the same way. If they are both 0, then we need to create a new group, so count++.

Comment hidden because of low score. Click to expand.
0

robert.. ur approach will not work for the following case:

1 0 0 1
1 1 1 1

while scanning the first line you will create two groups and count them as 2. While its actually just one group.

Comment hidden because of low score. Click to expand.
0

epic_coder- what is the complexity of flipbits()
both time and space

Comment hidden because of low score. Click to expand.
0

Tomonfire,
The space complexity depends on what approach you use, recursive or iterative. It would be same as the space complexity of BFS.
Time complexity would be O(1) amortized.

Comment hidden because of low score. Click to expand.
0
of 0 vote

diagonal not considered?

in this example:
1 1 0 0
0 0 1 1
0 0 0 0
1 1 1 1

what is the answer? 2 groups? or 3 groups?

Comment hidden because of low score. Click to expand.
0

3

Comment hidden because of low score. Click to expand.
0

sorry，I don't know which 3 is counted here. Could you please explain to me ? Thank you

Comment hidden because of low score. Click to expand.
0

I replaced the 1s above with their group# so you can see why there are 3 groups.

1 1 0 0
0 0 2 2
0 0 0 0
3 3 3 3

Comment hidden because of low score. Click to expand.
0
of 0 vote

What is the question?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Not considering diagonals

``````import numpy as np

a = np.array([ [ 0 , 0, 0, 1 ],
[ 0,  0, 1, 1 ],
[ 1,  0, 0, 1 ],
[ 1,  1,  1, 0 ] ])

v = np.array ([ [ 0 , 0, 0, 0 ],
[ 0,  0, 0, 0 ],
[ 0,  0, 0, 0 ],
[ 0,  0,  0, 0 ] ])

n1 = ( i-1, j )
n2 = ( i, j+1 )
n3 = ( i+1, j )
n4 = ( i, j-1 )

n = [ n1, n2, n3, n4]
for n1 in n:
if ( n1[0] >= 0 and n1[0] <= 3
and n1[1] >=0 and n1[1] <= 3 ):
if v[n1] == 0 and a[n1] == a[i,j]:
v[n1] = 1
l.append(n1)

def process(l):
while ( len(l) > 0 ):
i,j = l.pop()

if __name__ == '__main__':
count=0
l = list()
for i in range(0, 4):
for j in range(0,4):

if v[i,j] == 0:
count = count + 1
process(l)

print count``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

assume we have n adjacent 1. If any of the adjacent 1's are considered as a group, the total number of groups of these n adjacent 1 is (n-1)+...1=n(n-1)/2.

So all we have to do is get the block of 1's from the matrix. A simple method is to iterate over the matrix horizontally and vertically once. If the matrix is m*n, it has O(m*n) complexity.

There should be optimal answers though.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Would the above matrix have 2 groups or 3 groups

Comment hidden because of low score. Click to expand.
0

I think 3.

Comment hidden because of low score. Click to expand.
0

sorry.. i think it should be 5.. 3 horizontal groups 2 vertical groups.

Comment hidden because of low score. Click to expand.
0

it is 3.unless and until stated we shouldn't consider the extremities of columns or rows to check for adjacency.

Comment hidden because of low score. Click to expand.
0

2

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

How many groups does this have? is it one ?

Comment hidden because of low score. Click to expand.
0

1

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the number of groups depends on the definition of group.

If we consider all possible combinations, a grid which is all composed by 1, and has size
m*n (it has many ways to find there grids, one way is find a grid, and then replace all its elements as 0, then find another till all elements are 0.)
And m has [m+(m-1)+...+1=m*(m+1)/2], n has [n+(n-1)+...+1=n*(n+1)/2],
so the number of groups is [m*(m+1)/2] * [n*(n+1)/2].

Comment hidden because of low score. Click to expand.
0
of 0 vote

hi

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use flood-fill algorithm

Comment hidden because of low score. Click to expand.
0
of 0 vote

Should use BFS or DFS search strategy, and once an element is visited, we will mark it as visited. If we encountered a visited node, simply skipping it. Should be done no larger than O(m*n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

It is the "connected component labeling" problem.

Search "Connected Component Labeling" in wikipedia for standard solutions

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution based on sets, without initialization.
Instead boundary conditions of (-1) are given

Starts with an empty list of sets
Runs on lines, check if upper/left neighbor are 1's
when it's a new "1" (no neighbors) -> append a new set with coordinates
when reaching a 1, check upper/left boundaries.
If has both, join sets if needed
otherwise, append to the set of upper or left "1" neighbor.

full code tested in Python

``````M = (1,1,1,0,1),\
(1,1,1,0,1),\
(1,0,0,1,0),\
(0,0,0,1,0),\
(1,1,1,0,0)

countMatrixBlocks(M)

def countMatrixBlocks(M):
printMatrix(M)
allMembers = reduce(lambda a,b: a+b, M)
if any( abs(m) > 1 for m in allMembers):
print "Not a binary matrix"
return

mSets = []
prevLineMembers = [-1]*len(M[0])
for line, members in enumerate(M):
prevMember = -1
for row, member in enumerate(members):
upper = (prevLineMembers[row] == 1)
prev = (prevMember == 1)

if (member == 0):
pass

elif (not upper) and (not prev):
mSets.append( sets.Set([(line, row)]) )

elif (upper and prev):
iPrev = [(line, row-1) in set for set in mSets].index(True)
iUpper = [(line-1, row) in set for set in mSets].index(True)
if (iUpper != iPrev):
mSets[iPrev].union( mSets.pop(iUpper) )

elif upper:
iUpper = [(line-1, row) in set for set in mSets].index(True)

elif prev:
iPrev = [(line, row-1) in set for set in mSets].index(True)

prevMember = member

prevLineMembers = members

print "# of blocks = %d" % (len(mSets))

def printMatrix(M):
for line in M:
print line``````

Comment hidden because of low score. Click to expand.
0

with output such as:
(1, 1, 1, 0, 1)
(1, 1, 1, 0, 1)
(1, 0, 0, 1, 0)
(0, 0, 0, 1, 0)
(1, 1, 1, 0, 0)
# of blocks = 4

Now add 1 in the (2,4) location...
(1, 1, 1, 0, 1)
(1, 1, 1, 1, 1)
(1, 0, 0, 1, 0)
(0, 0, 0, 1, 0)
(1, 1, 1, 0, 0)
# of blocks = 2

Comment hidden because of low score. Click to expand.
0
of 0 vote

A typical BFS problem

``````int adjacent1s (const std::vector< std::vector<int> > & matrix)
{
std::vector< std::vector<bool> > mark;
for (int i = 0; i < matrix.size (); ++i)
{
std::vector<bool> tmp;
for (int j = 0; j < matrix.at (0).size (); ++j)
{
tmp.push_back (false);
}
mark.push_back (tmp);
}

int retVal (0);
std::queue<Cell> q;
for (int i = 0; i < matrix.size (); ++i)
{
for (int j = 0; j < matrix.at (0).size (); ++j)
{
if (! mark.at (i).at (j) && 1 == matrix.at (i).at (j))
{
q.push (Cell (i, j));
while (! q.empty ())
{
Cell current = q.front ();
q.pop ();
mark.at (current.m_x).at (current.m_y) = true;

if (current.m_x + 1 < matrix.size () && ! mark.at (current.m_x + 1).at (current.m_y) && 1 == matrix.at (current.m_x + 1).at (current.m_y))
{
q.push (Cell (current.m_x + 1, current.m_y));
}
if (current.m_x > 0 && ! mark.at (current.m_x - 1).at (current.m_y) && 1 == matrix.at (current.m_x - 1).at (current.m_y))
{
q.push (Cell (current.m_x - 1, current.m_y));
}
if (current.m_y + 1 < matrix.at (0).size () && ! mark.at (current.m_x).at (current.m_y + 1) && 1 == matrix.at (current.m_x).at (current.m_y + 1))
{
q.push (Cell (current.m_x, current.m_y + 1));
}
if (current.m_y > 0 && ! mark.at (current.m_x).at (current.m_y - 1) && 1 == matrix.at (current.m_x).at (current.m_y - 1))
{
q.push (Cell (current.m_x, current.m_y - 1));
}
}
++ retVal;
}
}
}

return retVal;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Each time I encounter a 1, I use BFS to mark all the 1s in this group as -1. That way we can restore the matrix afterwards if needed and also avoid the need for extra memory.

``````static int numGroups(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
int count = 0;
for(int i=0; i<rows; i++) {
for(int j=0; j<cols; j++) {
if(matrix[i][j] == 1) {
count++;
traverse(matrix, i, j);
}
}
}
return count;
}

static void traverse(int[][] matrix, int i, int j) {
if(i<0 || j<0)
return;
if(i>=matrix.length || j>=matrix[0].length)
return;
if(matrix[i][j] != 1)
return;
matrix[i][j] = -1;
traverse(matrix, i-1, j);
traverse(matrix, i+1, j);
traverse(matrix, i, j-1);
traverse(matrix, i, j+1);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

codercareer.blogspot.com/2013/02/no-41-group-of-1s-in-matrix.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Solution{
public int Island(int[][] matrix){
if(matrix == null) return 0;
int row = matrix.length,column = matrix[0].length,res = 0;
if(row*column == 0) return 0;
for(int i = 0 ; i < row ;i++)
for(int j = 0 ; j < column ; j++)
if(matrix[i][j] == 1)
{
res++;
mark(matrix,i,j);
}
return res;
}
public void mark(int[][] matrix, int x , int y){

int row = matrix.length,column = matrix[0].length;
if(x<0 || x>= row || y<0 ||y>=column) return;
if(mark[x][y] == 1) mark[x][y] = 0;
else return;
mark(matrix,x+1,y+1);
mark(matrix,x+1,y-1);
mark(matrix,x-1,y+1);
mark(matrix,x-1,y-1);
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.