Maximum Points You Can Obtain from Cards

🎯

Maximum Points You Can Obtain from Cards

mediumSLIDING_WINDOWAmazonGoogleFacebook

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?

💡 This problem is about choosing elements from either end of an array to maximize a sum. Beginners often struggle because the problem seems to require checking many combinations, but a clever insight reduces it to a sliding window problem.

📋

Problem Statement

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

💡

Example

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

Output12

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

Input"cardPoints = [2,2,2], k = 2"

Output4

Take any two cards, all have value 2, total 4.

Input"cardPoints = [9,7,7,9,7,7,9], k = 7"

Output55

Take all cards since k equals the array length.

• k equals the length of the array → sum of all elements
• k equals 1 → maximum of first or last element
• All elements are equal → sum is k times that element
• Array with large values and k small → picking ends carefully matters

⚠️

Common Mistakes

Recomputing sums inside loops without prefix sums

Leads to time limit exceeded errors

✅ Use prefix and suffix sums to compute sums in O(1)

Confusing the problem as picking any k cards instead of only from ends

Incorrect solutions that pick cards from the middle

✅ Remember the problem constraint: picks only from start or end

Sliding window size miscalculation (using k instead of n-k)

Wrong subarray chosen, incorrect answer

✅ Use window size = n - k to find minimum subarray to exclude

Not handling edge cases like k = n or k = 0

Runtime errors or wrong output

✅ Add checks or rely on algorithm correctness for these cases

🧠

Brute Force (Try All Combinations)

💡 This approach exists to understand the problem deeply by exploring all possible ways to pick cards from the start and end. It is slow but clarifies the problem constraints and what is being asked.

Intuition

Try every possible way to pick i cards from the start and k - i cards from the end, then calculate the sum for each combination and find the maximum.

Algorithm

1. Initialize max_points to 0.
2. For i from 0 to k:
3. Calculate sum of first i cards and last k - i cards.
4. Update max_points if current sum is greater.

💡 The algorithm is straightforward but inefficient because it recalculates sums repeatedly and tries all combinations.

</>

Code

def maxScore(cardPoints, k):
    n = len(cardPoints)
    max_points = 0
    for i in range(k + 1):
        left_sum = sum(cardPoints[:i])
        right_sum = sum(cardPoints[n - (k - i):])
        current = left_sum + right_sum
        if current > max_points:
            max_points = current
    return max_points

# Example usage
if __name__ == '__main__':
    print(maxScore([1,2,3,4,5,6,1], 3))  # Output: 12

Line Notes

n = len(cardPoints)Get the total number of cards to know array boundaries

for i in range(k + 1)Try all splits of picks between left and right

left_sum = sum(cardPoints[:i])Sum first i cards from the start

right_sum = sum(cardPoints[n - (k - i):])Sum last k-i cards from the end

public class Solution {
    public static int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int maxPoints = 0;
        for (int i = 0; i <= k; i++) {
            int leftSum = 0;
            for (int j = 0; j < i; j++) {
                leftSum += cardPoints[j];
            }
            int rightSum = 0;
            for (int j = n - (k - i); j < n; j++) {
                rightSum += cardPoints[j];
            }
            int current = leftSum + rightSum;
            if (current > maxPoints) {
                maxPoints = current;
            }
        }
        return maxPoints;
    }

    public static void main(String[] args) {
        System.out.println(maxScore(new int[]{1,2,3,4,5,6,1}, 3)); // 12
    }
}

Line Notes

int n = cardPoints.length;Store array length for indexing

for (int i = 0; i <= k; i++)Try all possible splits of picks

for (int j = 0; j < i; j++)Sum cards from the start for current split

for (int j = n - (k - i); j < n; j++)Sum cards from the end for current split

#include <iostream>
#include <vector>
using namespace std;

int maxScore(vector<int>& cardPoints, int k) {
    int n = cardPoints.size();
    int maxPoints = 0;
    for (int i = 0; i <= k; i++) {
        int leftSum = 0;
        for (int j = 0; j < i; j++) {
            leftSum += cardPoints[j];
        }
        int rightSum = 0;
        for (int j = n - (k - i); j < n; j++) {
            rightSum += cardPoints[j];
        }
        int current = leftSum + rightSum;
        if (current > maxPoints) {
            maxPoints = current;
        }
    }
    return maxPoints;
}

int main() {
    vector<int> cardPoints = {1,2,3,4,5,6,1};
    cout << maxScore(cardPoints, 3) << endl; // 12
    return 0;
}

Line Notes

int n = cardPoints.size();Get size of input vector

for (int i = 0; i <= k; i++)Iterate over all possible splits

for (int j = 0; j < i; j++)Sum first i cards

for (int j = n - (k - i); j < n; j++)Sum last k-i cards

function maxScore(cardPoints, k) {
    const n = cardPoints.length;
    let maxPoints = 0;
    for (let i = 0; i <= k; i++) {
        let leftSum = 0;
        for (let j = 0; j < i; j++) {
            leftSum += cardPoints[j];
        }
        let rightSum = 0;
        for (let j = n - (k - i); j < n; j++) {
            rightSum += cardPoints[j];
        }
        const current = leftSum + rightSum;
        if (current > maxPoints) {
            maxPoints = current;
        }
    }
    return maxPoints;
}

// Example usage
console.log(maxScore([1,2,3,4,5,6,1], 3)); // 12

Line Notes

const n = cardPoints.length;Store length of array for indexing

for (let i = 0; i <= k; i++)Try all splits of picks between left and right

for (let j = 0; j < i; j++)Sum cards from the start for current split

for (let j = n - (k - i); j < n; j++)Sum cards from the end for current split

⏱

Complexity

TimeO(k^2)

SpaceO(1)

For each i from 0 to k, sums of up to k elements are computed twice (start and end), resulting in O(k^2) time complexity.

💡 If n=100000 and k=50000, this approach would do billions of operations, which is too slow for interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and is a good starting point.

🧠

Prefix and Suffix Sum Arrays

💡 This approach improves brute force by precomputing prefix and suffix sums to avoid repeated summations, making the solution efficient enough for large inputs.

Intuition

Precompute sums from the start and from the end, then for each split i, sum prefix[i] and suffix[k - i] to get the total points quickly.

Algorithm

1. Compute prefix sums for the first k cards.
2. Compute suffix sums for the last k cards.
3. For i from 0 to k, calculate prefix[i] + suffix[k - i].
4. Return the maximum sum found.

💡 Precomputing sums avoids repeated summations and speeds up the solution significantly.

</>

Code

def maxScore(cardPoints, k):
    n = len(cardPoints)
    prefix = [0] * (k + 1)
    suffix = [0] * (k + 1)
    for i in range(k):
        prefix[i + 1] = prefix[i] + cardPoints[i]
        suffix[i + 1] = suffix[i] + cardPoints[n - 1 - i]
    max_points = 0
    for i in range(k + 1):
        current = prefix[i] + suffix[k - i]
        if current > max_points:
            max_points = current
    return max_points

# Example usage
if __name__ == '__main__':
    print(maxScore([1,2,3,4,5,6,1], 3))  # Output: 12

Line Notes

prefix = [0] * (k + 1)Initialize prefix sums array with zero for base case

suffix = [0] * (k + 1)Initialize suffix sums array similarly

prefix[i + 1] = prefix[i] + cardPoints[i]Build prefix sums cumulatively from the start

suffix[i + 1] = suffix[i] + cardPoints[n - 1 - i]Build suffix sums cumulatively from the end

public class Solution {
    public static int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int[] prefix = new int[k + 1];
        int[] suffix = new int[k + 1];
        for (int i = 0; i < k; i++) {
            prefix[i + 1] = prefix[i] + cardPoints[i];
            suffix[i + 1] = suffix[i] + cardPoints[n - 1 - i];
        }
        int maxPoints = 0;
        for (int i = 0; i <= k; i++) {
            int current = prefix[i] + suffix[k - i];
            if (current > maxPoints) {
                maxPoints = current;
            }
        }
        return maxPoints;
    }

    public static void main(String[] args) {
        System.out.println(maxScore(new int[]{1,2,3,4,5,6,1}, 3)); // 12
    }
}

Line Notes

int[] prefix = new int[k + 1];Create prefix sums array with extra space for zero base

int[] suffix = new int[k + 1];Create suffix sums array similarly

prefix[i + 1] = prefix[i] + cardPoints[i];Accumulate prefix sums from left

suffix[i + 1] = suffix[i] + cardPoints[n - 1 - i];Accumulate suffix sums from right

#include <iostream>
#include <vector>
using namespace std;

int maxScore(vector<int>& cardPoints, int k) {
    int n = cardPoints.size();
    vector<int> prefix(k + 1, 0);
    vector<int> suffix(k + 1, 0);
    for (int i = 0; i < k; i++) {
        prefix[i + 1] = prefix[i] + cardPoints[i];
        suffix[i + 1] = suffix[i] + cardPoints[n - 1 - i];
    }
    int maxPoints = 0;
    for (int i = 0; i <= k; i++) {
        int current = prefix[i] + suffix[k - i];
        if (current > maxPoints) {
            maxPoints = current;
        }
    }
    return maxPoints;
}

