Maximum Points Tourist Can Earn

Medium

DE Shaw

1 view

Topics:

ArraysDynamic Programming

You are given two integers, n and k, along with two 2D integer arrays, stayScore and travelScore.

A tourist is visiting a country with n cities, where each city is directly connected to every other city. The tourist's journey consists of exactly k 0-indexed days, and they can choose any city as their starting point.

Each day, the tourist has two choices:

Stay in the current city: If the tourist stays in their current city curr during day i, they will earn stayScore[i][curr] points.
Move to another city: If the tourist moves from their current city curr to city dest, they will earn travelScore[curr][dest] points.

Return the maximum possible points the tourist can earn.

Example 1:

Input: n = 2, k = 1, stayScore = [[2,3]], travelScore = [[0,2],[1,0]]

Output: 3

Explanation:

The tourist earns the maximum number of points by starting in city 1 and staying in that city.

Example 2:

Input: n = 3, k = 2, stayScore = [[3,4,2],[2,1,2]], travelScore = [[0,2,1],[2,0,4],[3,2,0]]

Output: 8

Explanation:

The tourist earns the maximum number of points by starting in city 1, staying in that city on day 0, and traveling to city 2 on day 1.

Constraints:

1 <= n <= 200
1 <= k <= 200
n == travelScore.length == travelScore[i].length == stayScore[i].length
k == stayScore.length
1 <= stayScore[i][j] <= 100
0 <= travelScore[i][j] <= 100
travelScore[i][i] == 0

Maximum Points Tourist Can Earn

Medium

DE Shaw

1 view

Topics:

ArraysDynamic Programming

You are given two integers, n and k, along with two 2D integer arrays, stayScore and travelScore.

A tourist is visiting a country with n cities, where each city is directly connected to every other city. The tourist's journey consists of exactly k 0-indexed days, and they can choose any city as their starting point.

Each day, the tourist has two choices:

Stay in the current city: If the tourist stays in their current city curr during day i, they will earn stayScore[i][curr] points.
Move to another city: If the tourist moves from their current city curr to city dest, they will earn travelScore[curr][dest] points.

Return the maximum possible points the tourist can earn.

Example 1:

Input: n = 2, k = 1, stayScore = [[2,3]], travelScore = [[0,2],[1,0]]

Output: 3

Explanation:

The tourist earns the maximum number of points by starting in city 1 and staying in that city.

Example 2:

Input: n = 3, k = 2, stayScore = [[3,4,2],[2,1,2]], travelScore = [[0,2,1],[2,0,4],[3,2,0]]

Output: 8

Explanation:

The tourist earns the maximum number of points by starting in city 1, staying in that city on day 0, and traveling to city 2 on day 1.

Constraints:

1 <= n <= 200
1 <= k <= 200
n == travelScore.length == travelScore[i].length == stayScore[i].length
k == stayScore.length
1 <= stayScore[i][j] <= 100
0 <= travelScore[i][j] <= 100
travelScore[i][i] == 0

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `points` array and the value of `max_distance`?
Can the values in the `points` array be negative?
If no locations can be reached from the starting location (location 0), what value should I return?
Are the location indices always sequential starting from 0?
Is it possible for `max_distance` to be zero?

Brute Force Solution

Approach

The brute force approach explores every single possible path the tourist could take through all the available locations. We calculate the total points earned for each of these paths. Finally, we choose the path that yields the highest total points.

Here's how the algorithm would work step-by-step:

Start by considering every location as a potential starting point for the tourist.
From each starting location, explore every possible next location the tourist could visit.
Continue exploring all possible sequences of locations the tourist can visit, making sure the tourist never visits the same location twice within a single trip.
For each complete trip (a valid sequence of locations), calculate the total points the tourist would earn.
Compare the total points earned from all the different possible trips.
Select the trip that provides the maximum total points. This is the optimal solution found by exhaustively checking every possibility.

Code Implementation

