Given a matrix with N rows and M columns and a target value X, search for X in the matrix.
Return the position of the first occurrence of X as {row, col}. Return {-1, -1} when the target value is absent from the matrix.
Example 1
Input: mat = [[1, 2, 3], [7, 6, 8], [9, 2, 5]], X = 6
Output: {1, 1}
Explanation: Target value 6 is present at row 1 and column 1.
Example 2
Input: mat = [[3, 4, 5, 0], [2, 9, 8, 7]], X = 10
Output: {-1, -1}
Explanation: Target value 10 is absent from all matrix cells.
Approach
This approach checks every element of the matrix one by one until the target value is found. Since the matrix is unsorted, no rows or columns can be skipped, so a complete scan may be required in the worst case.
Algorithm
Traverse every row using an outer loop, as the matrix is unsorted and any row can contain the target value.
For each row, use an inner loop to traverse all columns, which makes sure every element in the current row is checked.
Compare the current element with the target value, as a match would confirm that the target exists at the current row and column.
If the current element matches the target, return its row and column indices, since the required position has been found.
If the entire matrix is processed without finding a match, return
{-1, -1}, which signifies that the target does not exist in the matrix.
Dry Run
search in a matrix
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to search a target value in a matrix. pair<int, int> searchElement(vector<vector<int>>& mat, int target) { // Traverse every row from top to bottom. for (int row = 0; row < (int)mat.size(); row++) { // Traverse every column from left to right. for (int col = 0; col < (int)mat[row].size(); col++) { // Return position when target value is found. if (mat[row][col] == target) { return {row, col}; } } } // Return not-found position after complete traversal. return {-1, -1}; }};// Driver code.int main() { vector<vector<int>> mat = {{1, 2, 3}, {7, 6, 8}, {9, 2, 5}}; int target = 6; Solution sol; pair<int, int> ans = sol.searchElement(mat, target); cout << "{" << ans.first << ", " << ans.second << "}" << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N × M), worst-case traversal checks every matrix cell once.
Space Complexity: O(1), only loop variables are used.
Interview follow-up Questions
Yes. Without sorted order, every cell may contain the target value.
Be the first to add a comment.