Let $s_1,\dots ,s_n$ be the input sequence of bins and $s_i\le m$ for $i=1,\dots ,n$. The $k$ leftmost bins can be put into the next $k$ bins in some order if and only if $2k\le n$ and there exists a permutation $p$ of the numbers $1,\dots ,k$, such that

$${\displaystyle s_i<s_{k+p(i)}\text{ for }i=1,\dots ,k(1)}$$

The solution to the problem is the largest $k$ satisfying condition (1). Assume that $k$ is a solution and $p$ is a permutation satisfying condition (1). Let

• $x=max(s_1,\dots ,s_k)$ and $x=s_i$
• $y=max(s_{k+1},\dots ,s_{k+k})$ and $y=s_{k+j}$

It is obvious that $x<y$. Assume that $p(i)=k+jj$ and $p(ii)=k+j$. Then

$${\displaystyle s_i<s_{k+jj}\le s_{k+j}}$$ $${\displaystyle s_{ii}\le s_i<s_{k+jj}}$$

Therefore we can modify the permutation $p$ such that $p(i)=j$ and $p(ii)=jj$, and the modified $p$ also satisfies condition (1). Let $L(x)$ be the number of bins of size $x$ in the first $k$ bins, and $R(x)$ be the number of bins of size $x$ in the next $k$ bins, that is

$${\displaystyle \begin{array}{rlr}L(x)& =|\{i:1\le i\le k,s_i=x\}|& x=1,\dots ,m\\ R(x)& =|\{j:k+1\le j\le 2k,s_j=x\}|& x=1,\dots ,m\end{array}}$$

Define $R(m+1)=0$ and $D(m+1)=0$ and

$${\displaystyle D(x)=D(x+1)+R(x+1)-L(x)x=m,\dots ,1}$$

Now we can state that the $k$ leftmost bins can be put into the next $k$ bins in some order if and only if condition (2) holds.

$${\displaystyle D(x)\ge 0x=m,\dots ,1(2)}$$

Values of $L(x)$ and $R(x)$ can be computed in $\mathrm{\Theta }(n)$ running time and then checking for the condition (2) takes $\mathcal{O}(m)$ time. Therefore for a given value of $k$ we can check whether $k$ is a solution in $\mathcal{O}(mn)$ time. Moreover, if we already computed the values of $L$ and $R$ for a given $k$ then for $k-1$ we have to modify $L(k)$, $R(k)$, $R(2k)$ and $R(2k-1)$ only. As a consequence, we obtain an $\mathcal{O}(mn)$ worst case running time algorithm. The required memory is $\mathrm{\Theta }(m+n)$.

We can speed up a bit by recomputing only those $D(x)$ that might be changed by decreasing the value of $k$.