CareerCup

There are n*n elements, so you can't possible have a O(n) solution, but O(n*n).

// prints all valid positions in O(n*n) with extra O(n) space.
// If the interviewer just wants a boolean Possible/Impossible, just return true/false
void FindOut(int matrix[1000][1000], int n) {
    int row_zeros[n], col_ones[n], i, j;
    for (i = 0 ; i < n ; i++) {
        row_zeros[i] = col_ones[i] = 0;
        for (j = 0 ; j < n ; j++) {
             row_zeros[i] += matrix[i][j] == 0;
             col_ones[i] += matrix[j][i] == 1;
        }
    }
    for (i = 0 ; i < n ; i++)
        for (j = 0; j < n ; j++)
            if (matrix[i][j] == 1) {
                if (row_zeros[i] == n-1 && col_ones[j] == n)
                     printf("position (%d, %d)\n", i, j);
            } else {
                if (row_zeros[i] == n && col_ones[j] == n-1)
                     printf("position (%d, %d)\n", i, j);
            }
}

Lol .. no there cant be a row with all 0's and column with all 1's in same matrix.. avoid jumping into coding..

equivalent to the celebrity problem

@anup : I understand there are two separate loops for rows and colums...

but, when you are traversing only rows, we have to use two nested loops to traverse each element in each row?

Time Complexity : O( M * N )

Step 1 ) Store sum of each row and each column.
Mark all row/columns with sum 0 or 1 as ZERO or ONE.
If sum is 1, store what index had element 1.

Step 2 ) Iterate through all rows marked ZERO/ONE.

a) If a row is ZERO and a column marked ZERO/ONE exists, Bingo! we have our pair.

b ) If a row is ONE then check if the column corresponding to stored index is marked ZERO/ONE. If yes, we have our pair

keep repeating this process upto last row. if no success, no such row/column exists.

Posting solution on behalf of Abhishek.

Here the idea is to traverse from the bottom to top.

1) consider a[i][j], check if i'th row is zero and j'th column is 1. if yes, return true. Note that we have started from a[n][n];
2) else if a[i][j] ==0
move one column left and check (1).
if a[i][j]==1
move one row up and check(1)..


In this code isrow checks if all the row element are 0's except a[i][j] and iscolumn checks if all the column elements are 1's except a[i][j].

isbooleanmatrix(A,i,j,n)
{
   if(i==0 && j ==0)
   {
       if(isrow && iscoulumn)
           return true;
       else
        {
              printf("Not Present");
              return;
	}
   }
   else
   {
           if(isrow && iscoulumn)
               return true;
          else  
          {
                if(A[i][j] == 0 && j)
                     isbooleanmatrix(A,i,j-1,n);
                else
                     isbooleanmatrix(A,i-1,j,n);
                 if(i)
                      isbooleanmatrix(A,i-1,j,n);
                 else
                      isbooleanmatrix(A,i,j-1,n);
	}
    }
}

for(i=0;i<n;i++)
{
  if(a[i][i]==1 && a[i][n-i-1]==1)
     t[index++]=i;
}
for(i=0;i<index;i++)
{
   flag=0;
   for(j=0;j<n;j++)
   {
      if(a[j][t[i]]!=1) 
      {
           flag=1;
           break;
       }
   }
   if(flag==0)
     return i;
}
return -1;

However, it is still O(n^2) if the matrix is dense with many entries 1.

it is not possible to have simultaneously all the elements of any row zero and also all elments of any one columns as 1...so no such i and j exist together....

Please explain your idea first (or just your idea).
You have to touch every element of the array, O(n^2), so this gives us a lot of room to work with.

Say you have two integer arrays (zero initialized) of size n:
R[i] -> for information on each rows i
C[i] -> for information on each column i

As you are scanning row i from left to right, if you encounter a '1' somewhere but do not encounter it after that point, mark the position in R[i]. If you did not encounter any 1's mark this somehow (e.g., R[i] = -1). If any other case leave R[i] as it is (i.e., 0).

