If we chose a fixed width, we can easily find out how many lines it would take to fit all the words; simply follow a greedy algorithm – if a word can fit in the current line (including the space to the previous word, if any), do so, otherwise put it in a new line. This takes \(O(N)\) time.

It doesn’t seem obvious how to reverse this in order to find the minimum width for the specified number of lines; however we can note that the function of width to number of lines is a monotonic function, that is, if we increase the width, the number of lines can only stay the same or decrease. We can use binary search to “reverse” a monotonic function using only \(O(\log x)\) evaluations of the function, where \(x\) is the size of the domain.

To binary search, we must also choose our domain (lower bound and upper bound of input). The lower bound should be \(\max _i L_i\) as a narrower window will never fit all the words, while the upper bound is \(N - 1 + \sum_i L_i\), as that’s the space required to put all the words in a single line.

The problem is thus solved in \(O(N \log (N \max L) )\).