Maximum Vacation Days solution and explanation
Google
4 more videos on this problem
LeetCode 568. Maximum Vacation DaysHappy Coding · 18:51 · 3K views
Maximum Vacation Days - 30min Coding ChallengeNihao, MrZhang · 30:26 · 1K views
568. Maximum Vacation Days (Leetcode Hard)Programming Live with Larry · 7:21 · 949 views
LeetCode Hard 568 Maximum Vacation Daysrobzingcod · 13:34 · 145 views
LeetCode 568: Maximum Vacation DaysAlitaCode · 30:31 · 39 views
The problem
LeetCode wants to give one of its best employees the option to travel among n cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow.
Rules and restrictions:
- You can only travel among
ncities, represented by indexes from0ton - 1. Initially, you are in the city indexed0on Monday. - The cities are connected by flights. The flights are represented as an
n x nmatrix (not necessarily symmetrical), calledflightsrepresenting the airline status from the cityito the cityj. If there is no flight from the cityito the cityj,flights[i][j] == 0; Otherwise,flights[i][j] == 1. Also,flights[i][i] == 0for alli. - You totally have
kweeks (each week has seven days) to travel. You can only take flights at most once per day and can only take flights on each week's Monday morning. Since flight time is so short, we do not consider the impact of flight time. - For each city, you can only have restricted vacation days in different weeks, given an
n x kmatrix calleddaysrepresenting this relationship. For the value ofdays[i][j], it represents the maximum days you could take a vacation in the cityiin the weekj. - You could stay in a city beyond the number of vacation days, but you should work on the extra days, which will not be counted as vacation days.
- If you fly from city
Ato cityBand take the vacation on that day, the deduction towards vacation days will count towards the vacation days of cityBin that week. - We do not consider the impact of flight hours on the calculation of vacation days.
Given the two matrices flights and days, return the maximum vacation days you could take during k weeks.
Example 1:
Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]] Output: 12 Explanation: One of the best strategies is: 1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day. (Although you start at city 0, we could also fly to and start at other cities since it is Monday.) 2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days. 3rd week : stay at city 2, and play 3 days and work 4 days. Ans = 6 + 3 + 3 = 12.
Example 2:
Input: flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]] Output: 3 Explanation: Since there are no flights that enable you to move to another city, you have to stay at city 0 for the whole 3 weeks. For each week, you only have one day to play and six days to work. So the maximum number of vacation days is 3. Ans = 1 + 1 + 1 = 3.
Example 3:
Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]] Output: 21 Explanation: One of the best strategies is: 1st week : stay at city 0, and play 7 days. 2nd week : fly from city 0 to city 1 on Monday, and play 7 days. 3rd week : fly from city 1 to city 2 on Monday, and play 7 days. Ans = 7 + 7 + 7 = 21
Constraints:
n == flights.lengthn == flights[i].lengthn == days.lengthk == days[i].length1 <= n, k <= 100flights[i][j]is either0or1.0 <= days[i][j] <= 7
Approach overview
Problem Overview: You start in city 0 and have k weeks to travel across n cities. A flight matrix tells you which cities are connected, and a vacation matrix tells how many days you can spend in each city per week. Each Monday you can stay or take a flight, and the goal is to maximize total vacation days.
Approach 1: DFS + Memoization (Top-Down DP) (Time: O(k * n^2), Space: O(k * n))
This approach models the problem as a decision tree: for every week and city, you choose whether to stay or fly to another reachable city. A recursive DFS explores all possible paths across weeks. Without optimization this becomes exponential, but memoization caches results for states defined by (week, city). Each state iterates through all cities to check valid flights using the adjacency matrix, accumulating the best possible vacation total. Memoization ensures each state is computed once, reducing the complexity to O(k * n^2). This version is intuitive and mirrors the natural decision process of the problem.
Approach 2: Bottom-Up Dynamic Programming (Matrix Transition) (Time: O(k * n^2), Space: O(n))
The iterative DP approach builds results week by week. Define dp[c] as the maximum vacation days achievable when starting the current week in city c. For each week, compute a new array by considering transitions from every previous city. If you can stay or fly (flights[prev][curr] == 1), update the best value using dp[prev] + days[curr][week]. This essentially treats the flight matrix as a transition graph and the vacation matrix as weekly rewards. Rolling arrays reduce memory to O(n). This approach avoids recursion and runs efficiently even when the number of weeks is large.
The key insight is that every week represents a layer in the state graph, and cities are nodes in that layer. Transitions come from the flight matrix, while rewards come from the vacation matrix. Dynamic programming works well because optimal choices for future weeks depend only on the current week and city.
Understanding matrix-based transitions is common in problems involving travel schedules or stage-based decisions. Related patterns appear in dynamic programming, grid-like reasoning with matrix data, and iteration over array structures.
Recommended for interviews: The bottom-up dynamic programming approach is what interviewers typically expect. It clearly shows you can model the problem as states and transitions. Explaining the DFS version first demonstrates problem understanding, while implementing the iterative DP proves you can optimize time and space.
Solution
class Solution:
def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
n = len(flights)
K = len(days[0])
f = [[-inf] * n for _ in range(K + 1)]
f[0][0] = 0
for k in range(1, K + 1):
for j in range(n):
f[k][j] = f[k - 1][j]
for i in range(n):
if flights[i][j]:
f[k][j] = max(f[k][j], f[k - 1][i])
f[k][j] += days[j][k - 1]
return max(f[-1][j] for j in range(n))class Solution {
public int maxVacationDays(int[][] flights, int[][] days) {
int n = flights.length;
int K = days[0].length;
final int inf = 1 << 30;
int[][] f = new int[K + 1][n];
for (var g : f) {
Arrays.fill(g, -inf);
}
f[0][0] = 0;
for (int k = 1; k <= K; ++k) {
for (int j = 0; j < n; ++j) {
f[k][j] = f[k - 1][j];
for (int i = 0; i < n; ++i) {
if (flights[i][j] == 1) {
f[k][j] = Math.max(f[k][j], f[k - 1][i]);
}
}
f[k][j] += days[j][k - 1];
}
}
int ans = 0;
for (int j = 0; j < n; ++j) {
ans = Math.max(ans, f[K][j]);
}
return ans;
}
}class Solution {
public:
int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
int n = flights.size();
int K = days[0].size();
int f[K + 1][n];
memset(f, -0x3f, sizeof(f));
f[0][0] = 0;
for (int k = 1; k <= K; ++k) {
for (int j = 0; j < n; ++j) {
f[k][j] = f[k - 1][j];
for (int i = 0; i < n; ++i) {
if (flights[i][j] == 1) {
f[k][j] = max(f[k][j], f[k - 1][i]);
}
}
f[k][j] += days[j][k - 1];
}
}
int ans = 0;
for (int j = 0; j < n; ++j) {
ans = max(ans, f[K][j]);
}
return ans;
}
};function maxVacationDays(flights: number[][], days: number[][]): number {
const n = flights.length;
const K = days[0].length;
const inf = Number.NEGATIVE_INFINITY;
const f: number[][] = Array.from({ length: K + 1 }, () => Array(n).fill(inf));
f[0][0] = 0;
for (let k = 1; k <= K; k++) {
for (let j = 0; j < n; j++) {
f[k][j] = f[k - 1][j];
for (let i = 0; i < n; i++) {
if (flights[i][j]) {
f[k][j] = Math.max(f[k][j], f[k - 1][i]);
}
}
f[k][j] += days[j][k - 1];
}
}
return Math.max(...f[K]);
}func maxVacationDays(flights [][]int, days [][]int) (ans int) {
n, K := len(flights), len(days[0])
f := make([][]int, K+1)
for i := range f {
f[i] = make([]int, n)
for j := range f[i] {
f[i][j] = -(1 << 30)
}
}
f[0][0] = 0
for k := 1; k <= K; k++ {
for j := 0; j < n; j++ {
f[k][j] = f[k-1][j]
for i := 0; i < n; i++ {
if flights[i][j] == 1 {
f[k][j] = max(f[k][j], f[k-1][i])
}
}
f[k][j] += days[j][k-1]
}
}
for j := 0; j < n; j++ {
ans = max(ans, f[K][j])
}
return
}impl Solution {
pub fn max_vacation_days(flights: Vec<Vec<i32>>, days: Vec<Vec<i32>>) -> i32 {
let n = flights.len();
let k = days[0].len();
let inf = i32::MIN;
let mut f = vec![vec![inf; n]; k + 1];
f[0][0] = 0;
for step in 1..=k {
for j in 0..n {
f[step][j] = f[step - 1][j];
for i in 0..n {
if flights[i][j] == 1 {
f[step][j] = f[step][j].max(f[step - 1][i]);
}
}
f[step][j] += days[j][step - 1];
}
}
*f[k].iter().max().unwrap()
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS + Memoization | O(k * n^2) | O(k * n) | Good for understanding the decision tree and converting brute force recursion into DP |
| Bottom-Up Dynamic Programming | O(k * n^2) | O(n) | Best practical solution; efficient and commonly expected in interviews |
Frequently asked questions
Is Maximum Vacation Days easy or hard?
Maximum Vacation Days is categorized as a Hard problem on LeetCode. The challenge comes from modeling travel decisions across weeks and cities while efficiently handling transitions using dynamic programming.
Maximum Vacation Days Python/Java solution
Implementations typically use a DP array that stores the best vacation total for each city. For every week, compute a new array by checking whether staying or flying from each previous city is possible. The same logic translates directly across Python, Java, C++, Go, and other languages.
How to solve Maximum Vacation Days in O(n)?
The full problem cannot be solved in O(n) because every week may require checking transitions between all pairs of cities. The best known approach is O(k * n^2) using dynamic programming, where each week processes all possible city transitions defined by the flight matrix.
What is the best approach for Maximum Vacation Days?
The most effective solution uses dynamic programming with week-by-week state transitions. Define a DP state representing the maximum vacation days achievable when starting a given week in a specific city. For each week, iterate over all possible previous cities and update reachable cities using the flight matrix. This results in O(k * n^2) time and O(n) space with a rolling array.
Is Maximum Vacation Days asked at Google/Amazon/Meta?
Maximum Vacation Days is a classic dynamic programming problem that has appeared in interviews at companies like Google and Amazon. It tests the ability to model states, transitions, and optimize decisions over multiple stages using DP.
What data structure is used in Maximum Vacation Days?
The solution mainly uses arrays and matrices. The flight matrix represents connectivity between cities, while the vacation matrix stores rewards per city per week. Dynamic programming arrays track the maximum vacation days achievable for each city at every week.
What is the time complexity of Maximum Vacation Days?
The optimal dynamic programming solution runs in O(k * n^2) time, where n is the number of cities and k is the number of weeks. For each week, the algorithm checks all city-to-city transitions using the flight matrix. Space complexity can be reduced to O(n) using rolling arrays.