Maximum Points You Can Obtain from Cards

📋

Problem

Imagine you have a deck of cards with points on each card, and you want to maximize your score by picking cards only from the start or the end of the deck. How do you decide which cards to pick?

You are given an integer array 'cardPoints' of size n and an integer k. You can take cards from the beginning or the end of the array exactly k times. Your goal is to maximize the sum of the points of the cards you take. Return the maximum points you can obtain.

1 ≤ n ≤ 10^51 ≤ k ≤ n1 ≤ cardPoints[i] ≤ 10^4

Edge cases: k equals the length of the array → sum of all elementsk equals 1 → maximum of first or last elementAll elements are equal → sum is k times that element

</>

IDE

def maxScore(cardPoints: list[int], k: int) -> int:public int maxScore(int[] cardPoints, int k)int maxScore(vector<int>& cardPoints, int k)function maxScore(cardPoints, k)

def maxScore(cardPoints, k):
    # Write your solution here
    pass

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxScore(vector<int>& cardPoints, int k) {
    // Write your solution here
    return 0;
}

function maxScore(cardPoints, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: sum of first k cards onlyGreedy approach picking only from the start without considering picks from the end.✅ Enumerate all splits i in [0,k] and compute prefix[i] + suffix[k-i], then take max.

Wrong: sum of last k cards onlyGreedy approach picking only from the end without considering picks from the start.✅ Enumerate all splits i in [0,k] and compute prefix[i] + suffix[k-i], then take max.

Wrong: incorrect sum less than total when k == nOff-by-one error or missing base case for k equals array length.✅ Return sum(cardPoints) directly when k == len(cardPoints).

Wrong: incorrect output for empty input or k=0No base case handling for empty array or zero picks.✅ Return 0 immediately if cardPoints is empty or k is 0.

Wrong: time limit exceeded on large inputsBrute force or O(k^2) approach instead of O(n) sliding window.✅ Implement sliding window to find minimal sum subarray of length n-k in O(n).

✓

Test Cases

Try testing your solution on edge cases like empty arrays and single elements.

Consider tricky inputs that break greedy assumptions or off-by-one errors.

Prepare for large inputs by optimizing to O(n) time complexity.

t1_01basic

Input{"cardPoints":[1,2,3,4,5,6,1],"k":3}

Expected12

⏱ Performance - must finish in 2000ms

Take the last two cards (6,1) and the first card (1) for a total of 12 points.

💡 Try considering all ways to split k picks between the start and end of the array.

💡 Use prefix sums for the first i cards and suffix sums for the last k-i cards.

💡 Calculate max sum by iterating i from 0 to k and summing prefix[i] + suffix[k-i].

Why it failed: Incorrect output means the solution likely does not consider all combinations of picks from start and end. Fix by enumerating all splits i in [0,k] and summing prefix[i] + suffix[k-i].

✓ Correctly computes max points by checking all combinations of picks from start and end.

t1_02basic

Input{"cardPoints":[2,2,2],"k":2}

Expected4

⏱ Performance - must finish in 2000ms

Picking any two cards from start or end yields 4 points since all cards have value 2.

💡 Check if your solution handles cases where all card values are equal.

💡 Sum of any k cards from either end should be the same; verify your logic accounts for this.

💡 Ensure your code correctly sums prefix and suffix arrays and picks the maximum.

Why it failed: If output is less than 4, the solution likely misses cases where cards have equal values or does not correctly sum prefix and suffix arrays. Fix by verifying sums and max selection logic.

✓ Correctly handles uniform card values and sums to maximum points.

t2_01edge

Input{"cardPoints":[],"k":0}

Expected0

⏱ Performance - must finish in 2000ms

Empty array and k=0 means no cards can be taken, so max points is 0.

💡 Consider the case when the input array is empty.

💡 Check if your code handles k=0 and returns 0 without errors.

💡 Return 0 immediately if cardPoints is empty or k is 0.

Why it failed: If output is not 0, solution likely does not handle empty input or k=0 correctly. Fix by adding base case checks for empty array or zero picks.

✓ Correctly returns 0 for empty input or zero picks.

t2_02edge

Input{"cardPoints":[10],"k":1}

Expected10

⏱ Performance - must finish in 2000ms

Single element array with k=1 means picking the only card available, total 10 points.

💡 Test with the smallest non-empty array and k=1.

💡 Ensure your solution handles single-element arrays correctly.

💡 Return the single element value when k equals array length.

Why it failed: If output is not 10, solution likely mishandles single-element arrays or k=1. Fix by returning cardPoints[0] when n=1 and k=1.

✓ Correctly handles single-element arrays and returns the card value.

t2_03edge

Input{"cardPoints":[5,5,5,5,5],"k":5}

Expected25

⏱ Performance - must finish in 2000ms

k equals array length means taking all cards, sum is 5*5=25.

💡 Check if your solution handles the case when k equals the length of the array.

💡 Sum all elements when k == n.

💡 Return sum(cardPoints) directly if k == len(cardPoints).

Why it failed: If output is less than 25, solution likely does not handle k == n correctly. Fix by returning sum of all cards when k equals array length.

✓ Correctly returns sum of all cards when k equals array length.

t3_01corner

Input{"cardPoints":[100,1,1,1,100],"k":3}

Expected201

⏱ Performance - must finish in 2000ms

Optimal picks are first and last cards (100+100) plus one from middle (1), total 102 points.

💡 Beware of greedy approaches that pick only from one side.

💡 Try enumerating all splits of k picks between start and end.

💡 Use sliding window to find minimum sum subarray of length n-k to subtract from total.

Why it failed: If output is less than 102, solution likely uses a greedy approach picking only from one side. Fix by enumerating all splits or using sliding window to find minimal middle subarray.

✓ Correctly handles cases where optimal picks are split between start and end.

t3_02corner

Input{"cardPoints":[1,79,80,1,1,1,200,1],"k":3}

Expected202

⏱ Performance - must finish in 2000ms

Optimal picks are last card (1), first card (1), and the 200 near the end, total 201 points.

💡 Check if your solution confuses 0/1 knapsack with fixed picks from ends.

💡 Use sliding window to find minimal sum subarray of length n-k.

💡 Subtract minimal middle subarray sum from total sum to get max points.

Why it failed: If output is less than 201, solution may confuse problem with unbounded picks or knapsack. Fix by using sliding window to find minimal middle subarray sum and subtract from total.

✓ Correctly distinguishes fixed picks from ends and uses sliding window approach.

t3_03corner

Input{"cardPoints":[1,2,3,4,5,6,1],"k":7}

Expected22

⏱ Performance - must finish in 2000ms

k equals array length means taking all cards, sum is 22.

💡 Verify your code handles the exact boundary condition k == n.

💡 Return sum of all cards when k equals length of cardPoints.

💡 Avoid off-by-one errors in loops or indexing.

Why it failed: If output is less than 22, solution likely has off-by-one error or does not handle k == n correctly. Fix by returning sum(cardPoints) when k == n.

✓ Correctly handles exact boundary condition k == n.

t4_01performance

Input{"cardPoints":[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,9977,9976,9975,9974,9973,9972,9971,9970,9969,9968,9967,9966,9965,9964,9963,9962,9961,9960,9959,9958,9957,9956,9955,9954,9953,9952,9951,9950,9949,9948,9947,9946,9945,9944,9943,9942,9941,9940,9939,9938,9937,9936,9935,9934,9933,9932,9931,9930,9929,9928,9927,9926,9925,9924,9923,9922,9921,9920,9919,9918,9917,9916,9915,9914,9913,9912,9911,9910,9909,9908,9907,9906,9905,9904,9903,9902,9901,9900],"k":50}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and k=50 tests O(n) sliding window solution efficiency within 2 seconds.

💡 Brute force O(k^2) will time out on large inputs.

💡 Use sliding window to find minimal sum subarray of length n-k in O(n).

💡 Calculate total sum once and subtract minimal subarray sum for max points.

Why it failed: TLE indicates brute force or inefficient approach. Fix by implementing O(n) sliding window to find minimal middle subarray sum.

✓ Solution runs efficiently in O(n) time using sliding window.

Practice

1. Consider the following Python code implementing the sliding window with count matching optimization to find all anagrams of p in s. What is the final returned list when s = "cbaebabacd" and p = "abc"?

easy

A. [0, 1, 6]

B. [0, 6, 7]

C. [0, 6, 8]

D. [0, 6]

Solution

1. Step 1: Trace first window (indices 0 to 2)

   Substring "cba" is an anagram of "abc", so index 0 is added.

2. Step 2: Slide window and check matches

   Next valid anagram found at index 6 ("bac"). No other windows match all counts.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Known example output matches [0, 6] [OK]

Hint: Anagrams appear at indices 0 and 6 only [OK]

Common Mistakes:

• Including indices where substring is not full anagram
• Off-by-one errors in window boundaries

2. What is the time complexity of the optimal sliding window algorithm for counting the number of contiguous subarrays where the product of all elements is less than k in an array of length n?

medium

A. O(n²), because the inner while loop can run up to n times for each right pointer increment.

B. O(n), because each element is visited at most twice by the left and right pointers.

C. O(n log n), due to repeated division operations inside the while loop.

D. O(n), but requires O(n) extra space to store intermediate products.

Solution

1. Step 1: Analyze outer and inner loops

   The right pointer moves from 0 to n-1 once. The left pointer only moves forward when product ≥ k, also at most n times.

2. Step 2: Confirm total operations

   Each element is visited at most twice (once by right, once by left), so total operations are O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers each move forward at most n times -> O(n) [OK]

Hint: Two pointers each advance at most n times [OK]

Common Mistakes:

• Assuming inner loop runs n times per iteration -> O(n²)
• Confusing division cost as log n

3. Suppose you want to find the longest substring with at most k distinct characters, but now characters can be reused infinitely many times and the string is extremely long. Which modification to the sliding window approach is necessary to handle this efficiently?

hard

A. Use a frequency map with counts and shrink window when counts exceed k distinct characters, ignoring last seen positions

B. Maintain an ordered dictionary of last seen indices and shrink window as usual; no change needed

C. Use a frequency map and shrink the window only when distinct characters exceed k, ignoring last seen indices

D. Switch to a brute force approach since reuse breaks sliding window assumptions

Solution

1. Step 1: Understand reuse impact

   When characters can be reused infinitely, tracking last seen indices is insufficient; frequency counts are needed.

2. Step 2: Modify approach

   Use a frequency map to count occurrences and shrink window when distinct characters exceed k, ignoring last seen positions.

3. Step 3: Confirm efficiency

   This approach maintains O(n) time and handles reuse correctly.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency map with counts is required for reuse scenarios [OK]

Hint: Frequency counts needed when characters can be reused infinitely [OK]

Common Mistakes:

• Assuming last seen indices suffice for reuse
• Thinking brute force is necessary

4. Suppose the problem is modified so that characters in t can be reused unlimited times (i.e., the substring in s must contain at least one occurrence of each character in t, but counts do not matter). Which modification to the sliding window algorithm correctly solves this variant?

hard

A. Keep frequency counts and require window_count[c] >= t_count[c] for all c, same as original

B. Use brute force to check all substrings since counts no longer matter

C. Sort s and t and use two pointers to find minimal substring

D. Track only presence of characters from t in the window, increment have when a character appears at least once, decrement when it disappears

Solution

1. Step 1: Understand problem change

   Since counts do not matter, only presence of each character is required, so frequency counts can be replaced by boolean presence tracking.

2. Step 2: Modify sliding window logic

   Increment have when a character from t appears first time in window, decrement when it leaves. Shrink window when all characters are present.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Tracking presence instead of counts solves the reuse variant efficiently [OK]

Hint: Track presence, not counts, when duplicates don't matter [OK]

Common Mistakes:

• Using original count-based logic
• Assuming brute force is needed
• Sorting breaks substring order

5. Suppose the sliding window maximum problem is modified so that elements can be reused multiple times (i.e., the window can slide but elements may appear multiple times in the output). Which of the following statements about the monotonic deque approach is true?

hard

A. The monotonic deque approach fails because it assumes each element appears only once; a max-heap is required instead.

B. The monotonic deque approach must be modified to track counts of elements to handle reuse correctly.

C. The monotonic deque approach works without any changes since it only depends on indices.

D. The problem reduces to a different pattern; monotonic deque is not applicable and a segment tree is needed.

Solution

1. Step 1: Understand the reuse modification

   Allowing elements to be reused means the same element can contribute multiple times as the window slides, potentially overlapping.

2. Step 2: Analyze monotonic deque assumptions

   The original deque stores indices assuming each element appears once per position. To handle reuse, counts or frequency tracking is needed to maintain correctness.

3. Step 3: Evaluate other options

   Monotonic deque without modification fails; max-heap alone is inefficient; segment tree is overkill for this variant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Tracking counts allows correct max maintenance with reuse [OK]

Hint: Reuse breaks unique index assumption; track counts to fix [OK]

Common Mistakes:

• Assuming no changes needed for reuse
• Switching to max-heap without efficiency gain
• Thinking monotonic deque is inapplicable