Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Frequently Asked Questions
4.1.
Why is the time complexity of the optimized approach is O(n)?
4.2.
What do we do in the brute-force approach?
4.3.
Can a matrix be allocated using vectors?
5.
Conclusion
Last Updated: Mar 27, 2024

Search in a Row wise and Column wise Sorted Matrix

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog covers a matrix problem. Matrices are among the most important and often asked data structures in programming contests and technical interviews. There are various standard matrix problems and techniques. This blog tackles a coding task that involves 

searching for an element in an m*n matrix and printing its position.

Recommended Topic, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

Ninja has given you a n x n matrix and a number x, determine the position of x in the matrix if it exists. If not, print "Not Found."  Every row and column in the specified matrix is sorted in ascending order. The designed algorithm should have a linear time complexity.

Sample Examples

Example 1

Input

x=36

Output

(2,0)

Explanation

The Element at (2,0) in the matrix is 36.

Example 2

Input

 

x=21

Output

Element Not Found

Explanation

The Element is not present in the matrix.

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. If at the end of the search, the element is not found, print element is not found.

Algorithm

1. Run a nested loop, one for iterating every row and one for iterating every column.

2. Check each index for x and output the index of the element if it is found.

3. If the element cannot be found, print "Element not found".

Implementation

// Program to search an element in row-wise
// and column-wise sorted matrix by brute-force approach
#include <bits/stdc++.h>

using namespace std;

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

  // start traversing through the entire matrix
  for (int i = 0; i < p; i++)
  {
    for (int j = 0; j < p; j++)
      // if element is found return the index
      if (matrix[i][j] == x)
      {
        cout << "(" << i << ", "
             << j << ")"
             << "\n";
        return 1;
      }
  }

  cout << "Element not found\n";
  return 0;
}

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

 

Output

(1,2)

Time Complexity

The time complexity of the above approach is O(n2) as the solution iterates through every row and column of the matrix.

Space Complexity

The program's auxiliary space is O(1) because no additional data structure is involved.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

 

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 ProblemSorted MatrixBook Allocation Problem and Unique Matrix.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem 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!

Previous article
Find the missing and repeating number in an array
Next article
Maximize Subarray Sum of Given Array by Adding X in the Range [L, R] for Q queries
Live masterclass