LeetCode 568 - Maximum Vacation Days

LeetCode Problem 568

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

This problem asks us to maximize the total number of vacation days over k weeks while traveling between n cities under specific flight constraints.

We start in city 0 on the Monday morning of week 0. Every Monday morning, we may either stay in the current city or take exactly one flight to another city if a direct flight exists. After arriving in a city for that week, we earn the number of vacation days specified by days[city][week].

The input contains two matrices:

• flights[i][j] indicates whether we can fly directly from city i to city j.
• days[i][w] indicates how many vacation days we can enjoy if we spend week w in city i.

The goal is to compute the maximum total vacation days achievable across all weeks.

The constraints are important:

• n <= 100
• k <= 100

A naive brute-force search over all possible travel schedules would explode exponentially because every week may involve multiple city choices. Since both dimensions are at most 100, this strongly suggests that a polynomial-time dynamic programming solution is expected.

An important detail is that staying in the same city is always allowed, even though flights[i][i] == 0. The flight matrix only represents actual flights between distinct cities.

Another subtle point is that flights happen on Monday morning before vacation days for that week are counted. That means if we fly into a city at the start of a week, we immediately gain that city's vacation days for that week.

Several edge cases can easily cause bugs:

• No flights at all, meaning we are trapped in city 0.
• Cities that are unreachable from the starting city.
• Optimal schedules that require temporarily taking fewer vacation days to unlock better future weeks.
• Cases where staying in place is better than flying.
• Weeks where all cities offer 0 vacation days.

The problem guarantees valid matrix dimensions and binary flight entries, so we do not need to validate input structure.

Approaches

Brute Force Approach

The brute-force solution tries every possible sequence of cities over all k weeks.

At each week, from the current city, we consider all reachable cities including staying in the current city. We recursively explore every possible travel schedule and compute the total vacation days accumulated.

This approach is correct because it explicitly enumerates every valid path and chooses the maximum total.

However, it is far too slow. In the worst case, every city can reach every other city, giving approximately n choices per week. The total number of schedules becomes:

$$O(n^k)$$

With n = 100 and k = 100, this is completely infeasible.

Dynamic Programming Insight

The key observation is that the problem has overlapping subproblems.

Suppose we know:

• the current week
• the city we are in at the start of that week

Then the best possible future result from that state is always the same, regardless of how we arrived there.

This naturally leads to dynamic programming.

We define:

$$dp[week][city]$$

as the maximum vacation days obtainable after finishing week while ending in city.

For each week, we transition from all previously reachable cities into all currently reachable cities.

Since each state only depends on the previous week, we can optimize space to use only one dimension.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^k)	O(k) recursion stack	Tries every possible travel schedule
Optimal Dynamic Programming	O(k * n^2)	O(n)	Computes best achievable value for each city each week

Algorithm Walkthrough

1. Initialize a DP array of size n.

The value dp[city] represents the maximum vacation days achievable after the previous week while currently being in city.

Initially, only city 0 is reachable, so:

dp[0] = 0
dp[other] = -1

We use -1 to represent unreachable states. 2. Process weeks one by one.

For every week, create a new array called next_dp.

This array stores the best vacation totals after completing the current week. 3. For every city reachable from the previous week, attempt all valid moves.

From city from_city, we may:

• stay in the same city
• fly to any city to_city where flights[from_city][to_city] == 1

4. Update the destination city's best value.

If we can move from from_city to to_city, then:

next_dp[to_city] =
    max(next_dp[to_city],
        dp[from_city] + days[to_city][week])

We add the vacation days of the destination city because we spend the current week there. 5. Replace the old DP array.

After processing all transitions for the current week:

dp = next_dp

6. Continue until all weeks are processed.
7. Return the maximum value in dp.

After the final week, each entry represents the best total achievable while ending in that city.

Why it works

The DP invariant is:

After processing week w, dp[city] stores the maximum vacation days achievable by ending week w in city.

Every valid schedule must transition from some city in week w - 1 to a reachable city in week w. The algorithm evaluates all such transitions and keeps only the best total for each destination city.

