Maximum Vacation Days - Practice Coding Problems

Maximum Vacation Days - Problem

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 where flights[i][j] == 1 means there is a flight from city i to city j, otherwise flights[i][j] == 0.
You totally have k weeks to travel. You can only take flights at most once per day and can only take flights on each week's Monday morning.
For each city, you can only have restricted vacation days in different weeks, given an n x k matrix called days where days[i][j] represents the maximum days you could take a vacation in city i in week j.

Input & Output

Example 1 — Basic Case

$ Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[4,2,2]]

› Output: 12

💡 Note: Optimal path: Week 0: fly to city 1 (6 days), Week 1: stay in city 1 (0 days), Week 2: fly to city 2 (2 days). Total: 6 + 0 + 2 = 8. Actually, better path: Week 0: fly to city 1 (6 days), Week 1: fly to city 2 (2 days), Week 2: stay in city 2 (2 days). Total: 6 + 2 + 2 = 10. Best path: Week 0: fly to city 1 (6 days), Week 1: fly to city 2 (2 days), Week 2: fly to city 1 (3 days) or Week 0: fly to city 2 (4 days), Week 1: fly to city 1 (0 days), Week 2: fly to city 1 (3 days) = 7. The actual maximum is 12.

Example 2 — No Flights Available

$ Input: flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[6,6,6]]

› Output: 3

💡 Note: No flights available, must stay in city 0 for all 3 weeks: 1 + 1 + 1 = 3 vacation days

Example 3 — All Cities Connected

$ Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[2,5,1],[4,1,3],[3,2,4]]

› Output: 13

💡 Note: Optimal: Week 0: fly to city 1 (4 days), Week 1: stay in city 1 (1 day), Week 2: fly to city 2 (4 days). Total: 4 + 1 + 4 = 9. Better: Week 0: fly to city 1 (4 days), Week 1: fly to city 0 (5 days), Week 2: fly to city 2 (4 days) = 13

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] ≤ 10³
flights[i][i] == 0 for all i

Visualization

Tap to expand

Understanding the Visualization

Input

Flight connections matrix and vacation days per city-week

Process

Use DP to find optimal travel schedule

Output

Maximum vacation days achievable

Key Takeaway

🎯 Key Insight: Use dynamic programming to track maximum vacation days achievable from each city-week combination, building the solution backwards from the final week.

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to use dynamic programming to track maximum vacation days achievable from each city-week state. The optimal approach uses bottom-up DP with time complexity O(n²k) and space O(nk), building the solution iteratively from the last week backwards.

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n²k)	O(nk)	Build solution iteratively from base cases
Memoization (Top-Down DP)	O(n²k)	O(nk)	Cache results to avoid redundant calculations
Brute Force Recursion	O(n^k)	O(k)	Try all possible travel routes recursively

Bottom-Up Dynamic Programming — Algorithm Steps

Initialize DP table with dimensions [weeks][cities]
Fill last week with vacation days for each city
For each previous week, compute max by considering all reachable cities
Return maximum value from week 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set base case: week k = 0 days

Fill Table

Work backwards from week k-1 to 0

Result

Answer is dp[0][0]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int flights[][3], int days[][3]) {
    int n = 3, k = 3;
    
    // dp[week][city] = max vacation days if we're in city at start of week
    int dp[4][3];
    
    // Initialize with -1
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = -1;
        }
    }
    
    // Base case: week k (no more weeks)
    for (int city = 0; city < n; city++) {
        dp[k][city] = 0;
    }
    
    // Fill DP table from week k-1 to 0
    for (int week = k - 1; week >= 0; week--) {
        for (int city = 0; city < n; city++) {
            // Try staying in current city
            dp[week][city] = max(dp[week][city], days[city][week] + dp[week + 1][city]);
            
            // Try flying to other cities
            for (int nextCity = 0; nextCity < n; nextCity++) {
                if (flights[city][nextCity] == 1) {
                    dp[week][city] = max(dp[week][city], days[nextCity][week] + dp[week + 1][nextCity]);
                }
            }
        }
    }
    
    return dp[0][0]; // Start at city 0, week 0
}

int main() {
    // Simplified parsing for demonstration
    int flights[3][3] = {{0,1,1},{1,0,1},{1,1,0}};
    int days[3][3] = {{1,3,1},{6,0,3},{4,2,2}};
    
    int result = solution(flights, days);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²k)

For each of k weeks and n cities, we check n possible previous cities

⚠ Quadratic Growth

Space Complexity

O(nk)

DP table stores n×k states for all city-week combinations

⚡ Linearithmic Space

15.6K Views

Medium Frequency

~35 min Avg. Time

542 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler