Log inSign up
hardGeeksforGeeksNot Started

Word Wrap

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of integers nums where nums[i] represents the length of the ith word. You are also given a maximum line width k.

You need to arrange these words into multiple lines such that each line has at most k characters including spaces between words (each word separated by exactly 1 space).

The cost of a line is defined as the square of the number of extra spaces at the end of the line (i.e. extraSpaces^2). However, the last line does not incur any cost.

Find the minimum total cost to wrap all words.

### Example 1 - Input: nums = [3, 2, 2, 5], k = 6 - Output: 10 - Explanation: - Line 1: Word 0 (3) -> extra spaces = 6 - 3 = 3, cost = 3^2 = 9. - Line 2: Word 1 (2) and Word 2 (2) -> length = 2 + 1 + 2 = 5, extra spaces = 6 - 5 = 1, cost = 1^2 = 1. - Line 3: Word 3 (5) -> Last line, cost = 0. - Total cost = 9 + 1 + 0 = 10.

### Example 2 - Input: nums = [3, 2, 2], k = 4 - Output: 5

Constraints:

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= k <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model line-breaking and text formatting as partition DP.
  • Correctly handle the last line zero-cost exception.
  • Implement backward 1D tabulation in O(n2) time and O(n) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Formatting words into lines with fixed character width.
  • Minimizing quadratic raggedness (extra space penalty).
  • Last line has zero penalty.

Algorithmic Decision Tree:

  • Solve backwards from index n - 1 down to 0.
  • Stop inner loop as soon as line length > k.

Connected Patterns:

Palindrome PartitioningRod CuttingMatrix Chain Multiplication

1. Recursive Word Partitioning

Intuition

Recursively try ending the current line after each word that fits within width k.

Algorithm

  1. Define solve(i).
  2. If i == n, return 0.
  3. Initialize minCost = inf, currentLen = 0.
  4. For j = i to n - 1:
  5. currentLen += nums[j] + (j > i ? 1 : 0).
  6. If currentLen > k, break.
  7. cost = (j == n - 1) ? 0 : (k - currentLen)^2 + solve(j + 1).
  8. minCost = min(minCost, cost).
  9. Return minCost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int i, const vector<int>& nums, int k) {
9 int n = nums.size();
10 if (i == n) return 0;
11
12 int minCost = 1e9, curLen = 0;
13 for (int j = i; j < n; ++j) {
14 curLen += nums[j] + (j > i ? 1 : 0);
15 if (curLen > k) break;
16
17 int cost = (j == n - 1) ? 0 : (k - curLen) * (k - curLen) + solve(j + 1, nums, k);
18 minCost = min(minCost, cost);
19 }
20
21 return minCost;
22 }
23public:
24 int solveWordWrap(vector<int>& nums, int k) {
25 return solve(0, nums, k);
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<int> nums = {3, 2, 2, 5};
32 cout << "Min Cost: " << sol.solveWordWrap(nums, 6) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. Memoized Top-Down DP

Intuition

Store minimum cost for suffix starting at index i in a 1D memo array of size n.

Algorithm

  1. Initialize memo array of size n with -1.
  2. In solve(i): return memo[i] if already computed.
  3. Evaluate all valid line endpoints j.
  4. Store in memo[i] and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int i, const vector<int>& nums, int k, vector<int>& memo) {
9 int n = nums.size();
10 if (i == n) return 0;
11 if (memo[i] != -1) return memo[i];
12
13 int minCost = 1e9, curLen = 0;
14 for (int j = i; j < n; ++j) {
15 curLen += nums[j] + (j > i ? 1 : 0);
16 if (curLen > k) break;
17
18 int cost = (j == n - 1) ? 0 : (k - curLen) * (k - curLen) + solve(j + 1, nums, k, memo);
19 minCost = min(minCost, cost);
20 }
21
22 return memo[i] = minCost;
23 }
24public:
25 int solveWordWrap(vector<int>& nums, int k) {
26 vector<int> memo(nums.size(), -1);
27 return solve(0, nums, k, memo);
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<int> nums = {3, 2, 2, 5};
34 cout << "Min Cost: " << sol.solveWordWrap(nums, 6) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

3. Backward 1D DP Tabulation

Intuition

Tabulate dp[i] from n - 1 down to 0 using a 1D array of size n + 1.

Algorithm

  1. Initialize dp array of size n + 1 with 0.
  2. Loop i from n - 1 down to 0:
  3. dp[i] = infinity, curLen = 0.
  4. For j from i to n - 1:
  5. curLen += nums[j] + (j > i ? 1 : 0).
  6. If curLen > k, break.
  7. cost = (j == n - 1) ? 0 : (k - curLen)^2 + dp[j + 1].
  8. dp[i] = min(dp[i], cost).
  9. Return dp[0].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int solveWordWrap(vector<int>& nums, int k) {
10 int n = nums.size();
11 vector<int> dp(n + 1, 0);
12
13 for (int i = n - 1; i >= 0; --i) {
14 int minCost = 1e9, curLen = 0;
15 for (int j = i; j < n; ++j) {
16 curLen += nums[j] + (j > i ? 1 : 0);
17 if (curLen > k) break;
18
19 int cost = (j == n - 1) ? 0 : (k - curLen) * (k - curLen) + dp[j + 1];
20 minCost = min(minCost, cost);
21 }
22 dp[i] = minCost;
23 }
24
25 return dp[0];
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<int> nums = {3, 2, 2, 5};
32 cout << "Min Cost: " << sol.solveWordWrap(nums, 6) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive PartitioningO(2^n)O(n)Exhaustive branching over all line breaks.Overlapping suffixes
2.Memoized DPO(n^2)O(n)Cache minimum cost for each suffix in memo array.Call stack
3.Backward 1D TabulationOptimalO(n^2)O(n)Iteratively fill dp array from right to left.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Adding spaces before the first word of a line: spaces only go BETWEEN words.

Pitfall 2:

Charging cost on the last line when j == n - 1.

Crucial Edge Cases to Validate:

  • All words fit in a single line: Total length <= k; cost is 0 since it is the last line.
  • A word has length exactly k: Fills the entire line; cost is 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain that this is Donald Knuth's classic line-breaking algorithm used in LaTeX/TeX.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the last line incur ZERO cost regardless of how many extra spaces are left on it?

Back to DSA Sheet