DEV Community

Subramanya Chakravarthy
Subramanya Chakravarthy

Posted on

Maximum Points You Can Obtain from Cards - LeetCode

The question is a bit tricky, In programming terms we need to find sub-array such that you can draw maximum points

Sliding winndow algorithm is a useful technique whenever you need to find some substring or subarray. Here we need to find a subarray from the beginning and end

Explanation:

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

  1. [1,2,3,4,5,6,1] --> start = [1,2,3], end = [], max = 6
  2. [1,2,3,4,5,6,1] --> start = [1,2], end = [1], max = 6
  3. [1,2,3,4,5,6,1] --> start = [1], end = [6, 1], max = 8
  4. [1,2,3,4,5,6,1] --> start = [], end = [5, 6, 1], max = 12

Here's the algorithm

  1. Create these variables
    • leftWindow = k - 1, wondering why leftWindow is k - 1? it's because we need array indices values
    • leftSum = 0
    • rightWindow = cardPoints.length - 1
    • rightSum = 0
  2. Now Loop through the card array k times and add each value to the leftSum
  3. Let's assume leftSum is the maxSum max = leftSum
  4. Start sliding the window while leftWindow is > 0 then decrease the leftSum and increase the rightSum. check whether leftSum + rightSum is greater than max

Here's the solution

var maxScore = function(cardPoints, k) {
    let leftW = k - 1, 
        leftSum = 0, 
        rightW = cardPoints.length - 1, 
        rightSum = 0;

    for(let i = 0; i < k; i++) {
        leftSum += cardPoints[i];
    }

    let max = leftSum;

    while(leftW >= 0) {
        leftSum -= cardPoints[leftW];
        rightSum += cardPoints[rightW];

        leftW--;
        rightW--;

        max = Math.max(max, leftSum + rightSum);
    }

    return max;
};

Top comments (0)