int main() {
    vector<int> cardPoints = {1,2,3,4,5,6,1};
    cout << maxScore(cardPoints, 3) << endl; // 12
    return 0;
}

Line Notes

vector<int> prefix(k + 1, 0);Initialize prefix sums vector with zeros

vector<int> suffix(k + 1, 0);Initialize suffix sums vector similarly

prefix[i + 1] = prefix[i] + cardPoints[i];Build prefix sums from left

suffix[i + 1] = suffix[i] + cardPoints[n - 1 - i];Build suffix sums from right

function maxScore(cardPoints, k) {
    const n = cardPoints.length;
    const prefix = new Array(k + 1).fill(0);
    const suffix = new Array(k + 1).fill(0);
    for (let i = 0; i < k; i++) {
        prefix[i + 1] = prefix[i] + cardPoints[i];
        suffix[i + 1] = suffix[i] + cardPoints[n - 1 - i];
    }
    let maxPoints = 0;
    for (let i = 0; i <= k; i++) {
        const current = prefix[i] + suffix[k - i];
        if (current > maxPoints) {
            maxPoints = current;
        }
    }
    return maxPoints;
}

// Example usage
console.log(maxScore([1,2,3,4,5,6,1], 3)); // 12

Line Notes

const prefix = new Array(k + 1).fill(0);Initialize prefix sums array with zeros

const suffix = new Array(k + 1).fill(0);Initialize suffix sums array similarly

prefix[i + 1] = prefix[i] + cardPoints[i];Accumulate prefix sums from the start

suffix[i + 1] = suffix[i] + cardPoints[n - 1 - i];Accumulate suffix sums from the end

⏱

Complexity

TimeO(k)

SpaceO(k)

Prefix and suffix sums are computed in O(k), and then a single loop of size k+1 finds the max sum, total O(k) time since k ≤ n.

💡 For n=100000 and k=50000, this approach does about 150000 operations, which is efficient for interviews.

Interview Verdict: Accepted

This approach is efficient and passes all test cases, making it a good solution to implement in interviews.

🧠

Sliding Window on the Middle Subarray

💡 This approach uses a clever insight: instead of picking k cards from the ends, find the minimum sum subarray of length n-k in the middle and subtract it from the total sum to get the maximum points.

Intuition

Total points are fixed. Removing a contiguous subarray of length n-k from the middle leaves k cards from the ends. Minimizing the middle subarray sum maximizes the points taken.

Algorithm

1. Calculate total sum of all cards.
2. Use a sliding window of size n-k to find the minimum sum subarray.
3. Subtract the minimum subarray sum from total sum.
4. Return the result as maximum points.

💡 This approach reduces the problem to a classic sliding window minimum sum problem, which is efficient and elegant.

</>

Code

def maxScore(cardPoints, k):
    n = len(cardPoints)
    total = sum(cardPoints)
    window_size = n - k
    current_sum = sum(cardPoints[:window_size])
    min_subarray_sum = current_sum
    for i in range(window_size, n):
        current_sum += cardPoints[i] - cardPoints[i - window_size]
        if current_sum < min_subarray_sum:
            min_subarray_sum = current_sum
    return total - min_subarray_sum

# Example usage
if __name__ == '__main__':
    print(maxScore([1,2,3,4,5,6,1], 3))  # Output: 12

Line Notes

total = sum(cardPoints)Calculate total points to use as base

window_size = n - kSize of subarray to exclude

current_sum = sum(cardPoints[:window_size])Initialize sliding window sum

current_sum += cardPoints[i] - cardPoints[i - window_size]Slide window by adding new and removing old element

public class Solution {
    public static int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int total = 0;
        for (int point : cardPoints) total += point;
        int windowSize = n - k;
        int currentSum = 0;
        for (int i = 0; i < windowSize; i++) {
            currentSum += cardPoints[i];
        }
        int minSubarraySum = currentSum;
        for (int i = windowSize; i < n; i++) {
            currentSum += cardPoints[i] - cardPoints[i - windowSize];
            if (currentSum < minSubarraySum) {
                minSubarraySum = currentSum;
            }
        }
        return total - minSubarraySum;
    }

    public static void main(String[] args) {
        System.out.println(maxScore(new int[]{1,2,3,4,5,6,1}, 3)); // 12
    }
}

Line Notes

int total = 0;Initialize total sum accumulator

