LeetCode 568: Maximum Vacation Days Solution

Master LeetCode problem 568 (Maximum Vacation Days), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

568. Maximum Vacation Days

Hard

Array Dynamic Programming Matrix

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming with memoization. We will create a 2D array to store the maximum vacation days that can be accumulated up to each city for each week. We will iterate over each week and each city, and calculate the maximum vacation days that can be accumulated at that city for that week by considering the maximum vacation days accumulated at the previous city for the previous week plus the vacation days for the current city for the current week. We will update the values in the 2D array as we iterate through the weeks and cities.

At the end of the iteration, the maximum vacation days that can be accumulated at the last city for the last week will be our final result.

Algorithm:

Initialize a 2D array dp of size n x k where n is the number of cities and k is the number of weeks.
Initialize dp[0][0] to be equal to the vacation days at the first city for the first week.
Iterate over each week starting from the second week:
- For each city, calculate the maximum vacation days that can be accumulated at that city for that week:
  - For each previous city, calculate the maximum vacation days that can be accumulated at the previous city for the previous week and add the vacation days for the current city for the current week.
  - Update the value in dp if it is greater than the current value.
Return the maximum vacation days that can be accumulated at the last city for the last week.

Time Complexity:

The time complexity of this approach is O(n * k^2) where n is the number of cities and k is the number of weeks.

Space Complexity:

The space complexity is O(n * k) for the 2D array dp used for memoization.

: :

Solution Code

class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int n = flights.length;
        int k = days[0].length;
        
        int[][] dp = new int[n][k];
        dp[0][0] = days[0][0];
        
        for (int week = 1; week < k; week++) {
            for (int city = 0; city < n; city++) {
                dp[city][week] = dp[city][week - 1] + days[city][week];
                for (int prevCity = 0; prevCity < n; prevCity++) {
                    if (flights[prevCity][city] == 1) {
                        dp[city][week] = Math.max(dp[city][week], dp[prevCity][week - 1] + days[city][week]);
                    }
                }
            }
        }
        
        int maxVacation = 0;
        for (int city = 0; city < n; city++) {
            maxVacation = Math.max(maxVacation, dp[city][k - 1]);
        }
        
        return maxVacation;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 568 (Maximum Vacation Days)?

This page provides optimized solutions for LeetCode problem 568 (Maximum Vacation Days) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 568 (Maximum Vacation Days)?

The time complexity for LeetCode 568 (Maximum Vacation Days) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 568 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 568 in Java, C++, or Python.

Back to LeetCode Solutions