Maximum Vacation Days - Video Solutions

HardArrayDynamic ProgrammingMatrix

Practice this problem Read Solution

LeetCode 568. Maximum Vacation Days

18:513,372 views

5 video solutions available

Maximum Vacation Days - Video Solution

Watch 5 video solutions for Maximum Vacation Days, a hard level problem involving Array, Dynamic Programming, Matrix. This walkthrough by Happy Coding has 3,372 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.

Problem Statement

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 n cities, represented by indexes from 0 to n - 1. Initially, you are in the city indexed 0 on Monday.
The cities are connected by flights. The flights are represented as an n x n matrix (not necessarily symmetrical), called flights representing the airline status from the city i to the city j. If there is no flight from the city i to the city j, flights[i][j] == 0; Otherwise, flights[i][j] == 1. Also, flights[i][i] == 0 for all i.
You totally have k weeks (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 k matrix called days representing this relationship. For the value of days[i][j], it represents the maximum days you could take a vacation in the city i in the week j.
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 A to city B and take the vacation on that day, the deduction towards vacation days will count towards the vacation days of city B in 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.length
n == flights[i].length
n == days.length
k == days[i].length
1 <= n, k <= 100
flights[i][j] is either 0 or 1.
0 <= days[i][j] <= 7

Read full problem with examples

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.

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

Continue Learning

Practice this problem

Solve it on FleetCode

Read Solution & Explanation

Detailed text walkthrough