Word Wrap — Solution in Python, Java & C++
Word Wrap solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Microsoft.
Word Wrap is a hard coding problem on arrays and dynamic programming, asked in Amazon, Microsoft and Flipkart interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Microsoft, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A paragraph of n words is to be printed on lines of width k. Word i is nums[i] characters long, the words must stay in their given order, and two words on the same line are separated by exactly one space. Every word fits on a line by itself (nums[i] <= k).
If a line holds words i..j, it uses nums[i] + … + nums[j] + (j - i) characters, and the remaining k minus that are its extra spaces. The cost of a line is the square of its extra spaces — except the last line, which costs nothing.
Choose where to break lines so the total cost is as small as possible, and return that minimum.
Example 1
Input: nums = [3,2,2,5], k = 6
Output: 10
Explanation: Lines [3], [2,2], [5]: the first has 3 extra spaces (cost 9), the second uses 2 + 1 + 2 = 5 characters (cost 1), and the last line is free. Total 10.
Example 2
Input: nums = [3,2,2], k = 4
Output: 5
Explanation: [3] costs 1; [2,2] would need 5 characters, so [2] costs 4; the last [2] is free.
Example 3
Input: nums = [5], k = 5
Output: 0
Explanation: A single line is the last line.
Constraints
1 <= n <= 5001 <= nums[i] <= 1000max(nums) <= k <= 2000
Hints for Word Wrap
Hint 1
Filling each line as much as possible (greedy) is not optimal when the cost is squared — spreading the slack evenly is cheaper.
Hint 2
Decide the first line: it holds words
0..jfor somej. The rest of the paragraph is the same problem starting at wordj + 1.Hint 3
Let
best[i]be the minimum cost to print wordsi..n-1. Try everyjwhile the line still fits; a line that reaches the last word costs0, otherwise(k - len)^2 + best[j + 1].
How to solve Word Wrap
A layout is a sequence of lines, and once the first line is fixed, the rest is an independent smaller paragraph. So define the cost of laying out a suffix of the words, and fill it from the end.
Approach
- Set
best[n] = 0. - For
ifromn - 1down to0: extend a line from wordione word at a time, keeping its lengthlen; stop oncelen > k. - For each end
jthat fits: ifjis the last word the line is free, otherwise it costs(k - len)^2 + best[j + 1]. Keep the minimum asbest[i]. - Return
best[0].
Why it works
Every valid layout of words i..n-1 starts with a line i..j that fits, followed by a valid layout of j+1..n-1; its cost is the first line's cost plus that layout's cost, which is at least best[j + 1]. Trying every feasible j therefore finds the optimum, and the last line is recognised as the one that contains word n - 1.
Complexity
- Time —
O(n^2) (a line holds at mostk / 2words, soO(n * k)too) - Space —
O(n)
Pitfalls
- The last line is free even if it is almost empty — don't charge it.
- Separating spaces count towards the line length:
lengrows bynums[j] + 1per word after the first. - The total stays below
500 * 1999^2 < 2^31, but a careless sentinel likeINT_MAXplus a cost overflows — compare before adding.
Reference solution
Python
from typing import List
def solveWordWrap(nums: List[int], k: int) -> int:
n = len(nums)
best = [0] * (n + 1)
for i in range(n - 1, -1, -1):
top = None
length = -1
for j in range(i, n):
length += nums[j] + 1
if length > k:
break
cost = 0 if j == n - 1 else (k - length) ** 2 + best[j + 1]
if top is None or cost < top:
top = cost
best[i] = top
return best[0]Java
public static int solveWordWrap(int[] nums, int k) {
int n = nums.length;
long[] best = new long[n + 1];
for (int i = n - 1; i >= 0; i--) {
long top = Long.MAX_VALUE;
int len = -1;
for (int j = i; j < n; j++) {
len += nums[j] + 1;
if (len > k) break;
long cost = j == n - 1 ? 0 : (long) (k - len) * (k - len) + best[j + 1];
if (cost < top) top = cost;
}
best[i] = top;
}
return (int) best[0];
}C++
int solveWordWrap(vector<int>& nums, int k) {
int n = nums.size();
vector<long long> best(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
long long top = LLONG_MAX;
int len = -1;
for (int j = i; j < n; j++) {
len += nums[j] + 1;
if (len > k) break;
long long cost = j == n - 1 ? 0 : (long long) (k - len) * (k - len) + best[j + 1];
top = min(top, cost);
}
best[i] = top;
}
return (int) best[0];
}JavaScript
var solveWordWrap = function(nums, k) {
var n = nums.length;
var best = new Array(n + 1).fill(0);
for (var i = n - 1; i >= 0; i--) {
var top = Infinity;
var len = -1;
for (var j = i; j < n; j++) {
len += nums[j] + 1;
if (len > k) break;
var cost = j === n - 1 ? 0 : (k - len) * (k - len) + best[j + 1];
if (cost < top) top = cost;
}
best[i] = top;
}
return best[0];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming