Finding row wise sum of transpose of hv-convex binary matrix

I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m).

e.g. I get {4,3,2,2,1} in the input. It's the row wise sum of the following matrix:

    1 1 1 1
    1 1 1 0
    1 1 0 0
    1 1 0 0
    1 0 0 0

To solve the problem, I have to find the row-wise sum of it's transpose.

i.e. I need to calculate {5,4,2,1}

1 1 1 1 1
1 1 1 1 0
1 1 0 0 0
1 0 0 0 0

Can it be achieved in less than O(n*m)?

A non-increasing sequence of integers is known as a partition. The operation you are describing is known as conjugation. Given a partition $\lambda_1,\ldots,\lambda_n$, you can compute its conjugate $\lambda'_1,\ldots,\lambda'_m$ as follows:

• Initialize a pointer $i$ at $n$.

• Set $\lambda'_1 = i$.

• Advance $i$ backwards until $\lambda_i \geq 2$.

• Set $\lambda'_2 = i$.

• Advance $i$ backwards until $\lambda_i \geq 3$.

• Set $\lambda'_3 = i$.

• ...

• Stop once $i = 1$.

As an example, here is how you apply this algorithm on $4,3,2,2,1$.
$$
\begin{align*}
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
&&&& \uparrow \\
&&&& 5
\end{array} \\\hline
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
&&& \uparrow \\
&&& 4
\end{array} \\\hline
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
& \uparrow \\
& 2
\end{array} \\\hline
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
\uparrow \\
1
\end{array}
\end{align*}
$$
It might happen that at some point $i$ doesn't advance at all. This is what happens if we apply this algorithm on $5,4,2,1$:
$$
\begin{align*}
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
&&& \uparrow \\
&&& 4
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
&& \uparrow \\
&& 3
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
& \uparrow \\
& 2
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
& \uparrow \\
& 2
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
\uparrow \\
1
\end{array}
\end{align*}
$$

StackExchange Computer Science Q#110116, answer score: 4