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 listtest_list = [[4, 3, 1, 2, 3], [7, 5, 3, 6, 3],             [8, 5, 3, 5, 3], [1, 2, 3, 4, 6]]Â
# printing original listprint("The original list is : " + str(test_list))Â
# initializing check coordi, j = 1, 3Â
# initializing KK = 3Â
# getting nearest coordinatesres_abs, res_ord = near_coord(test_list, i, j, K)Â
# printing resultprint("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, 3output = 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.
