CODEWITHSUNDEEP
c++
cppuser
cppuser

Reputation: 3

time complexity in finding elements

I have sorted two dimensional array both row and columns in non-descending order, let's say

I want to find first occurence and last occurrence of given number by index, this is expected output for search value 20:

Main principles of this program:

I wrote 2 functions to find first and last occurrence of given number but it only works for 1D array so I came up with idea to rewrite each line from 2D array into the 1D vector and call these functions for elements in this vector. What is more with this solution im getting more outputs than i expect because for each launch of the loop im looking for first and last occurrence of given number in each row so with the solution below i will get output like this: `

Unfortunately, it breakes above rules(time complexity and calling function inside function). The way I wanted to do it:

I am hoping that someone will give me tips on how to solve this task in a manner consistent with the principles.

Upvotes: 0

Views: 440

Answers (1)

sparik
sparik

Reputation: 1201

Let's say we have a matrix M with n rows and m columns. Here is how you can find the first occurrence of a number x in O(n+m) time.

Start at the top right corner of the matrix. Set row=1 and col=m (assuming 1-based indexes). On each step of the algorithm, we are considering the submatrix M[row...n][1...col]. That is, the submatrix where (row, col) is the top right corner.

  1. If M[row][col] is equal to x, then we found x, but there may be more xs on the left on the same row. So check all the row to find the first one and terminate the algorithm
  2. If M[row][col] > x, then x is definitely not on the column col, because each column is sorted. So we can eliminate the whole column and continue the search. Set col=col-1 and start from step 1.
  3. Similarly, If M[row][col] < x, then x is cannot be on the row row. So we set row=row+1 and start from step 1.

Also you need to check if (row, col) is in the bounds of the matrix. If it's not, then there is no x in the matrix

The case of last occurrence is symmetrical and I'll leave that as an exercise.

Upvotes: 1

Related Questions