CODEWITHSUNDEEP
c++algorithmmatrix
Andre Ahmed
Andre Ahmed

Reputation: 1891

Binary search in 2D Matrix

This is not a homework, it's an interview question that I have read in a website with no answers. I'm just verifying my solution.

Question:

Given a Matrix with 0′s and 1′s in sorted order. design an algorithm to return row index with maximum number of 1′s. after that he modified the question that some rows are sorted in increasing order and some in decreasing order.

I'm thinking of applying a binary search for each row, that would result in O(Rows*LogRows), but for the counting of the ones, that would result again in another iteration, I'm thinking of reducing that timing, to add the ones that I'm iterating to a hash map, or a dictionary, then after saving the numbers of ones, I iterate again to look for the maximum rows.

Is there a faster solution in terms of complexity, or a flaw in my approach ?

Upvotes: 1

Views: 779

Answers (1)

amit
amit

Reputation: 178471

Why do you need to count the ones once you get the index of the first one (ascending) or first zero (descending)? Figuring out if a row is descending sorted or ascending can be done in a single op - compare the first and last element.

High-level pseudo code:

maxRow <- -1
maxOnes <- -infinity
For each row:
  check if row is ascending or descending
  do a binary search for the first 0 (if descending) or first 1 (if ascending)
  use the above calculated index, and the length of the row to find number of ones in this row
  if number of ones is more than maxOnes:
     modify maxRow and maxOnes with the values of this line
return maxRow

This is done in O(#rows*log{size(row)})

Upvotes: 2

Related Questions