Python Program to find the Next Nearest element in a Matrix
Given a matrix, a set of coordinates and an element, the task is to write a python program that can get the coordinates of the elements next occurrence.
Input : test_list = [[4, 3, 1, 2, 3], [7, 5, 3, 6, 3], [8, 5, 3, 5, 3], [1, 2, 3, 4, 6]], i, j = 1, 3, K = 3
Output : (1, 4)
Explanation : After (1, 3), 3 is found at (1, 4)
Input : test_list = [[4, 3, 1, 2, 3], [7, 5, 3, 6, 3], [8, 5, 3, 5, 3], [1, 2, 3, 4, 6]], i, j = 2, 3, K = 3
Output : (2, 4)
Explanation : After (2, 3), 3 is found at (2, 4)
Method : Using loop and enumerate()
In this we start iteration from the required coordinates and check just for the next nearest K inside the rectangle formed from row + 1, col + 1 to N, N coordinate. Returns -1, -1 if not occurrence is found.
Example:
Python3
# get Nearest coord. def near_coord(test_list, x, y, val): for idx, row in enumerate (test_list[x:]): for j, ele in enumerate (row): # checking for value at lower formed rectangle if ele = = val and j > y: return idx + x, j # if no index found return - 1 , - 1 # initializing list test_list = [[ 4 , 3 , 1 , 2 , 3 ], [ 7 , 5 , 3 , 6 , 3 ], [ 8 , 5 , 3 , 5 , 3 ], [ 1 , 2 , 3 , 4 , 6 ]] # printing original list print ( "The original list is : " + str (test_list)) # initializing check coord i, j = 1 , 3 # initializing K K = 3 # getting nearest coordinates res_abs, res_ord = near_coord(test_list, i, j, K) # printing result print ( "Found K index : " + str ((res_abs, res_ord))) |
Output:
The original list is : [[4, 3, 1, 2, 3], [7, 5, 3, 6, 3], [8, 5, 3, 5, 3], [1, 2, 3, 4, 6]]
Found K index : (1, 4)
Time Complexity: O(n*m)
Auxiliary Space: O(k)
Approach#2: Using generator
Algorithm:
1. The function find_next_nearest
takes a matrix test_list
, a starting position (i, j)
, and a value k
as input.
2. It initializes rows
with the number of rows in the matrix and cols
with the number of columns in the matrix.
3. Inside the generator
nested function, it iterates through the matrix rows from i
to rows - 1
, and for each row, iterates through the columns from j + 1
to cols - 1
.
4. For each cell in this range, it checks if the value at that cell is equal to k
. If it is, it yields the coordinates (row, col)
as a tuple.
5. The yielded coordinates are collected into a list named next_nearest
.
6. The function then returns the first element of next_nearest
if it’s not empty (i.e., if a match was found), otherwise, it returns None
.
Python3
def find_next_nearest(matrix, i, j, k): rows = len (matrix) cols = len (matrix[ 0 ]) def generator(): for row in range (i, rows): for col in range (j + 1 , cols): if matrix[row][col] = = k: yield (row, col) next_nearest = list (generator()) return next_nearest[ 0 ] if next_nearest else None test_list = [[ 4 , 3 , 1 , 2 , 3 ], [ 7 , 5 , 3 , 6 , 3 ], [ 8 , 5 , 3 , 5 , 3 ], [ 1 , 2 , 3 , 4 , 6 ]] i, j, k = 1 , 3 , 3 output = find_next_nearest(test_list, i, j, k) print (output) |
(1, 4)
Time Complexity: O((rows – i) * (cols – j – 1)), where rows
is the number of rows in the matrix and cols
is the number of columns in the matrix.
Space complexity: O(rows * cols), where rows
is the number of rows in the matrix and cols
is the number of columns in the matrix.
Contact Us