Maximum Points You Can Obtain from Cards
Medium
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:
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:
cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.
Example 3:
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.
How would you go about solving this problem? What are the time and space complexities?
Solution
Brute Force Approach
The most straightforward approach is to try all possible combinations of taking k cards from the beginning and end of the row. This involves iterating through all possible numbers of cards taken from the beginning (from 0 to k) and calculating the remaining cards to be taken from the end. The score for each combination is then calculated, and the maximum score is tracked.
Code (Python)
def max_score_brute_force(cardPoints, k):
n = len(cardPoints)
max_score = 0
for x in range(k + 1):
current_score = 0
# Take x cards from the beginning
for i in range(x):
current_score += cardPoints[i]
# Take k - x cards from the end
for i in range(k - x):
current_score += cardPoints[n - 1 - i]
max_score = max(max_score, current_score)
return max_score
Time Complexity
O(k^2) - The outer loop iterates k + 1 times, and the inner loops (for calculating the score) iterate a maximum of k times in total.
Space Complexity
O(1) - Constant extra space is used.
Optimal Solution: Sliding Window
A more efficient approach is to use a sliding window technique. Instead of trying all combinations of taking cards from the beginning and end, we can think about the problem as finding the minimum sum of a subarray of size n - k. We then subtract this minimum sum from the total sum of all card points to get the maximum score.
Algorithm
- Calculate the total sum of all card points.
- Find the minimum sum of a subarray of size
n - k. - Subtract the minimum subarray sum from the total sum to get the maximum score.
Code (Python)
def max_score_optimal(cardPoints, k):
n = len(cardPoints)
total_sum = sum(cardPoints)
window_size = n - k
current_sum = sum(cardPoints[:window_size])
min_sum = current_sum
for i in range(window_size, n):
current_sum += cardPoints[i] - cardPoints[i - window_size]
min_sum = min(min_sum, current_sum)
return total_sum - min_sum
Time Complexity
O(n) - We iterate through the array once to calculate the total sum and once to find the minimum subarray sum.
Space Complexity
O(1) - Constant extra space is used.
Edge Cases
- If
kis equal to the length ofcardPoints, then the maximum score is simply the sum of all card points. - If
cardPointsis empty orkis 0, the result is 0.
