#1423

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Maximum Points You Can Obtain from Cards

Maximize your score by selecting k cards from the beginning or end of the array using a sliding window approach.

Problem Statement

You are given an array of integers cardPoints, where each element represents the points of a card. In each step, you can pick one card from either the beginning or the end of the array, and you need to select exactly k cards. The goal is to maximize the sum of the points of the selected cards.

The optimal strategy is to find a subarray of length n - k (where n is the length of cardPoints) to remove, as the sum of the remaining cards will give the highest possible score. You must return the maximum score achievable.

Examples

Example 1

Input: cardPoints = [1,2,3,4,5,6,1], k = 3

Output: 12

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

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

You have to take all the cards. Your score is the sum of points of all cards.

Constraints

1 <= cardPoints.length <= 105
1 <= cardPoints[i] <= 104
1 <= k <= cardPoints.length

Solution Approach

Sliding Window

The main technique to solve this problem is the sliding window. First, calculate the total sum of the array. Then, use a sliding window of size n - k to find the subarray with the minimum sum. Subtract this minimum sum from the total sum to get the maximum possible score.

Prefix Sum

Using a prefix sum array helps efficiently compute the sum of any subarray. This allows the sliding window approach to be implemented in constant time for each shift, avoiding the need for recalculating sums from scratch.

Optimized Calculation

Rather than calculating the sum for every possible subarray, optimize the approach by updating the sliding window sum as you move it across the array. This ensures the solution runs in linear time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n) due to the sliding window approach, where n is the length of cardPoints. The space complexity is O(n) for storing the prefix sum array.

What Interviewers Usually Probe

Candidate understands sliding window technique and its applications in array-based problems.
Candidate is able to optimize the sum calculation using prefix sums.
Candidate shows awareness of both time and space complexities in their approach.

Common Pitfalls or Variants

Common pitfalls

Failing to properly calculate the sum of the remaining cards after removing a subarray.
Overlooking the need to use a sliding window of the correct size (n - k) for optimal performance.
Not handling edge cases where the array length is small or where k equals the length of the array.

Follow-up variants

Solve for the case where k is equal to the length of the array.
Explore alternate approaches using dynamic programming to solve the problem.
Find a way to optimize the solution for extremely large arrays (n approaching 100,000).

FAQ

What is the sliding window technique in this problem?

The sliding window technique is used to calculate the sum of a subarray of length n - k by sliding across the array and keeping track of the sum of the cards left behind.

How do I calculate the maximum score for this problem?

The maximum score is calculated by subtracting the sum of the minimum subarray (of length n - k) from the total sum of the array.

What is the time complexity of the sliding window approach?

The time complexity is O(n), as the sliding window only requires a single pass over the array.

What is the significance of the prefix sum array in this problem?

The prefix sum array allows for quick calculations of the sum of any subarray, optimizing the sliding window technique.

How can I optimize my solution for larger inputs?

Optimizing the solution involves using a sliding window and prefix sums to ensure the algorithm runs in linear time (O(n)).

terminal

Solution

Solution 1: Sliding Window

We can use a sliding window of length $k$ to simulate this process.

1

2

3

4

5

6

7

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        ans = s = sum(cardPoints[-k:])
        for i, x in enumerate(cardPoints[:k]):
            s += x - cardPoints[-k + i]
            ans = max(ans, s)
        return ans

Continue Practicing

#1248 count number of nice subarrays #1658 minimum operations to reduce x to zero #1703 minimum adjacent swaps for k consecutive ones