Word Wrap Problem

Problem Statement

Given an array of word lengths words[] and a maximum line width maxWidth, arrange the words into lines such that the total cost of extra spaces is minimized. The cost of a line is (extra spaces)^3 where extra spaces = maxWidth - total characters in that line - spaces between words. The last line has no cost.

Example:

• Input: words = [3, 2, 2, 5], maxWidth = 6
• Output: 10
• Explanation: Line 1: word1 (length 3) → 3 extra spaces, cost = 27. But putting words 1+2 on line 1: 3+2+1(space)=6, cost=0. Words 3+4 won't fit together. Better arrangement minimizes total cost.

Noob-Friendly Explanation

Imagine you're writing a paragraph and each line can only be a certain width (like a narrow column in a newspaper). You want to fit words into lines such that there's as little wasted space as possible. The more empty space on a line, the worse it looks (and the penalty is cubic — lots of empty space is REALLY bad).

It's like packing boxes on shelves — you want to fill each shelf as completely as possible.

Approach 1: Brute Force (Recursion)

Intuition

Try all possible ways to put words on lines. For each word, decide whether to put it on the current line or start a new line. Compute the total cost for each arrangement and return the minimum.

Algorithm

1. Starting from the first word, try putting 1 word, 2 words, 3 words, etc. on the first line (as long as they fit).
2. For each choice, compute the cost of extra spaces on that line and recursively solve for remaining words.
3. Return the minimum total cost.

class Solution {
    public int wordWrap(int[] words, int maxWidth) {
        return solve(words, maxWidth, 0);
    }

    private int solve(int[] words, int maxWidth, int index) {
        if (index == words.length) return 0;

        int remainingWidth = maxWidth;
        int cost = Integer.MAX_VALUE;

        for (int j = index; j < words.length; j++) {
            // Check if word j fits on the current line
            if (j == index) {
                remainingWidth -= words[j];
            } else {
                remainingWidth -= (1 + words[j]); // 1 for space between words
            }

            if (remainingWidth < 0) break; // Doesn't fit

            int lineCost;
            if (j == words.length - 1) {
                lineCost = 0; // Last line has no cost
            } else {
                lineCost = remainingWidth * remainingWidth * remainingWidth;
            }

            int totalCost = lineCost + solve(words, maxWidth, j + 1);
            cost = Math.min(cost, totalCost);
        }

        return cost;
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - In the worst case, we explore all possible line break combinations.
• Space Complexity: O(n) - Recursion stack depth.

Approach 2: Optimal (Dynamic Programming)

Intuition

Use a DP array where dp[i] = minimum cost to arrange words i through n-1. We fill this bottom-up starting from the last word.

Algorithm

1. Create dp[n+1] where dp[n] = 0 (no words left = no cost).
2. For each word i from n-1 to 0, try putting words i to j on one line.
3. Compute the extra space cost and add dp[j+1].
4. dp[i] = min over all valid j of (cost(i,j) + dp[j+1]).

class Solution {
    public int wordWrap(int[] words, int maxWidth) {
        int n = words.length;
        int[] dp = new int[n + 1];
        dp[n] = 0; // No words = no cost

        for (int i = n - 1; i >= 0; i--) {
            int remainingWidth = maxWidth;
            dp[i] = Integer.MAX_VALUE;

            for (int j = i; j < n; j++) {
                if (j == i) {
                    remainingWidth -= words[j];
                } else {
                    remainingWidth -= (1 + words[j]);
                }

                if (remainingWidth < 0) break;

                int lineCost;
                if (j == n - 1) {
                    lineCost = 0; // Last line has no cost
                } else {
                    lineCost = remainingWidth * remainingWidth * remainingWidth;
                }

                dp[i] = Math.min(dp[i], lineCost + dp[j + 1]);
            }
        }

        return dp[0];
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - Two nested loops, each going up to n.
• Space Complexity: O(n) - DP array of size n+1.