{x}
blog image

Maximum Vacation Days

Solution Explanation:

This problem can be solved using dynamic programming. We want to find the maximum number of vacation days we can take over K weeks, considering flight availability and vacation days per city per week.

Approach:

We use a 2D DP array f where f[k][i] represents the maximum vacation days achievable by the end of week k if we are currently in city i.

  1. Initialization: f[0][0] = 0. We start at city 0 on Monday of week 0, having taken 0 vacation days. All other f[0][i] values are initialized to negative infinity, representing unreachable states.

  2. Iteration: We iterate through weeks (k from 1 to K) and cities (i from 0 to n-1). For each f[k][i], we consider two possibilities:

    • Staying in the same city: We can stay in city i from week k-1 to week k, adding the vacation days available in city i during week k (days[i][k-1]) to f[k-1][i].

    • Flying from another city: We check which cities j have flights to city i (flights[j][i] == 1). For each such city, we consider the maximum vacation days achieved by the end of week k-1 if we were in city j (f[k-1][j]). We add the vacation days in city i during week k (days[i][k-1]) to this value.

  3. Finding the Maximum: After iterating through all weeks and cities, we find the maximum value among f[K][i] for all cities i. This represents the maximum vacation days achievable by the end of week K.

Time Complexity Analysis:

The outer loop iterates K times (weeks), and the inner loops iterate n times (cities) each. The nested loop iterates n times in the worst case. Therefore, the total time complexity is O(n²K).

Space Complexity Analysis:

We use a DP array of size (K+1) x n. Therefore, the space complexity is O(nK).

Code Explanations (with slight improvements):

The provided code in different languages implements this DP approach. Here are some minor improvements and explanations:

Python3:

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        n = len(flights)
        K = len(days[0])
        #Use a large negative number instead of -inf for better clarity and performance in some cases.
        inf = float('-inf')
        dp = [[inf] * n for _ in range(K + 1)]  # More descriptive variable name
        dp[0][0] = 0
 
        for k in range(1, K + 1):
            for i in range(n):  # Iterate through destination cities
                for j in range(n): # Iterate through origin cities
                    if flights[j][i] == 1:  # Check flight availability
                        dp[k][i] = max(dp[k][i], dp[k-1][j] + days[i][k-1])
                # Consider staying in the same city (if this is better than flying in).
                dp[k][i] = max(dp[k][i], dp[k-1][i] + days[i][k-1] if k > 0 else days[i][k-1])
            
 
        return max(dp[K]) #Return the max vacation days across all cities in the final week

Java:

class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int n = flights.length;
        int K = days[0].length;
        int[][] dp = new int[K + 1][n]; //More descriptive variable name
 
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MIN_VALUE); //Use Integer.MIN_VALUE instead of a custom large negative number
        }
        dp[0][0] = 0;
 
        for (int k = 1; k <= K; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (flights[j][i] == 1) {
                        dp[k][i] = Math.max(dp[k][i], dp[k - 1][j] + days[i][k - 1]);
                    }
                }
                // Handle staying in the same city
                dp[k][i] = Math.max(dp[k][i], (k > 0 ? dp[k-1][i] : 0) + days[i][k-1]);
            }
        }
 
        int maxDays = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i) {
            maxDays = Math.max(maxDays, dp[K][i]);
        }
        return maxDays;
    }
}

C++:

class Solution {
public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        int n = flights.size();
        int K = days[0].size();
        vector<vector<int>> dp(K + 1, vector<int>(n, INT_MIN)); //More descriptive variable name and use of vectors
        dp[0][0] = 0;
 
        for (int k = 1; k <= K; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (flights[j][i] == 1) {
                        dp[k][i] = max(dp[k][i], dp[k - 1][j] + days[i][k - 1]);
                    }
                }
                //Handle staying in same city
                dp[k][i] = max(dp[k][i], (k > 0 ? dp[k-1][i] : 0) + days[i][k - 1]);
            }
        }
 
        int maxDays = INT_MIN;
        for (int i = 0; i < n; ++i) {
            maxDays = max(maxDays, dp[K][i]);
        }
        return maxDays;
    }
};

Go:

func maxVacationDays(flights [][]int, days [][]int) int {
    n, K := len(flights), len(days[0])
    dp := make([][]int, K+1)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = math.MinInt32 //Use math.MinInt32 instead of a custom large negative number.
        }
    }
    dp[0][0] = 0
 
    for k := 1; k <= K; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if flights[j][i] == 1 {
                    dp[k][i] = max(dp[k][i], dp[k-1][j]+days[i][k-1])
                }
            }
            //Handle staying in the same city.
            dp[k][i] = max(dp[k][i], (dp[k-1][i] + days[i][k-1]) )
 
        }
    }
 
    maxDays := math.MinInt32
    for i := 0; i < n; i++ {
        maxDays = max(maxDays, dp[K][i])
    }
    return maxDays
}
 
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

These improved versions use more descriptive variable names and handle the case of staying in the same city more explicitly, leading to more readable and potentially slightly more efficient code. The use of Integer.MIN_VALUE or math.MinInt32 avoids the need for manually defining a large negative number which can improve readability and reduce potential errors. The Python code now uses float('-inf') which is generally preferred over a manually set large negative number for better precision in floating point arithmetic.