How to find the minimum positive integer in a list of lists in O(n)?

user_8307171 0
Viewed 571

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!

big-o python
3 Answers

An O(n) idea is to start at the top-right corner, move left when you are on a positive value, and move down otherwise. For a square array, this visits at most 2*n - 1 indices, because the algorithm never backtracks. List subscription is O(1), so we are linear time complexity and constant space complexity.

def min_linear(L):
    n_rows = len(L)
    n_cols = len(L[0])
    row, col = 0, n_cols - 1  # start a the top-right corner
    best = L[-1][-1]  # initialized to the maximum element
    if best <= 0:
        # no positive elements
        return -1
    while col >= 0 and row < n_rows:
        val = L[row][col]
        if val > 0:
            best = min(val, best)
            col -= 1  # move left
        else:
            row += 1  # move down
    return best
user_6740390

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))
user_88226100

I can provide some basic idea:

1.start from bottom right

since it's sorted in both row and column, meaning bottom right is biggest, and if bottom right is negative, then rest of those is negative.

2.make a path walking solution

It means you would like to walk down(descending) until you meet negative, which you then move another direction. Utility the advantage of ascending, you can walk to min pos without checking middle items, because they are obviously larger. By doing so, you can also skip negative value too.

user_115164190
Related