568. Maximum Vacation Days
Problem Description
LeetCode offers a challenge that simulates planning a travel itinerary to maximize vacation days while adhering to certain constraints. You can visit n
different cities, each identified by indices from 0
to n-1
, and have k
weeks to spend your vacation days. The goal is to choose a travel schedule that will allow you to maximize your total vacation days.
The rules you must keep in mind are:
- You start in city
0
. - Travel is possible between cities based on a flights matrix. A
1
inflights[i][j]
means you can fly from cityi
to cityj
, while a0
means no flight is available. - You have
k
weeks to travel, and you can only fly on Monday mornings. - Each city has a limit on how many vacation days you can spend there each week, described by a matrix
days
. - You can work on days that are not counted towards your vacation.
- Travelling from city
A
to cityB
uses up a vacation day of cityB
. - The time spent on flights is not factored into the vacation days.
The task is to take these rules into account and determine the maximum number of vacation days you can enjoy.
Intuition
To solve this problem, we need an approach that can consider all possible travel routes and select the one that yields the maximum vacation days. A dynamic programming solution is well-suited for this problem since it allows us to make decisions at each stage while keeping track of all previously computed states for future reference.
The essential idea behind the solution is to use a two-dimensional array f
where f[k][j]
represents the maximum vacation days you can have by the end of week k
if you are in city j
. Initialization is critical: f[0][0]
is set to 0
because the starting point is city 0
with no vacation days used yet.
The dynamic programming process then iterates over each week. For every city j
, it updates the maximum vacation days by trying to maintain the same city or by flying from some city i
where a flight is available (flights[i][j] == 1
). After taking the maximum from these options, the vacation days available in city j
for that week (days[j][k - 1]
) are added.
This approach ensures that at any point in the iteration, f[k][j]
contains the optimum number of vacation days up to that week if you are in city j
. After iterating over all weeks and cities, the solution will be the maximum value in the last row of the array f
, which represents the maximum vacation days for the last week at any city.
The elegance of dynamic programming lies in its ability to break down complex decisions into simpler, overlapping subproblems, storing those results, and reusing them in an optimal manner to construct an answer for the global problem.
Learn more about Dynamic Programming patterns.
Solution Approach
The provided solution is an implementation of dynamic programming. To understand the code, let's break it down into its core components:
-
Dynamic Array Initialization:
f = [[-inf] * n for _ in range(K + 1)] f[0][0] = 0
In this block, we're initializing an array
f
that holds the maximum vacation days.-inf
is used to indicate that a state is initially unreachable. The first city at the first week is set to 0 since we start with no vacation days utilized prior to the first week. -
Nested Loops for State Transition:
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]
- The outermost loop iterates over weeks (
k
), as each iteration corresponds to the state of each week. - The second loop iterates over every city (
j
), as we want to calculate the maximum vacation days if we end up in cityj
at the end of weekk
. - Inside the second loop, there's an inner loop over every city (
i
) that checks if a flight is available from cityi
to cityj
. If a flight is available, the maximum vacation days for cityj
are updated by taking the maximum of the current value or the value for cityi
from the previous week. - After deciding whether to stay in the same city or fly from another city, we add the vacation days for city
j
in the corresponding week (days[j][k - 1]
).
- The outermost loop iterates over weeks (
-
Final Result:
return max(f[-1][j] for j in range(n))
- After updating the array
f
for all the weeks, the final result is the maximum value in the last week (which is at indexK
) for all cities. This represents the scenario where, irrespective of the city you are in, you want the maximum vacation days accumulated by the last week of your travel schedule.
- After updating the array
This solution effectively utilizes a bottom-up dynamic programming approach, filling out a table of sub-solutions (vacation days for each city at the end of each week), which are then combined to form the solution to the overarching problem (maximum vacation days after k
weeks).
The approach ensures we consider every potential week-to-week transition while adhering to the constraints of available flights and maximum vacation days in each city. By completing the matrix, the algorithm canvasses all strategic paths without redundant recalculations, which characterizes dynamic programming's optimization.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a scenario with 3 cities (n = 3
) and 2 weeks (K = 2
) to spend on vacation. The available flights matrix and days matrix are as follows:
flights = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ] days = [ [1, 3], [6, 0], [3, 4] ]
The flights matrix indicates that from any city, one can fly to either of the other two cities. The days matrix shows the vacation days one can spend in each city during each of the two weeks.
Initialization
- First, we initialize the dynamic array
f
with-infinity
to indicate unknown/unreachable states, except for the starting point which is city0
at week0
with0
vacation days spent.
Iteration Process
Week 1:
- When we are at the start of week 1 (
k = 1
), we look at each cityj
.- For city
0
, since we start there, we don't need to consider flights. We can take advantage of the vacation days in city0
, which is1
. Sof[1][0] = 1
. - For city
1
, there is a flight from city0
to city1
. We can either stay in city0
and accumulate1
day or fly to city1
and accumulate6
days. So we choose to fly andf[1][1] = 6
. - For city
2
, there's also a flight from city0
to city2
. Again, we can either stay in city0
with1
day or fly to city2
and accumulate3
days. So we fly andf[1][2] = 3
.
- For city
Week 2:
- Moving to week 2 (
k = 2
), we now examine the options from the perspective of each cityj
.- In city
0
, we can either come from city0
with1
day (accumulated from last week) or come from city2
with3
days as there are flights available from both. We choose the latter for a total of3 + 3 = 6
days becausedays[0][1] = 3
. - In city
1
, the flight from city0
to city1
doesn't give us any vacation days for this week asdays[1][1] = 0
. So we stay in city1
and keep the6
days accumulated from last week. - In city
2
, we can fly from either city1
or city0
, with last week's days of6
and3
, respectively. Since city2
has4
vacation days available this week (days[2][1]
), we choose to come from city1
for a total of6 + 4 = 10
days in city2
.
- In city
Final Decision and Result
- After completing the iteration process, we find the maximum value in the
f
array for the last week. This would bemax(f[2])
which equates tomax([6, 6, 10]) = 10
. The maximum vacation days one can spend is10
by traveling from city0
to city1
in the first week and then to city2
in the second week.
This example illustrates each step of the dynamic programming approach and shows how the solution can be traced and optimized week by week, given the flight availability and the vacation days constraints.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
5 # Number of cities
6 num_cities = len(flights)
7 # Number of weeks
8 num_weeks = len(days[0])
9 # Initialize the dp array with -infinity to signify unvisited states
10 # plus one row for initial state (week 0)
11 dp = [[float('-inf')] * num_cities for _ in range(num_weeks + 1)]
12 # Starting city has 0 vacation days initially
13 dp[0][0] = 0
14
15 # Loop through each week
16 for week in range(1, num_weeks + 1):
17 # Loop through each city for the current week
18 for current_city in range(num_cities):
19 # First, assume staying in the same city as the previous week
20 dp[week][current_city] = dp[week - 1][current_city]
21
22 # Then, check for other cities we can fly to
23 for previous_city in range(num_cities):
24 # If there is a flight from a previous city to the current city
25 if flights[previous_city][current_city]:
26 # Take the max of staying or flying from the previous city
27 dp[week][current_city] = max(dp[week][current_city], dp[week - 1][previous_city])
28
29 # Add the vacation days for the current city and week
30 dp[week][current_city] += days[current_city][week - 1]
31
32 # Find the max vacation days from the last week across all cities
33 return max(dp[num_weeks][city] for city in range(num_cities))
34
1class Solution {
2 public int maxVacationDays(int[][] flights, int[][] days) {
3 int numCities = flights.length; // Number of cities
4 int numWeeks = days[0].length; // Number of weeks
5 final int INF = Integer.MIN_VALUE; // Representation of negative infinity
6 int[][] dp = new int[numWeeks + 1][numCities]; // DP table for storing max vacation days
7
8 // Initialize DP table with negative infinity indicating not reachable
9 for (int[] week : dp) {
10 Arrays.fill(week, INF);
11 }
12
13 // Base case: start at city 0 at week 0
14 dp[0][0] = 0;
15
16 // Fill the DP table week by week
17 for (int week = 1; week <= numWeeks; ++week) {
18 for (int currentCity = 0; currentCity < numCities; ++currentCity) {
19 // Max vacation days in the current city without flying
20 dp[week][currentCity] = dp[week - 1][currentCity];
21
22 // Check for flights from other cities to the current city and update max days
23 for (int prevCity = 0; prevCity < numCities; ++prevCity) {
24 if (flights[prevCity][currentCity] == 1) {
25 dp[week][currentCity] = Math.max(dp[week][currentCity], dp[week - 1][prevCity]);
26 }
27 }
28
29 // If the city is reachable, add vacation days for the current week
30 if (dp[week][currentCity] != INF) {
31 dp[week][currentCity] += days[currentCity][week - 1];
32 }
33 }
34 }
35
36 // Find the maximum vacation days from all reachable cities at the last week
37 int maxVacationDays = 0;
38 for (int city = 0; city < numCities; ++city) {
39 maxVacationDays = Math.max(maxVacationDays, dp[numWeeks][city]);
40 }
41
42 return maxVacationDays;
43 }
44}
45
1class Solution {
2public:
3 int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
4 // n represents the number of cities
5 int numCities = flights.size();
6 // k represents the number of weeks
7 int numWeeks = days[0].size();
8 // dp array to store the maximum vacation days up to week k in city j
9 int dp[numWeeks + 1][numCities];
10 // initializing the dp array with minimum possible value
11 memset(dp, -0x3f, sizeof(dp));
12 // starting at city 0 with 0 vacation days
13 dp[0][0] = 0;
14
15 // Iterate over each week
16 for (int week = 1; week <= numWeeks; ++week) {
17 // Iterate over each city for the current week
18 for (int city = 0; city < numCities; ++city) {
19 // Set the dp value for the current city and week to the vacation days of the same city in the previous week
20 dp[week][city] = dp[week - 1][city];
21 // Check all possible cities where we could have come from to the current city
22 for (int prevCity = 0; prevCity < numCities; ++prevCity) {
23 if (flights[prevCity][city] == 1) {
24 // Update the dp value for the current city and week with the maximum between the current dp value and
25 // vacation days of the previous city in the previous week
26 dp[week][city] = max(dp[week][city], dp[week - 1][prevCity]);
27 }
28 }
29 // Add the vacation days of the current city for the current week
30 dp[week][city] += days[city][week - 1];
31 }
32 }
33
34 // Initialize answer for the maximum vacation days
35 int maxVacation = 0;
36 // Iterate over each city at the last week to find the maximum vacation days
37 for (int city = 0; city < numCities; ++city) {
38 maxVacation = max(maxVacation, dp[numWeeks][city]);
39 }
40
41 return maxVacation;
42 }
43};
44
1// Define the maximumDays function to calculate max vacation days
2function maximumDays(flights: number[][], days: number[][]): number {
3 // n represents the number of cities
4 let numCities: number = flights.length;
5 // k represents the number of weeks
6 let numWeeks: number = days[0].length;
7
8 // dp array to store the maximum vacation days up to week k in city j
9 let dp: number[][] = new Array(numWeeks + 1).fill(0).map(() => new Array(numCities).fill(Number.MIN_SAFE_INTEGER));
10
11 // starting at city 0 with 0 vacation days
12 dp[0][0] = 0;
13
14 // Iterate over each week
15 for (let week = 1; week <= numWeeks; ++week) {
16 // Iterate over each city for the current week
17 for (let city = 0; city < numCities; ++city) {
18 // Initially set the dp value for the current city and week
19 // to the vacation days of the same city in the previous week
20 dp[week][city] = dp[week - 1][city];
21
22 for (let prevCity = 0; prevCity < numCities; ++prevCity) {
23 // Check if there is a flight from prevCity to city
24 if (flights[prevCity][city] === 1) {
25 // Update the dp value for the current city and week with the maximum between the current dp value and
26 // the vacation days of the previous city in the previous week
27 dp[week][city] = Math.max(dp[week][city], dp[week - 1][prevCity]);
28 }
29 }
30 // Add the vacation days of the current city for the current week
31 dp[week][city] += days[city][week - 1];
32 }
33 }
34
35 // Initialize the answer for the maximum vacation days
36 let maxVacation: number = 0;
37 // Iterate over each city at the last week to find the maximum vacation days
38 for (let city = 0; city < numCities; ++city) {
39 maxVacation = Math.max(maxVacation, dp[numWeeks][city]);
40 }
41
42 return maxVacation;
43}
44
45// Usage:
46// const flights = [[...], [...], ...];
47// const days = [[...], [...], ...];
48// console.log(maximumDays(flights, days));
49
Time and Space Complexity
The code provided aims to solve a problem where it calculates the maximum vacation days one can take given certain flight connectivity and days one can spend in each city per week.
Time Complexity
The time complexity of the algorithm is primarily determined by the nested loops:
- The outer loop runs for
K
iterations, whereK
is the number of weeks. - The first inner loop runs for
n
iterations, wheren
is the number of cities. - The second inner loop (nested inside the first one) also runs for
n
iterations, again going through all cities.
Each of these loop iterations involves constant time operations or operations that take O(1)
time.
Thus, the total time complexity is given by O(K * n^2)
.
Space Complexity
The space complexity is determined by the storage used for the f
array, which is a 2D array with dimensions (K + 1) x n
. Here, f[k][j]
represents the maximum vacation days one can achieve till week k
in city j
.
Thus, the space complexity of the algorithm is O(K * n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!