1

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?

homies
  • 89
  • 10
  • Maybe by reusing the original matrix? – mkrieger1 Mar 20 '22 at 15:59
  • @mkrieger1 hey, I tried doing so, however I couldn't really figure out a way as I'm recursing through and the matrix is getting smaller each time, the input is just the matrix list itself, so no pointers or anything like that allowed – homies Mar 20 '22 at 17:17

1 Answers1

0

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

homies
  • 89
  • 10
  • Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Mar 24 '22 at 08:19