Word Wrap

Hard
1608.

Word Wrap

Word Wrap is a hard coding problem on arrays and dynamic programming, asked in Amazon, Microsoft and Flipkart interviews.

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 <= 500
  • 1 <= nums[i] <= 1000
  • max(nums) <= k <= 2000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var solveWordWrap = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 500
  • 1 <= nums[i] <= 1000
  • max(nums) <= k <= 2000

Hints for Word Wrap

  1. Hint 1

    Filling each line as much as possible (greedy) is not optimal when the cost is squared — spreading the slack evenly is cheaper.

  2. Hint 2

    Decide the first line: it holds words 0..j for some j. The rest of the paragraph is the same problem starting at word j + 1.

  3. Hint 3

    Let best[i] be the minimum cost to print words i..n-1. Try every j while the line still fits; a line that reaches the last word costs 0, 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

  1. Set best[n] = 0.
  2. For i from n - 1 down to 0: extend a line from word i one word at a time, keeping its length len; stop once len > k.
  3. For each end j that fits: if j is the last word the line is free, otherwise it costs (k - len)^2 + best[j + 1]. Keep the minimum as best[i].
  4. 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 most k / 2 words, so O(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: len grows by nums[j] + 1 per word after the first.
  • The total stays below 500 * 1999^2 < 2^31, but a careless sentinel like INT_MAX plus 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