Do the same thing with each column ( mark position of the only 0 you saw in a column in C[i], or if you did not see any 0's, set C[i]=-1).

Now do your check:
If any element of R is > 0, say R[t], then if t's column was all 1's we have a match ... thus check of C[R[t]] = -1. We have a match if so.

If any element of C is > 0, say C[t], then if t's row was all 0's we have a match.. thus check R[C[t]] = -1. We will have a match.

Note, these check only takes O(n) time.
Going through each column and row only takes O(n^2) time.
Thus total O(n^2).

If interviewer expects somtehing that is n^2 without the O , then he/she is a loser.

Everything here is about 2n^2 + O(n). So why bother coming up with fancy/trickery? A systematic solution gives the best case time.

Can't we have two array coloumnSums and rowSums.
Then look for indexes where
(
i coloumnSums value is 0
and
j rowSums value is n-1
and
A[i][j] is 0
) OR (
i coloumnSums value is 1
and
j rowSums value is n
and
A[i][j] is 1
)

Time complexity O(2n)

def magic_row_col_exists(matrix):

    row_size = len(matrix)
    col_size = len(matrix[0])

    # dict to track which row/col is invalid
    invalid_rows = {}
    invalid_cols = {}

    num_zeroes_in_row = [0] * row_size
    num_ones_in_col = [0] * col_size

    # iterate all elements in the matrix
    for i in xrange(0, row_size):
        # if either all rows are invalid or all cols are invalid, return False
        if len(invalid_cols) == col_size or len(invalid_rows) == row_size:
            return False

        for j in xrange(0, col_size):
            if matrix[i][j] == 0:
                num_zeroes_in_row[i] += 1
            else:
                num_ones_in_col[j] +=1

            # mark if this row is invalid
            if j > 1 and num_zeroes_in_row[i] < j:
                invalid_rows[i] = True

            # mark if this col is invalid
            if i > 1 and num_ones_in_col[j] < i:
                invalid_cols[j] = True

    if len(invalid_rows) == row_size or len(invalid_cols) == col_size:
        return False
    else:
        # valid row indices are those which are not in invalid_rows
        valid_row_indices = [ i for i in xrange(0, row_size) if i not in invalid_rows.keys():

        for i in valid_row_indices:
            if num_zeroes_in_row[i] == row_size:
                # if a row containing all zeroes, as long as there is a col that is valid, return True
                if len(invalid_cols) < col_size:
                    return True
            else:
                # if a row contains all zeroes, except 1
                for j in xrange(0, col_size):
                    # look all the values in the column containing 1, they all must contain 1's
                    # if so, return True 
                    if matrix[i][j] == 1 and num_ones_in_col[j] == col_size:
                        return True
        return False

This problem could be simplified to : "find out if a boolean matrix NxN has a row of 0s with O(N) steps". Not possible without having a vector logical operation between rows/columns as a single step.

If you go through two consecutive rows , you will either find a 1 or not. Which is what we have to do here right ?
I mean the matrix will be say :
0 0 0 0
0 0 0 1
0 0 0 1
0 0 0 1

or say

0 1 0
0 1 0
0 1 0

In either case if we check two consecutive rows, then we have our result right?

O(n^2) or O(n) what is the meaning of "n"？

If there is a row with all zeros, then there can't be a column with all 1s.

int row, col;
printf("Enter row number: ");
scanf_s("%d", &row);

printf("\nEnter column number: ");
scanf_s("%d", &col);

if(row > n || col > n)
{
printf("\nIncorrect row/col value!");
}
else
{
int flag = 0;
for(int i = 0; i<n; i++)
{
if(matrix[row-1][i] != 0 && i!=col-1)
{
flag = 1;
break;
}
if(matrix[i][col-1]!=1 && i!=row-1)
{
flag=1;
break;
}
}

if(flag == 0)
{
printf("Row and Column values are correct!!!!!");
}
else
{
printf("Row and Column values are not correct---");
}
}

simple ,
create the array of all 0 in it and "OR" it with all the rows if the result is all zero then such a row exists.
again for column create array of 'n' 1 and "AND" it with all the rows till we find the result as all 1 array or end of column.

1. Traverse the given matrix from top left to bottom right.
2. Keep track of the row. If row has all zeros and only one ambigous elemtent.
Save AMBIGUOUS_ROW[i] = Column Index of ambiguous elem. i is the row index we are conidering.
3. If row is all zeros. Mark AMBIGUOUS_ROW[i] as -2.
If not mark AMBIGUOUS_ROW[i] = -1 to indicate invalid row.
4. Perform the same with all columns marking row indices of all ambiguous elements. However check for 1s now. These are two seperate loops outside each other complexity is still O(n).
// We now have both AMBIGOUS_ROW[] and AMBIGOUS_COL[]
5. Traverse AMBIGUOUS_ROW from 0 to N-1. Each element with index 'i' in this array represents the ith row.
6. If AMBIGOUS_ROW[i] == -1 ignore. // Invalid row
7. If AMBIGOUS_ROW[i] == -2 ignore // All potential matches will be caught while traversing AMBIGUOUS_COL // All 0 row
8. If AMBIGOUS_ROW[i] == Something else, 5 for example, then see AMBIGOUS_COL[i]. If its -2, we have a match, otherwise we dont.
9. Now repeat for cols.
10. Traverse AMBIGUOUS_COL from 0 to N-1. Each element with index 'j' in this array represents the jth column.
11. If AMBIGOUS_COL[j] == -1 ignore.
12. If AMBIGOUS_COL[j] == -2 ignore // All potential matches will be caught while traversing AMBIGUOUS_ROW
13. If AMBIGOUS_COL[j] == Something else, 10 for example, then see AMBIGOUS_ROW[j]. If its -2, we have a match, otherwise we dont.

1. Traverse the given matrix from top left to bottom right.
2. Keep track of the row. If row has all zeros and only one ambiguous element.
Save AMBIGUOUS_ROW[i] = Column Index of ambiguous elem. i is the row index we are considering.
3. If row is all zeros. Mark AMBIGUOUS_ROW[i] as -2.
If not mark AMBIGUOUS_ROW[i] = -1 to indicate invalid row.
4. Perform the same with all columns marking row indices of all ambiguous elements. However check for 1s now. These are two separate loops outside each other complexity is still O(n).
// We now have both AMBIGOUS_ROW[] and AMBIGOUS_COL[]
5. Traverse AMBIGUOUS_ROW from 0 to N-1. Each element with index 'i' in this array represents the ith row.
6. If AMBIGOUS_ROW[i] == -1 ignore. // Invalid row
7. If AMBIGOUS_ROW[i] == -2 ignore // All potential matches will be caught while traversing AMBIGUOUS_COL // All 0 row
8. If AMBIGOUS_ROW[i] == Something else, 5 for example, then see AMBIGOUS_COL[5]. If its -2, we have a match, otherwise we dont.
9. Now repeat for cols.
10. Traverse AMBIGUOUS_COL from 0 to N-1. Each element with index 'j' in this array represents the jth column.
11. If AMBIGOUS_COL[j] == -1 ignore.
12. If AMBIGOUS_COL[j] == -2 ignore // All potential matches will be caught while traversing AMBIGUOUS_ROW
13. If AMBIGOUS_COL[j] == Something else, 10 for example, then see AMBIGOUS_ROW[10]. If its -2, we have a match, otherwise we dont.

Traverse the matrix diagonally.

1) traverse each diagonal element.
2) while traversing, check if a[i-1][j]==0 && a[i][j-1]==1;
3) if (2) satisfies then i and j could be the row and column we are looking for. Traverse the entire column up and down and check if all are ones, then traverse the entire row left and right and check if all are zeros.
4) If still we don't get the row and column , traverse diagonally till the end repeating (2) and (3)