How to get all the minimum elements according to its first element of the inside list in a nested list?

Question

Simply put! there is this list say LST = [[12,1],[23,2],[16,3],[12,4],[14,5]] and i want to get all the minimum elements of this list according to its first element of the inside list. So for the above example the answer would be [12,1] and [12,4]. Is there any typical way in python of doing this? Thanking you in advance.

Answer 1

A compact single-pass solution requires sorting the list -- that's technically O(N log N) for an N-long list, but Python's sort is so good, and so many sequences "just happen" to have some embedded order in them (which timsort cleverly exploits to go faster), that sorting-based solutions sometimes have surprisingly good performance in the real world.

Here's a solution requiring 2.6 or better:

import itertools
import operator
f = operator.itemgetter(0)

def minima(lol):
  return list(next(itertools.groupby(sorted(lol, key=f), key=f))[1])

To understand this approach, looking "from the inside, outwards" helps.

f, i.e., operator.itemgetter(0), is a key-function that picks the first item of its argument for ordering purposes -- the very purpose of operator.itemgetter is to easily and compactly build such functions.

sorted(lol, key=f) therefore returns a sorted copy of the list-of-lists lol, ordered by increasing first item. If you omit the key=f the sorted copy will be ordered lexicographically, so it will also be in order of increasing first item, but that acts only as the "primary key" -- items with the same first sub-item will in turn be sorted among them by the values of their second sub-items, and so forth -- while with the key=f you're guaranteed to preserve the original order among items with the same first sub-item. You don't specify which behavior you require (and in your example the two behaviors happen to produce the same result, so we cannot distinguish from that example) which is why I'm carefully detailing both possibilities so you can choose.

itertools.groupby(sorted(lol, key=f), key=f) performs the "grouping" task that is the heart of the operation: it yields groups from the sequence (in this case, the sequence sorted provides) based on the key ordering criteria. That is, a group with all adjacent items producing the same value among themselves when you call f with the item as an argument, then a group with all adjacent item producing a different value from the first group (but same among themselves), and so forth. groupby respect the ordering of the sequence it takes as its argument, which is why we had to sort the lol first (and this behavior of groupby makes it very useful in many cases in which the sequence's ordering does matter).

Each result yielded by groupby is a pair k, g: a key k which is the result of f(i) on each item in the group, an iterator g which yields each item in the group in sequence.

The next built-in (the only bit in this solution which requires Python 2.6) given an iterator produces its next item -- in particular, the first item when called on a fresh, newly made iterator (and, every generator of course is an iterator, as is groupby's result). In earlier Python versions, it would have to be groupby(...).next() (since next was only a method of iterators, not a built-in), which is deprecated since 2.6.

So, summarizing, the result of our next(...) is exactly the pair k, g where k is the minimum (i.e., first after sorting) value for the first sub-item, and g is an iterator for the group's items.

So, with that [1] we pick just the iterator, so we have an iterator yielding just the subitems we want.

Since we want a list, not an iterator (per your specs), the outermost list(...) call completes the job.

Is all of this worth it, performance-wise? Not on the tiny example list you give -- minima is actually slower than either code in @Kenny's answer (of which the first, "two-pass" solution is speedier). I just think it's worth keeping the ideas in mind for the next sequence processing problem you may encounter, where the details of typical inputs may be quite different (longer lists, rarer minima, partial ordering in the input, &c, &c;-).

Answer 2

Two passes:

minval = min(LST)[0]
return [x for x in LST if x[0] == minval]

One pass:

def all_minima(iterable, key=None):
  if key is None: key = id
  hasminvalue = False
  minvalue = None
  minlist = []
  for entry in iterable:
     value = key(entry)
     if not hasminvalue or value < minvalue:
        minvalue = value
        hasminvalue = True
        minlist = [entry]
     elif value == minvalue:
        minlist.append(entry)
  return minlist

from operator import itemgetter
return all_minima(LST, key=itemgetter(0))

Answer 3

m = min(LST, key=operator.itemgetter(0))[0]
print [x for x in LST if x[0] == m]

Answer 4

minval = min(x[0] for x in LST)
result = [x for x in LST if x[0]==minval]