LeetCode 1335: Minimum Difficulty of a Job Schedule — Ultimate Guide
Minimum Difficulty of a Job Schedule
You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the jobs j where 0 <= j < i).
You have to finish at least one task every day. The difficulty of a job schedule is the sum of the difficulties of each day of the d day. The difficulty of a day is the maximum difficulty of a job done on that day.
You are given an integer array jobDifficulty and an integer d. The difficulty of the ith job is jobDifficulty[i].
Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.
Example 1:
Input: jobDifficulty = [6,5,4,3,2,1], d = 2 Output: 7 Explanation: First day you can finish the first 5 jobs, total difficulty = 6. Second day you can finish the last job, total difficulty = 1. The difficulty of the schedule = 6 + 1 = 7
Example 2:
Input: jobDifficulty = [9,9,9], d = 4 Output: -1 Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.
Example 3:
Input: jobDifficulty = [1,1,1], d = 3 Output: 3 Explanation: The schedule is one job per day. total difficulty will be 3.
Constraints:
1 <= jobDifficulty.length <= 3000 <= jobDifficulty[i] <= 10001 <= d <= 10
Why this problem matters
This is a classic array partitioning problem utilizing Multi-Dimensional Dynamic Programming. It frequently appears in technical interview rounds for tier-1 companies like Amazon and Uber. Mastering this problem teaches you:
How to manage sub-problems dependent on multiple parameters (the current job index and the remaining days).
How to balance constraints (e.g., ensuring at least one job per day).
Advanced optimizations, such as converting a Top-Down Recursive solution with Memoization into an optimized Bottom-Up Tabulation approach.
Intuition
Since jobs must be executed in their exact given sequence, this problem boils down to placing $d - 1$ dividers into the array to split it into $d$ contiguous subarrays.
At each step, we can decide where to end the "current day". If we are on day j and looking at jobs starting from index i, we can try ending our day at any index k (from i up to the point where we still leave enough remaining jobs for the remaining days).
The cost of this choice will be:
We calculate all valid choices for $k$ and pick the absolute minimum.
Dry run
Let's look at a small trace with jobDifficulty = and d = 2 days.
Initial Validation: Total jobs ($3$) $\ge$ total days ($2$), so a valid schedule is possible.
Our recursive state can be denoted as dfs(index, days_left):
dfs(0, 2)(Starting at Job 0, with 2 days left):Option A: End Day 1 at Job 0.
Day 1 Max =
6.Remaining subproblem:
dfs(1, 1)(Jobs `` on 1 remaining day).For
dfs(1, 1), since it's the last day, it must take all remaining jobs. Max of `` =5.Total for Option A = $6 + 5 = 11$.
Option B: End Day 1 at Job 1.
Day 1 Max = $\max(6, 5) = 6$.
Remaining subproblem:
dfs(2, 1)(Job `` on 1 remaining day).For
dfs(2, 1), Max of `` =4.Total for Option B = $6 + 4 = 10$.
We compare Option A ($11$) and Option B ($10$). The minimum is 10.
Iterative solution (Bottom-Up Tabulation)
The iterative approach builds a 2D DP table table from smaller subproblems upwards, avoiding call-stack overhead.
/**
* @param {number[]} jobDifficulty
* @param {number} d
* @return {number}
*/
var minDifficulty = function(jobDifficulty, d) {
const n = jobDifficulty.length;
// Edge case: If there are more days than jobs, it's impossible.
if (n < d) return -1;
// Initialize DP table filled with Infinity
// dp[i][j] represents the min difficulty to schedule first i jobs in j days
const dp = Array.from({ length: n + 1 }, () => Array(d + 1).fill(Infinity));
dp = 0; // Base case: 0 jobs in 0 days costs 0
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= Math.min(d, i); j++) {
let maxDifficulty = 0;
// Iterate backwards to find optimal split point for the j-th day
for (let k = i; k >= j; k--) {
maxDifficulty = Math.max(maxDifficulty, jobDifficulty[k - 1]);
if (dp[k - 1][j - 1] !== Infinity) {
dp[i][j] = Math.min(dp[i][j], dp[k - 1][j - 1] + maxDifficulty);
}
}
}
}
return dp[n][d] === Infinity ? -1 : dp[n][d];
};
Complexity Analysis
Time Complexity: $\mathcal{O}(N^2 \cdot d)$ — Due to three nested loops tracking jobs, days, and split points.
Space Complexity: $\mathcal{O}(N \cdot d)$ — Used to store state combinations within the 2D matrix.
Recursive solution (Top-Down Memoization)
The recursive structure tracks the index of the next job to schedule and how many days are left.
/**
* @param {number[]} jobDifficulty
* @param {number} d
* @return {number}
*/
var minDifficultyRecursive = function(jobDifficulty, d) {
const n = jobDifficulty.length;
if (n < d) return -1;
// Create a memo table initialized to -1
const memo = Array.from({ length: n }, () => Array(d + 1).fill(-1));
const dfs = (index, daysLeft) => {
// Base Case: If it's the last day, must complete all remaining jobs
if (daysLeft === 1) {
let maxVal = 0;
for (let i = index; i < n; i++) {
maxVal = Math.max(maxVal, jobDifficulty[i]);
}
return maxVal;
}
// Return cached result if already calculated
if (memo[index][daysLeft] !== -1) {
return memo[index][daysLeft];
}
let minTotalDifficulty = Infinity;
let currentDayMax = 0;
// Ensure we leave enough jobs for the remaining days (n - i - 1 >= daysLeft - 1)
for (let i = index; i <= n - daysLeft; i++) {
currentDayMax = Math.max(currentDayMax, jobDifficulty[i]);
const nextDaysDifficulty = dfs(i + 1, daysLeft - 1);
minTotalDifficulty = Math.min(minTotalDifficulty, currentDayMax + nextDaysDifficulty);
}
memo[index][daysLeft] = minTotalDifficulty;
return minTotalDifficulty;
};
return dfs(0, d);
};
Complexity Analysis
Time Complexity: $\mathcal{O}(N^2 \cdot d)$ — There are $N \cdot d$ unique recursive states, and each state loops up to $N$ times.
Space Complexity: $\mathcal{O}(N \cdot d)$ — Space spent on both the memoization grid and the recursion call stack.
Common mistakes
Incorrect Bound in Loop Splitting: Forgetting to preserve enough jobs for remaining days, which triggers empty processing days and causes downstream runtime exceptions.
Flawed Initialization Values: Initializing the table with
0instead ofInfinity. Because we seek a minimum result (Math.min), initializing states with 0 prevents the algorithm from finding higher correct minimum combinations.Missing the Primary Boundary Exception: Failing to check if
jobDifficulty.length < dat the entry point, yielding out-of-bounds calculations or incorrect answers instead of the required-1fallback.
Interview follow-ups
Can you reduce the space usage to O(N)? Yes. Notice that day
jonly relies on data from dayj - 1. We can switch to using two 1D rows (prevRowandcurrRow) instead of a full 2D array.Can we solve this in O(N * d) time? Yes, by using a Monotonic Decreasing Stack to track the maximum running difficulties efficiently, though it requires complex index alignment.
Related problems
LeetCode 410 - Split Array Largest Sum (Hard)
LeetCode 813 - Largest Sum of Averages (Medium)
LeetCode 1043 - Partition Array for Maximum Sum (Medium)
FAQ
Q: Why do we return -1 when jobs < days? A: The constraints dictate that you must complete at least one job every single day. If you have 3 jobs but 4 days, you will inevitably have an empty day, making a valid plan impossible.
Q: Can a job's difficulty be 0?
A: Yes, per the constraints (0 <= jobDifficulty[i] <= 1000), jobs can have zero difficulty. The logic holds true since Math.max correctly transitions through zero values.
Links & Resources
Live Code Repository:
GitHub — PraveenMistry/leetCode Master Complex Data Structures:
Medium — Linked List Guides
That’s all folks! In this post, we solved LeetCode problem #1335. Minimum Difficulty of a Job Schedule
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment