Maximum Vacation Days - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

HardPremiumFree on FleetCodeArray Dynamic Programming Matrix8 min readAsked at: Meta, Datadog, Google

Practice this problem

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

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

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Detailed 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

Video Solution

LeetCode 568. Maximum Vacation Days • Happy Coding • 3,372 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Vacation Days with our built-in code editor and test cases.

Practice on FleetCode

Cheapest Flights Within K Stops

Problem Info

DifficultyHard

Acceptance46.7%

Approaches1

Reading time8 min

Asked at

Meta Datadog Google