def maximum_points_tourist_brute_force(points):
    number_of_locations = len(points)
    maximum_points = 0

    def explore_paths(current_location, visited_locations, current_points):
        nonlocal maximum_points

        visited_locations = set(visited_locations)
        visited_locations.add(current_location)

        current_points += points[current_location]

        # Update maximum points found so far.
        maximum_points = max(maximum_points, current_points)

        # Explore all possible next locations.
        for next_location in range(number_of_locations):
            if next_location not in visited_locations:

                # Recursively explore the path from the next location.
                explore_paths(next_location, list(visited_locations), current_points)

    # Iterate through each location as a potential starting point.
    for start_location in range(number_of_locations):

        # Initiate exploration from the starting location.
        explore_paths(start_location, [], 0)

    return maximum_points

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n!) – The algorithm explores all possible paths the tourist can take through n locations. Starting from each location, it tries all possible next locations, and so on, ensuring no location is visited twice in a trip. This generates all permutations of the locations. The number of permutations of n items is n! (n factorial). Therefore, the time complexity is O(n!).

Space Complexity

O(N) – The brute force approach uses recursion to explore all possible paths. Since the tourist never visits the same location twice within a single trip, the maximum depth of the recursion is N, where N is the number of locations. Each recursive call requires a stack frame to store local variables and the return address. Therefore, the maximum space used by the call stack is proportional to N, resulting in O(N) space complexity. We also need to keep track of visited locations. This can be achieved through an auxiliary data structure (e.g., a boolean array) of size N, which also contributes to O(N) space.

Optimal Solution

Approach

The key to maximizing points is realizing that we can solve this problem sequentially. Instead of trying every combination of routes, we make the best decision at each location, knowing it leads to the overall best score. This is similar to planning a road trip where each stop is chosen to maximize your enjoyment.

Here's how the algorithm would work step-by-step:

Imagine you are the tourist and you are currently at one city.
Look at all the cities you can reach directly from your current city.
For each reachable city, calculate the total points you would have if you went there.
From all the reachable cities, select the one that gives you the highest total points (the points of the city itself plus the points you already have).
Move to that city.
Repeat steps 2-5 until you reach the final city. The points accumulated at the final city is the maximum points the tourist can earn.

Code Implementation

def maximum_points_tourist_can_earn(points, paths, start_city, end_city):
    number_of_cities = len(points)

    maximum_points = [float('-inf')] * number_of_cities
    maximum_points[start_city] = points[start_city]

    visited = [False] * number_of_cities

    current_city = start_city

    while not visited[end_city]:

        visited[current_city] = True

        # Iterate over all possible next cities.
        for next_city in range(number_of_cities):
            if paths[current_city][next_city] == 1 and not visited[next_city]:

                # Check if path exists and is unvisited
                new_points = maximum_points[current_city] + points[next_city]

                # Choose the path that yields the highest score.
                if new_points > maximum_points[next_city]:
                    maximum_points[next_city] = new_points

        best_next_city = -1
        best_next_city_points = float('-inf')

        # Find the unvisited city with the highest points
        for city_index in range(number_of_cities):
            if not visited[city_index] and maximum_points[city_index] > best_next_city_points:
                best_next_city = city_index
                best_next_city_points = maximum_points[city_index]

        if best_next_city == -1:
            break

        current_city = best_next_city

    return maximum_points[end_city]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m) – The provided algorithm iterates through cities sequentially, making a locally optimal decision at each step. Let n be the number of cities and m be the maximum number of cities reachable from any given city. In the worst case, for each of the n cities, the algorithm needs to examine all m reachable cities to find the one yielding the maximum score. Thus, the total number of operations is approximately n * m, leading to a time complexity of O(n*m).

Space Complexity

O(1) – The algorithm described makes decisions sequentially at each city, only keeping track of the current maximum points. It doesn't mention using any auxiliary data structures like lists, hash maps, or recursion. Therefore, the space used is constant and independent of the number of cities or connections, N. Only a few variables to store temporary point values might be needed, resulting in constant auxiliary space.

Edge Cases

Case	How to Handle
points array is null or empty	Return 0 if points is null or empty, as there are no locations to visit.
max_distance is 0	Return points[0] if max_distance is 0, as the tourist can only stay at the starting location.
points array has only one element	Return points[0] if points has only one element, as that's the only location.
All points are 0	Return 0, as the tourist cannot earn any points regardless of the path taken.
All points are negative	Use dynamic programming approach to find the maximum sum, even if all values are negative, the algorithm chooses the least negative values.
max_distance is larger than the array length	Iterate through the entire array, as the tourist can reach any location from the starting point.
Large input size that could cause recursion depth issues	Use dynamic programming (DP) with memoization instead of recursion to avoid stack overflow errors.
Integer overflow when summing points	Use a data type with larger capacity (e.g., long) to store the accumulated points.