Because all reachable states are considered and optimal substructure holds, the final maximum is guaranteed to be optimal.

Python Solution

from typing import List

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n = len(flights)
        k = len(days[0])

        dp = [-1] * n
        dp[0] = 0

        for week in range(k):
            next_dp = [-1] * n

            for from_city in range(n):
                if dp[from_city] == -1:
                    continue

                for to_city in range(n):
                    if from_city == to_city or flights[from_city][to_city] == 1:
                        next_dp[to_city] = max(
                            next_dp[to_city],
                            dp[from_city] + days[to_city][week]
                        )

            dp = next_dp

        return max(dp)

The implementation begins by initializing the DP array. Only city 0 is reachable before any weeks begin, so every other city is marked unreachable using -1.

For each week, we create a fresh next_dp array. This prevents updates for the current week from interfering with transitions still being processed.

The outer loop iterates through all possible source cities. If a city is unreachable, we skip it immediately.

The inner loop checks all destination cities. A transition is valid if:

• we stay in the same city
• or a flight exists

Whenever a valid transition exists, we update the destination city's best achievable vacation total.

After processing all transitions for the current week, we replace dp with next_dp.

Finally, we return the largest achievable value among all ending cities.

Go Solution

func maxVacationDays(flights [][]int, days [][]int) int {
	n := len(flights)
	k := len(days[0])

	dp := make([]int, n)

	for i := 1; i < n; i++ {
		dp[i] = -1
	}

	for week := 0; week < k; week++ {
		nextDP := make([]int, n)

		for i := 0; i < n; i++ {
			nextDP[i] = -1
		}

		for fromCity := 0; fromCity < n; fromCity++ {
			if dp[fromCity] == -1 {
				continue
			}

			for toCity := 0; toCity < n; toCity++ {
				if fromCity == toCity || flights[fromCity][toCity] == 1 {
					candidate := dp[fromCity] + days[toCity][week]

					if candidate > nextDP[toCity] {
						nextDP[toCity] = candidate
					}
				}
			}
		}

		dp = nextDP
	}

	answer := 0

	for _, value := range dp {
		if value > answer {
			answer = value
		}
	}

	return answer
}

The Go implementation closely mirrors the Python solution.

Since Go slices default to 0, we explicitly initialize unreachable states to -1.

Go does not provide a built-in max function for integers, so we use a simple comparison before assignment.

Integer overflow is not a concern because the maximum possible answer is:

100 weeks * 7 days = 700

which easily fits within Go's integer range.

Worked Examples

Example 1

flights =
[
  [0,1,1],
  [1,0,1],
  [1,1,0]
]

days =
[
  [1,3,1],
  [6,0,3],
  [3,3,3]
]

Initial state:

City	DP Value
0	0
1	-1
2	-1

Week 0

From city 0:

• stay in 0 → 0 + 1 = 1
• fly to 1 → 0 + 6 = 6
• fly to 2 → 0 + 3 = 3

Result:

City	DP After Week 0
0	1
1	6
2	3

Week 1

Process transitions from all reachable cities.

Best outcomes become:

City	DP After Week 1
0	9
1	6
2	9

Explanation:

• Best way to city 0:

• from city 1

• 6 + 3 = 9

• Best way to city 2:

• from city 1

• 6 + 3 = 9

Week 2

Final transitions:

City	DP After Week 2
0	10
1	12
2	12

Maximum value:

12

Example 2

flights =
[
  [0,0,0],
  [0,0,0],
  [0,0,0]
]

days =
[
  [1,1,1],
  [7,7,7],
  [7,7,7]
]

No flights exist, so we must remain in city 0.

Week-by-week DP

Week	DP State
Start	[0, -1, -1]
Week 0	[1, -1, -1]
Week 1	[2, -1, -1]
Week 2	[3, -1, -1]

Final answer:

3

Example 3

flights =
[
  [0,1,1],
  [1,0,1],
  [1,1,0]
]

days =
[
  [7,0,0],
  [0,7,0],
  [0,0,7]
]

Week 0

Best results:

City	Value
0	7
1	0
2	0

Week 1