for (int point : cardPoints) total += point;Sum all card points

int windowSize = n - k;Calculate size of subarray to exclude

currentSum += cardPoints[i] - cardPoints[i - windowSize];Update sliding window sum by removing left and adding right

#include <iostream>
#include <vector>
using namespace std;

int maxScore(vector<int>& cardPoints, int k) {
    int n = cardPoints.size();
    int total = 0;
    for (int point : cardPoints) total += point;
    int windowSize = n - k;
    int currentSum = 0;
    for (int i = 0; i < windowSize; i++) {
        currentSum += cardPoints[i];
    }
    int minSubarraySum = currentSum;
    for (int i = windowSize; i < n; i++) {
        currentSum += cardPoints[i] - cardPoints[i - windowSize];
        if (currentSum < minSubarraySum) {
            minSubarraySum = currentSum;
        }
    }
    return total - minSubarraySum;
}

int main() {
    vector<int> cardPoints = {1,2,3,4,5,6,1};
    cout << maxScore(cardPoints, 3) << endl; // 12
    return 0;
}

Line Notes

int total = 0;Initialize total sum variable

for (int point : cardPoints) total += point;Sum all elements in the vector

int windowSize = n - k;Calculate length of subarray to exclude

currentSum += cardPoints[i] - cardPoints[i - windowSize];Slide window by adding new and removing old element

function maxScore(cardPoints, k) {
    const n = cardPoints.length;
    const total = cardPoints.reduce((a, b) => a + b, 0);
    const windowSize = n - k;
    let currentSum = 0;
    for (let i = 0; i < windowSize; i++) {
        currentSum += cardPoints[i];
    }
    let minSubarraySum = currentSum;
    for (let i = windowSize; i < n; i++) {
        currentSum += cardPoints[i] - cardPoints[i - windowSize];
        if (currentSum < minSubarraySum) {
            minSubarraySum = currentSum;
        }
    }
    return total - minSubarraySum;
}

// Example usage
console.log(maxScore([1,2,3,4,5,6,1], 3)); // 12

Line Notes

const total = cardPoints.reduce((a, b) => a + b, 0);Sum all card points using reduce

const windowSize = n - k;Calculate size of subarray to exclude

for (let i = 0; i < windowSize; i++) { currentSum += cardPoints[i]; }Initialize sliding window sum

currentSum += cardPoints[i] - cardPoints[i - windowSize];Slide window by adding new and removing old element

⏱

Complexity

TimeO(n)

SpaceO(1)

We compute total sum once and use a sliding window of size n-k to find minimum subarray sum in O(n) time and O(1) space.

💡 For n=100000, this approach does about 100000 operations, which is very efficient and suitable for interviews.

Interview Verdict: Accepted

This is the optimal approach, combining insight and efficiency, and is the best solution to implement in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 The sliding window approach on the middle subarray is the best to code in interviews due to its optimal time and space complexity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(k^2)	O(1)	No	N/A	Mention only - never code
2. Prefix and Suffix Sums	O(k)	O(k)	No	N/A	Good for explaining optimization
3. Sliding Window on Middle Subarray	O(n)	O(1)	No	N/A	Code this approach in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to grasp the problem, then move to optimized solutions. Practice coding and explaining each step clearly.

How to Present

Clarify the problem constraints and what is being asked.Explain the brute force approach and its inefficiency.Introduce prefix and suffix sums to optimize summations.Present the sliding window approach on the middle subarray as the optimal solution.Code the optimal solution and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize naive solutions, and knowledge of sliding window techniques.

Common Follow-ups

• What if k is zero? → Return 0 as no cards are taken.
• Can you solve it if you can only pick from one end? → Yes, just sum first k cards.
• How to handle very large inputs efficiently? → Use O(n) sliding window approach.
• What if cardPoints contains negative values? → Sliding window still works but be careful with sums.

💡 These follow-ups test edge case handling, problem variations, and efficiency considerations.

🔍

Pattern Recognition

When to Use

1) You must pick exactly k elements from either end of an array. 2) You want to maximize or minimize sum. 3) The problem can be reframed as excluding a contiguous subarray. 4) Sliding window can find min/max subarray sums efficiently.

Signature Phrases

'You can take cards from the beginning or the end''Return the maximum points you can obtain'

NOT This Pattern When

Problems where you can pick cards from anywhere or without fixed k picks are different and may require DP or greedy.

Similar Problems

Maximum Sum of K Consecutive Elements - similar use of sliding windowMinimum Size Subarray Sum - sliding window for minimum sum subarraySliding Window Maximum - classic sliding window technique

