Scale Engineer

Maximum Points You Can Obtain from Cards

Med
#1316Time: O(2^k). The recursion tree has a depth of `k`, and each node branches into two, resulting in `2^k` calls at the last level.Space: O(k). The depth of the recursion stack can go up to `k`.2 companies
Patterns
Sliding WindowPrefix Sum
Data structures
Array
Companies
FlipkartDE Shaw

Prompt

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 <= 105
  • 1 <= cardPoints[i] <= 104
  • 1 <= k <= cardPoints.length

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly models the problem statement. At each step, we have two choices: take a card from the left end or the right end. We need to make k such choices. A recursive function can explore all possible sequences of choices and find the one that yields the maximum score.

Algorithm

  • Define a recursive function findMaxScore(points, left, right, k).
  • Base Case: If k == 0, return 0.
  • Recursive Step:
    • scoreLeft = points[left] + findMaxScore(points, left + 1, right, k - 1).
    • scoreRight = points[right] + findMaxScore(points, left, right - 1, k - 1).
    • Return max(scoreLeft, scoreRight).
  • Initial call: findMaxScore(cardPoints, 0, n-1, k).

Walkthrough

We define a recursive function, say findMaxScore(points, left, right, k), which calculates the maximum score obtainable from the subarray points[left...right] by taking k more cards. The base case for the recursion is when k becomes 0, meaning we have taken the required number of cards. In this case, the score to be added is 0, so we return 0. In the recursive step, we explore the two possible moves:

  1. Take the card at the left index: The score for this choice is points[left] plus the result of the recursive call on the smaller subarray points[left + 1...right] with k-1 cards to take.
  2. Take the card at the right index: The score for this choice is points[right] plus the result of the recursive call on the smaller subarray points[left...right - 1] with k-1 cards to take. The function returns the maximum of these two scores. The initial call to this function would be findMaxScore(cardPoints, 0, cardPoints.length - 1, k). This method explores a binary tree of choices of depth k, leading to an exponential number of computations.
class Solution {    public int maxScore(int[] cardPoints, int k) {        return findMaxScore(cardPoints, 0, cardPoints.length - 1, k);    }     private int findMaxScore(int[] points, int left, int right, int k) {        // Base case: no more cards to take        if (k == 0) {            return 0;        }         // Option 1: Take the leftmost card        int takeLeft = points[left] + findMaxScore(points, left + 1, right, k - 1);         // Option 2: Take the rightmost card        int takeRight = points[right] + findMaxScore(points, left, right - 1, k - 1);         // Return the maximum of the two options        return Math.max(takeLeft, takeRight);    }}

Complexity

Time

O(2^k). The recursion tree has a depth of `k`, and each node branches into two, resulting in `2^k` calls at the last level.

Space

O(k). The depth of the recursion stack can go up to `k`.

Trade-offs

Pros

  • It's a straightforward translation of the problem's decision-making process.

  • Simple to conceptualize and implement.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' error for all but the smallest values of k.

Solutions

/** * @param {number[]} cardPoints * @param {number} k * @return {number} */ var maxScore =  function (cardPoints, k) {    const n = cardPoints.length;    let s = cardPoints.slice(-k).reduce((a, b) => a + b);    let ans = s;    for (let i = 0; i < k; ++i) {      s += cardPoints[i] - cardPoints[n - k + i];      ans = Math.max(ans, s);    }    return ans;  };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem