pythonlistmatrixminima

Finding local minima in 2D array, in O(N) time


Given an NxN matrix where all numbers are unique, find ANY local minima in O(N) time. Here is an example of the matrix. It's given in

lst = [[30,100,20,19,18],
       [29,101,21,104,17],
       [28,102,22,105,16],
       [27,103,23,106,15],
       [26,25,24,107,14]]

enter image description here

So the way to solve it in O(N) time is to essentially split the list into 4 sections ("windows"), find the smallest element in the green (middle row & column) and compare it with the next "neighboring" smallest value. If not smaller than it's neighbor, recurse to either top left, top right, bottom left, bottom right, depending on which position that smaller than mid_smallest is in.

(slide 20) https://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

I have everything written out so far, but I'm really really struggling to find a way to recurse through one of the 4 sections: Here's the pseudocode: enter image description here

The portion I'm having a difficulty with is the recursion part ex: Find_find_minimum(Top-left_sub_matrix)

How can I recurse through the top left/right or bottom left/right matrix without creating another matrix?


Solution

  • Solved it. I modularized my function with different inputs as indicators.