Practice

1. Consider the following code snippet implementing the sliding window approach to find the maximum average subarray of size k. Given nums = [4, 2, 1, 7] and k = 2, what is the value of max_sum after the loop completes?

easy

A. 6

B. 7

C. 8

D. 9

Solution

1. Step 1: Initialize sums

   Initial window sum = nums[0] + nums[1] = 4 + 2 = 6, so max_sum = 6.

2. Step 2: Iterate through array

   i=2: current_sum = 6 + nums[2] - nums[0] = 6 + 1 - 4 = 3 (max_sum stays 6) i=3: current_sum = 3 + nums[3] - nums[1] = 3 + 7 - 2 = 8 (max_sum updated to 8)

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Max sum found is 8, which matches 8 [OK]

Hint: Track current_sum updates carefully at each iteration [OK]

Common Mistakes:

• Off-by-one errors in indices
• Confusing current_sum with max_sum

2. Consider the following Python function implementing the optimal sliding window approach to find the minimum length of a subarray containing duplicate cards. What is the returned value when calling minimumCardPickup([1, 2, 3, 2])?

def minimumCardPickup(cards):
    last_seen = {}
    left = 0
    min_len = float('inf')
    for right, card in enumerate(cards):
        if card in last_seen and last_seen[card] >= left:
            left = last_seen[card] + 1
        last_seen[card] = right
        if right - left + 1 > 1:
            min_len = min(min_len, right - left + 1)
    return min_len if min_len != float('inf') else -1

easy

A. 2

B. 4

C. -1

D. 3

Solution

1. Step 1: Trace iterations for input [1, 2, 3, 2]

   Indices: 0->1, 1->2, 2->3, 3->2. At right=3, card=2 is duplicate with last_seen[2]=1 ≥ left=0, so left moves to 2.

2. Step 2: Calculate min_len updates

   Subarray lengths considered: from indices 1 to 3 is length 3, but after left update, window is from 2 to 3 length 2, min_len updated to 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Minimum subarray with duplicate '2' is [3,2] length 2 [OK]

Hint: Update left pointer on duplicate to shrink window [OK]

Common Mistakes:

• Off-by-one error in window length
• Not updating left pointer correctly

3. What is the time complexity of the optimal sliding window solution for the Grumpy Bookstore Owner problem when given an input array of length n and window size X?

medium

A. O(n)

B. O(n * X)

C. O(n + X)

D. O(n log n)

Solution

1. Step 1: Analyze outer loop

   The code iterates over the array once to compute base satisfaction (O(n)).

2. Step 2: Analyze sliding window loop

   The sliding window moves from start to end once, updating sums in O(1) per step, total O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant-time updates -> O(n) [OK]

Hint: Sliding window updates in O(1) per step [OK]

Common Mistakes:

• Confusing with brute force O(n*X)
• Adding X to n instead of linear
• Assuming sorting needed

4. What is the time complexity of the optimal sliding window algorithm using an ordered dictionary to find the longest substring with at most k distinct characters, where n is the length of the string and k is the maximum distinct characters allowed?

medium

A. O(n * k)

B. O(n)

C. O(n log k)

D. O(n^2)

Solution

1. Step 1: Identify outer loop complexity

   The algorithm iterates over each character once, so the outer loop is O(n).

2. Step 2: Analyze operations inside loop

   OrderedDict operations (deletion and insertion) are O(1) amortized, and each character is added and removed at most once, so total is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each character processed once with O(1) ops -> O(n) [OK]

Hint: OrderedDict operations are O(1) amortized, total O(n) [OK]

Common Mistakes:

• Assuming O(n * k) due to nested loops
• Thinking ordered dictionary operations cost O(log k)

5. The following code attempts to implement the optimal sliding window approach to check if s2 contains a permutation of s1. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line checking if window_count[idx] == count[idx] to increment formed

B. Line computing required as sum of positive counts

C. Line decrementing window_count[left_idx] before adjusting formed

D. Line checking if len_s1 > len_s2 at start

Solution

1. Step 1: Identify bug in window shrinking logic

   The code decrements window_count[left_idx] before checking if it equals count[left_idx]. This causes incorrect formed count updates because the check should happen before decrement.

2. Step 2: Correct order of operations

   To fix, check if window_count[left_idx] == count[left_idx] before decrementing window_count[left_idx], then decrement and adjust formed accordingly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Formed count must reflect window state before decrement [OK]

Hint: Check order of decrement and formed adjustment in window shrink [OK]

Common Mistakes:

• Adjusting formed after decrementing counts
• Miscounting required matches