Maximum Points You Can Obtain from Cards

Medium

TikTok

0 views

Topics:

ArraysSliding Windows

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Constraints:

1 <= cardPoints.length <= 10⁵
1 <= cardPoints[i] <= 10⁴
1 <= k <= cardPoints.length

Maximum Points You Can Obtain from Cards

Medium

TikTok

0 views

Topics:

ArraysSliding Windows

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Constraints:

1 <= cardPoints.length <= 10⁵
1 <= cardPoints[i] <= 10⁴
1 <= k <= cardPoints.length

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 `cardPoints` array and the value of `k`? Can `k` ever be larger than the size of the `cardPoints` array?
Can the values in the `cardPoints` array be negative, zero, or only positive?
If `k` is 0 or the `cardPoints` array is empty, what should I return?
Are there any memory constraints that I should be aware of, given the size of the input?
If there are multiple combinations of cards that result in the same maximum sum, is any one of them acceptable?

Brute Force Solution

Approach

The brute force approach explores every conceivable combination of taking cards from the beginning or the end of the row. We simulate every possibility to find the best possible score. It's like trying every single hand you could make and then picking the best one.

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

Consider taking only cards from the beginning of the row.
Consider taking all possible combinations of cards from the beginning of the row, starting with one card, then two, then three, and so on, up to the maximum number of cards you can take.
For each of these 'beginning only' scenarios, calculate the total points.
Now, consider taking only cards from the end of the row and perform a similar process.
Next, consider taking a mix of cards. Start by taking one card from the beginning and the remaining from the end.
Then try taking two cards from the beginning and the remaining from the end.
Keep doing this, systematically shifting one card at a time from the end to the beginning, until you've exhausted all possible combinations of cards from both ends that meet the allowed number of cards to take.
For each of these mixed combinations, calculate the total points.
Compare the total points from all the 'beginning only', 'end only', and 'mixed' combinations you calculated.
Select the combination that yields the highest total points. This is your answer.

Code Implementation

def max_score_cards_brute_force(card_points, cards_to_take):
    max_score = 0

    # Check all possibilities by iterating through
    # possible combinations of taking from left and right
    for num_cards_from_left in range(cards_to_take + 1):
        current_score = 0
        
        # Calculate score from the left side
        for i in range(num_cards_from_left):
            current_score += card_points[i]

        # Calculate score from the right side
        for i in range(cards_to_take - num_cards_from_left):
            current_score += card_points[len(card_points) - 1 - i]

        # Maintain the maximum score
        max_score = max(max_score, current_score)

    # Edge case: If no cards are present, ensure
    # the returned score is zero
    if not card_points:
        return 0

    return max_score

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(k²) – The algorithm explores all possible combinations of taking cards from the beginning and end of the row. The outer loop iterates 'k' times representing the number of cards we can take. The inner loop implicitly iterates up to 'k' times, calculating the score for each possible combination of cards from the beginning and end (i cards from beginning and k-i cards from end). This results in roughly k * k/2 operations. Therefore, the time complexity is O(k²), where k is the number of cards to take.

Space Complexity

O(1) – The provided brute force approach primarily involves calculating sums for different combinations of cards. It does not explicitly mention the use of any auxiliary data structures like arrays, lists, or hash maps to store intermediate results or visited states. The algorithm uses a fixed number of variables to keep track of indices and maximum scores. Therefore, the space complexity is constant, independent of the number of cards (N).

Optimal Solution

Approach

The key insight is to focus on what *isn't* being taken rather than what *is*. Instead of trying to pick the best cards from both ends, identify the smallest set of cards to leave behind in the middle, which is much more efficient. We then find the smallest possible sum of cards left behind to get the maximum possible sum of cards we can obtain.

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

First, figure out the total sum of all the points on all the cards.
Next, realize that maximizing the points you get is the same as minimizing the points you leave behind.
Calculate the size of the 'window' of cards you'll be leaving in the middle. This window size will be based on how many cards you must choose.
Slide this window across all possible positions in the deck of cards.
Calculate the sum of the points within this window for each position.
Find the window position that has the smallest sum of points.
Subtract this smallest window sum from the total sum of all the cards. The result is the maximum points you can obtain.

Code Implementation

def max_score_sightseeing_pair(card_points, cards_to_take):
    total_points = sum(card_points)

    # Need to leave this many cards behind
    cards_to_leave = len(card_points) - cards_to_take

    current_window_sum = sum(card_points[:cards_to_leave])
    min_window_sum = current_window_sum

    # Slide the window to find the smallest sum
    for i in range(cards_to_leave, len(card_points)):
        current_window_sum += card_points[i] - card_points[i - cards_to_leave]
        min_window_sum = min(min_window_sum, current_window_sum)

    # Subtract the minimum we leave to get the maximum
    max_obtainable_points = total_points - min_window_sum

    return max_obtainable_points

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm first calculates the total sum of the card points, which takes O(n) time where n is the number of cards. It then calculates the size of the window to leave behind. Next, the algorithm iterates through the card array, sliding the window of a fixed size (n - k) where k is the number of cards to pick. Calculating the sum of the window's elements in each step and finding the minimum window sum takes O(n) time. Therefore, the overall time complexity is dominated by the single loop and the initial sum calculation, resulting in O(n).

Space Complexity

O(1) – The algorithm calculates the total sum of all cards and then uses a sliding window approach to find the minimum sum of a sub-array. It only stores a few variables such as the total sum, the window size, the current window sum, and the minimum window sum. These variables take up constant space regardless of the number of cards (N), therefore the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
cardPoints is null or empty	Return 0 because there are no cards to pick.
k is 0	Return 0 because no cards can be taken.
k is greater than the length of cardPoints	Return the sum of all elements in cardPoints as we can take all cards.
cardPoints contains negative numbers	The algorithm should correctly handle negative card points and find the maximum sum, potentially resulting in a negative maximum sum.
cardPoints contains only zeros	The algorithm should return 0 if k is less than or equal to the length of cardPoints.
Large array size and large values in cardPoints (potential integer overflow)	Use long instead of int to calculate the sum of card points to prevent integer overflow.
cardPoints contains extremely skewed distribution (e.g., one very large value, rest are small)	The sliding window/prefix sum approach correctly handles this scenario to find the optimal combination of cards.
k is equal to the length of the array.	Return the sum of all elements in the array.