Searching for an element in a sorted matrix can be challenging, especially as the matrix grows in size. This article aims to provide a comprehensive analysis of various methods to locate an integer XXX in a given N×NN \times NN×N matrix, where both rows and columns are sorted in ascending order. We will explore different approaches, their time complexities, and provide example implementations in various programming languages.
Understanding the Problem Statement
Given an N×NN \times NN×N matrix:
makefile
mat = {
{10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}
}
If we want to find the position of an integer XXX in this matrix, we will examine two primary approaches: a naive method that checks every element and a more efficient method that utilizes the properties of the sorted matrix.
Example Inputs and Outputs
- Input:
- mat[4][4]mat[4][4]mat[4][4]
- X=29X = 29X=29
- Output: Found at (2, 1)
- Input:
- mat[4][4]mat[4][4]mat[4][4]
- X=100X = 100X=100
- Output: Element not found
Approaches to Search in a Row-Wise and Column-Wise Sorted Matrix
Naive Approach: Traversing the Complete Matrix
The naive method involves iterating through each element in the matrix. This straightforward approach is simple but inefficient for larger matrices.
Time Complexity
- Time: O(N2)O(N^2)O(N2)
- Space: O(1)O(1)O(1)
Implementation in Various Languages
C++ Implementation:
cpp
#include <bits/stdc++.h>
using namespace std;
int search(int mat[4][4], int n, int x) {
if (n == 0) return -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == x) {
cout << “Element found at (” << i << “, ” << j << “)\n”;
return 1;
}
}
}
cout << “Element not found”;
return 0;
}
int main() {
int mat[4][4] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50} };
search(mat, 4, 29);
return 0;
}
Python Implementation:
python
def search(mat, n, x):
if n == 0:
return -1
for i in range(n):
for j in range(n):
if mat[i][j] == x:
print(f”Element found at ({i}, {j})”)
return 1
print(“Element not found”)
return 0
if __name__ == “__main__”:
mat = [[10, 20, 30, 40], [15, 25, 35, 45], [27, 29, 37, 48], [32, 33, 39, 50]]
search(mat, 4, 29)
Expected Approach: Optimized Search
A more efficient method involves starting from the top-right corner of the matrix. Based on the comparison between the target value and the current element, we can eliminate either a row or a column.
Steps:
- Start at the top-right corner of the matrix.
- If the current element is equal to XXX, return its position.
- If the current element is greater than XXX, move left (eliminate the current column).
- If the current element is less than XXX, move down (eliminate the current row).
Time Complexity
- Time: O(N)O(N)O(N)
- Space: O(1)O(1)O(1)
Implementation in Various Languages
C++ Implementation:
cpp
#include <bits/stdc++.h>
using namespace std;
int search(int mat[4][4], int n, int x) {
if (n == 0) return -1;
int i = 0, j = n – 1;
while (i < n && j >= 0) {
if (mat[i][j] == x) {
cout << “Element found at (” << i << “, ” << j << “)”;
return 1;
}
if (mat[i][j] > x) j–;
else i++;
}
cout << “Element not found”;
return 0;
}
int main() {
int mat[4][4] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50} };
search(mat, 4, 29);
return 0;
}
Python Implementation:
python
def search(mat, n, x):
if n == 0:
return -1
i, j = 0, n – 1
while i < n and j >= 0:
if mat[i][j] == x:
print(f”Element found at ({i}, {j})”)
return 1
if mat[i][j] > x:
j -= 1
else:
i += 1
print(“Element not found”)
return 0
if __name__ == “__main__”:
mat = [[10, 20, 30, 40], [15, 25, 35, 45], [27, 29, 37, 48], [32, 33, 39, 50]]
search(mat, 4, 29)
Conclusion
Searching for an element in a row-wise and column-wise sorted matrix can be efficiently accomplished using the optimized approach, significantly reducing time complexity. This method not only improves performance but also simplifies the code structure, making it easier to implement across various programming languages.
Also Read:
Fantasy Team Name Generator Football
Interpersonal vs Intrapersonal
Override CSS Style in PrimeVue
Directed Graph in Python LeetCode
Dropdown from a Search Bar in Vue
JavaScript Map of the Keys Method
2 thoughts on “Efficient Search in a Row-Wise and Column-Wise Sorted Matrix”