CODEWITHSUNDEEP
algorithmmatrixdata-structurestime-complexity
Eliran Turgeman
Eliran Turgeman

Reputation: 1656

Search first appearence in matrix under time complexity demands

I need to write a psuedo code for an algorithm that gets as an input a matrix (n x m) and outputs the row index of the first appearence of 0

I should describe two algorithms which one of them performs in O(mlogn) and the second one performs in O(m+n)

Special attribute of the matrix :
The matrix consists only of 0 and 1.
Once a zero value is entered all of the same column below that cell needs to be zero aswell.

Example for valid input:

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

The output should be : 1

Edit : I was able to come up with an algorithm with O(mlogn).

Upvotes: 0

Views: 57

Answers (2)

Aadith Menon
Aadith Menon

Reputation: 41

Edit: This answer was for the old question which didn't include the Special attribute of the matrix

I don't think it's possible to come up with an algorithm that performs better than O(mn) in the worst case.

Here is a naive solution that checks each element of the matrix.

def solve(mat, n, m):
   for i in range(1, n):
      for j in range(i, m):
         if mat[i][j] == 0:
            return i

   return -1

In the worst case (eg when there are no 0s in the input matrix):

The outer for loop will run n times and for each iteration, the inner for loop will run m times.

So the total time complexity will be O(m * n)

Upvotes: 0

fjardon
fjardon

Reputation: 7996

1st algorithm O(m*log(n))

Inside a column the values are sorted in descending order. This means you can find the first 0 in O(log(n)) by using a binary-search inside the column.

There are m columns to search. This leads to O(m*log(n)) to search all columns for their first 0. Finding the first 0 among those m results is O(m) which is dominated by the O(m*log(n)) of the previous search.

2nd algorithm O(m+n)

The second algorithm start from the cell at (n,m). For each column, starting from the last, we go up while we are on a cell with a 0. When we hit a 1 we move to the previous column.

i <- n
j <- m
r <- (-1, -1)
while (j >= 0):
  if M(i,j) == 1:
    j <- j-1
    continue
  while (i >= 0 && M(i,j) == 0)
    r <- (i,j)
    i <- i-1

At the end the result is in r or there was no result at all and r = (-1,-1)

Upvotes: 1

Related Questions