Search in a Row wise and Column wise Sorted Matrix

Optimized Approach

To locate the element, a better way is to use Divide and Conquer. In each comparison, we begin by eliminating a row or column in each comparison until an element is discovered. We should begin our search from the top-right corner of the matrix.

Algorithm

1. Say the provided element is x, then define two variables i = 0 and j = n-1 as row and column indexes.

2. Run a loop until we get i=n.

3. If the current element is more than x, reduce the count of j and Remove the current column.

4. If the current element is smaller than x, increment the count of i and remove the current row.

5. If the element is equal, print the position of the element.

Implementation

// Program to search an element in a
// sorted matrix by divide and conquer method
#include <bits/stdc++.h>

using namespace std;

int optimizedSearch(int matrix[3][3], int n, int x)
{
  if (n == 0)
    return -1;

  int s = matrix[0][0], l = matrix[n - 1][n - 1];
  if (x < s || x > l)
    return -1;

  // set index for top right element in the matrix
  int i = 0, j = n - 1;
  while (i < n && j >= 0)
  {
    if (matrix[i][j] == x)
    {
      cout << "("
           << i << "," << j << ")";
      return 1;
    }
    if (matrix[i][j] > x)
      j--;


    // Check if matrix[i][j] < x
    else
      i++;
  }

  cout << "Not found";
  return 0;
}

// Driver code
int main()
{
  int matrix[3][3] = {{10, 14, 18},
                      {22, 26, 30},
                      {34, 38, 42}};

  optimizedSearch(matrix, 3, 30);
  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

(1,2)

Time Complexity

The time complexity of the optimized approach will be O(n). Since only one traversal is required, i can go from 0 to n and j can go from n - 1 to 0 in at most 2*n steps, where n x n is the size of the matrix.

Space Complexity

The program's auxiliary space is O(1) because no additional space is required.

Frequently Asked Questions

Why is the time complexity of the optimized approach is O(n)?

Since only one traversal is required, i can go from 0 to n and j can go from n-1 to 0 in at most 2*n steps,  hence time complexity is O(n).

What do we do in the brute-force approach?

The approach is to run two nested loops, one iterates through rows and the other through the columns of the matrix. Check each element of the matrix for the enquired element and if found return the index of the element

Can a matrix be allocated using vectors?

Yes, a 2-d matrix can be allocated using a vector of vectors.

Conclusion

This article extensively discussed the problem of searching for an element in a row-wise and column-wise sorted 2-D matrix and returning its position and its time and space complexities.

We hope this blog has helped you enhance your knowledge regarding matrices. After reading about the matrices, are you not feeling excited to read/explore more articles on this topic? Don't worry, Coding Ninjas has you covered. To learn, Reset Matrix Problem, Sorted Matrix, Book Allocation Problem and Unique Matrix.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and much more! If you want to test your competency in coding, you may check out the mock test series and take part in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you can also look at the problems, interview experiences, and interview bundle for placement preparations.

Also, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!