Find the next available number in a python list

user_1459786 0
Viewed 163

I have a list of integers that represent how many times an item has been used and I need to find the next number in the sequence that has been used the least amount of times (it might not even be in the list)

The amount of items is dynamic, the example uses 9 but that could be. Also, the amount of times it can appear is dynamic too.

We have X items, all of which are allowed to be used y times

Example.

We have 9 items, both of which are allowed to be used 2 times but should be used in order.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2]

the above should return 3 as the next available item

[1, 2, 3, 4, 5]

the above should return 6 as the next available item

[1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9]

the above should return nothing, as there's no more available

I've already got me a function that's checking if the number appears at the max amount of uses

def is_item_available(item_number: int, uses: int, used_items: List):
    """Check if the item is available.
    Args:
        item_number (int): item number to be checked
        uses (int): number of uses allowed
        used_items (list): list of items currently used in a session
    Returns:
        bool: returns True if used item count is less than the uses number
    """
    return used_items.count(item_number) < uses
python
2 Answers

I think this function works, if the numbers are guaranteed to be from 1-9:

def next_item(used_items):
    if (used_items[-1] == 9 and len(used_items) == 18):
        return "nothing"
    elif (used_items[-1] == 9):
        return 1
    else:
        return used_items[-1] + 1
user_137993570

Most optimal solution would be to use a min-heap to store the online data and fetch the top of the heap:

import collections, heapq

lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2]

## Counter will maintain the count of each element in the list
counter = collections.Counter(lst)

## We now create a min-heap with (counter.count, list.val) as elements
heap = [(value, key) for key,value in dict(counter).items()]

## Now fetch the top element from the min-heap. By definition, this would correspond to the minimum list.val with minimum count

smallest_element = heapq.nsmallest(1, heap)

## If the list.val is already been used twice, return "None" else return the list.val 
if smallest_element[0] > 1:
  return None
return smallest_element[1]
user_102084810
Related