Checking if the mimimum is unique We have a finite poset and its subset $S$.

We can enumerate elements of $S$ using an iterator.

I need to check if there are more than one minimal elements of $S$ (regarding the above poset).

The best thing I came up with is to construct the graph of all elements of $S$ and then check it for minimal elements. But this:


requires to enumerate all elements of $S$ (while I would prefer to interrupt the calculating in the middle as soon as we get $2$ minimal elements);
may use much memory.


Is there a better way (without enumerating all $S$)?
You cannot avoid enumerating all elements. Consider the following two posets, with elements $x,y,z_1,\ldots,z_n$:


$x,y &lt; z_i$ for all $i$.
$x,y &lt; z_i$ for all $i &lt; n$, and $z_n &lt; x,y$.


The first poset has two minima, and second only one. You can only tell the difference by enumerating over all elements.



If there is a unique minimal element $z$, then $z &lt; w$ for all other elements $w$ (since there is a minimal element below any given element). This allows us to use the following constant space algorithm, which assumes that the elements of the poset are $z_1,\ldots,z_n$:


Initialize $t \gets z_1$.
For $i=2,\ldots,n$: if $z_i &lt; t$, let $t \gets z_i$.
Go over all elements again, and verify that $t \leq z_i$ for all of them.


There is a unique minimal element iff the verification succeeds.