Best results:

City	Value
0	7
1	14
2	7

Week 2

Best results:

City	Value
0	14
1	14
2	21

Final answer:

21

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k * n^2)	For every week, we examine all pairs of cities
Space	O(n)	Only two DP arrays of size n are maintained

The algorithm processes k weeks. During each week, every source city may transition to every destination city, producing n * n transitions.

The space complexity is optimized to one dimension because each week's computation depends only on the previous week.

Test Cases

from typing import List

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n = len(flights)
        k = len(days[0])

        dp = [-1] * n
        dp[0] = 0

        for week in range(k):
            next_dp = [-1] * n

            for from_city in range(n):
                if dp[from_city] == -1:
                    continue

                for to_city in range(n):
                    if from_city == to_city or flights[from_city][to_city] == 1:
                        next_dp[to_city] = max(
                            next_dp[to_city],
                            dp[from_city] + days[to_city][week]
                        )

            dp = next_dp

        return max(dp)

solution = Solution()

# Example 1
assert solution.maxVacationDays(
    [[0,1,1],[1,0,1],[1,1,0]],
    [[1,3,1],[6,0,3],[3,3,3]]
) == 12  # standard fully connected example

# Example 2
assert solution.maxVacationDays(
    [[0,0,0],[0,0,0],[0,0,0]],
    [[1,1,1],[7,7,7],[7,7,7]]
) == 3  # no flights available

# Example 3
assert solution.maxVacationDays(
    [[0,1,1],[1,0,1],[1,1,0]],
    [[7,0,0],[0,7,0],[0,0,7]]
) == 21  # optimal sequential travel

# Single city
assert solution.maxVacationDays(
    [[0]],
    [[5,6,7]]
) == 18  # must stay in same city

# All zero vacation days
assert solution.maxVacationDays(
    [[0,1],[1,0]],
    [[0,0],[0,0]]
) == 0  # no vacation possible anywhere

# Reachable city gives better future payoff
assert solution.maxVacationDays(
    [[0,1],[0,0]],
    [[1,1],[0,7]]
) == 8  # move early for larger later reward

# Staying is better than flying
assert solution.maxVacationDays(
    [[0,1],[1,0]],
    [[7,7],[1,1]]
) == 14  # staying in city 0 is optimal

# Unreachable city with high rewards
assert solution.maxVacationDays(
    [[0,0],[0,0]],
    [[1,1],[7,7]]
) == 2  # city 1 cannot be reached

# Multiple optimal routes
assert solution.maxVacationDays(
    [[0,1],[1,0]],
    [[3,3],[3,3]]
) == 6  # several schedules achieve same answer

Test Case Summary

Test	Why
Fully connected example	Verifies standard DP transitions
No flights	Ensures unreachable cities remain invalid
Sequential high rewards	Tests optimal multi-week planning
Single city	Validates minimum n
All zero days	Ensures algorithm handles zero rewards
Delayed payoff	Confirms future planning behavior
Staying optimal	Verifies staying is always considered
Unreachable high-value city	Prevents illegal transitions
Multiple optimal routes	Ensures max logic works correctly

Edge Cases

One important edge case occurs when there are no flights between any cities. A naive implementation may incorrectly assume travel is always possible or forget that unreachable cities should remain invalid. The DP solution handles this safely by initializing unreachable states to -1 and never transitioning from them.

Another critical edge case is the single-city scenario. Since flights[0][0] is always 0, an incorrect implementation might accidentally prevent staying in the same city. The solution explicitly allows transitions where from_city == to_city, ensuring staying is always legal.

A more subtle edge case involves future optimization. Sometimes the best immediate choice is not globally optimal. For example, taking fewer vacation days this week may allow access to a city with very large rewards later. Greedy approaches fail here because they only optimize locally. The DP solution correctly evaluates all possible reachable states week by week, guaranteeing the global optimum.

Another tricky situation occurs when certain cities offer extremely high vacation days but are unreachable from city 0. A buggy implementation may accidentally include them in calculations. Because the algorithm only transitions from previously reachable states, unreachable cities never contaminate the DP table.