Binary Search Optimization Problem

Question

Given a two-column table where: the text content of both columns is known, the total table width is fixed, and the column divider can be placed at any position — find the optimal placement of the column divider that minimizes the total height (length) of the table. The table height is determined by the taller of the two columns after text wrapping. Handle corner cases such as a single word whose length exceeds the available cell width.

AceOffer · Accepted Answer

Given a two-column table where: the text content of both columns is known, the total table width is fixed, and the column divider can be placed at any position — find the optimal placement of the column divider that minimizes the total height (length) of the table. The table height is determined by the taller of the two columns after text wrapping. Handle corner cases such as a single word whose length exceeds the available cell width.

Reported follow-ups:
1. What if a single word is longer than the cell width assigned to its column? (when: Candidate solves the base case)
2. If multiple divider positions give the same minimum table height, how do you handle that? (when: Candidate finds the optimal position)
3. How do you prove/justify the monotonicity or unimodal property needed for binary search to work here? (when: Candidate proposes binary search)

**Alternative approaches:** Linear scan (Try every possible divider position and compute table height for each; O(W * (N1 + N2)) where W is total width and N1, N2 are text lengths. Simple to implement but slower than binary/ternary search.); Ternary search (Works cleanly on unimodal functions; slightly more intuitive than binary search when the monotonicity argument is not immediately obvious, but requires verifying the unimodal property.)

Binary Search Optimization Problem

Problem Overview

Follow-up Arc

Approach Trade-offs

Practice

Approach	Notes
Linear scan	Try every possible divider position and compute table height for each; O(W * (N1 + N2)) where W is total width and N1, N2 are text lengths. Simple to implement but slower than binary/ternary search.
Ternary search	Works cleanly on unimodal functions; slightly more intuitive than binary search when the monotonicity argument is not immediately obvious, but requires verifying the unimodal property.