I am trying to write a program in python that consumes a list that contains as many inner lists as the length of the outer list. For example,
L = [[-10, -9, 99, 100],
[ -6, -3, 100, 101],
[ -1, 0, 1000, 1010],
[ -1, 10, 10000, 24852]]
and it outputs the smallest positive integer. It outputs -1 is there if all elements are negative or 0. The output for the list above would be 10. The elements are also always sorted in ascending order, so both the rows and the columns are sorted in ascending order. What this means is that if you look at any row or any column, it will be sorted from left-to-right and top-to-bottom, respectively.
The issue is I have to do this in O(n) efficiency (n referring to the length of the outer list) but every solution I come up with involves nested loops and thus the efficiency becomes O(n^2).
How can I achieve this in O(n) efficiency in python?
Edit: I have written the following code which works for some cases but doesn't work for others
def min_positive(L):
i = 0
n = len(L)
j = len(L) - 1
min_pos = L[0][j]
while ( i < n and j >= 0 ):
if (L[i][j] < min_pos and L[i][j] > 0):
min_pos = L[i][j]
if (L[i][j] >= min_pos):
j = j - 1
i = i + 1
if min_pos <= 0:
min_pos = -1
return min_pos
This works for the following list
L = [[-10, -9, 99, 100],
[ -6, -3, 100, 101],
[ -1, 0, 1000, 1010],
[ -1, 10, 10000, 24852]]
but doesn't work for the list
L = [[-10, -9, 99, 100],
[ -6, -3, 100, 101],
[ -1, 0, 1000, 1010],
[ 1, 10, 10000, 24852]]
ie. output should be 1 but it's still 10 Feel like I'm close so any help would be appreciated!
This is a worst case, O(M + N) solution where M is the number of rows and N is the number of columns.
L = [[-10, -9, 99, 100],
[ -6, -3, 100, 101],
[ -1, 0, 1000, 1010],
[ -1, 10, 10000, 24852]]
def get_least_positive(list_of_lists):
minimum = float("inf")
# start from top right
row = 0
column = len(list_of_lists[0]) - 1
# follow the staicase
while row < len(list_of_lists) and column >= 0:
elem = list_of_lists[row][column]
if elem > 0:
minimum = min(minimum, elem)
column -= 1
else: # found Negative, go to next row.
row += 1
return minimum if minimum != float('inf') else -1
print(get_least_positive(L))
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments