Python Program to find the Next Nearest element in a Matrix

0 0 2 minutes read

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)

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.