We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Points You Can Obtain from Cards

Number: 1538

Difficulty: Medium

Paid? No

Companies: Google, TikTok, Microsoft, Amazon, DE Shaw, Flipkart, Adobe

Problem Description

Given an array of integers cardPoints representing the points on each card arranged in a row, and an integer k, you need to pick exactly k cards from either the beginning or the end of the array. The goal is to maximize the total points obtained. You must decide which k cards to take to achieve the highest possible score.

Key Insights

  • Instead of choosing which k cards to take, think in reverse: find the contiguous subarray of length n - k (where n is the total number of cards) that has the minimum sum.
  • The maximal points you can obtain is the total sum of the cards minus the sum of the subarray that you did not choose.
  • A sliding window technique can efficiently find the minimum sum subarray of a given fixed length.
  • This approach changes a two-ended selection problem into a single contiguous subarray problem.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The idea is to first compute the total sum of the cardPoints array. If k equals the number of cards, then the answer is simply the total sum. Otherwise, since you are required to take k cards and the remaining cards form a contiguous block of length n - k, find that contiguous block with the minimum sum using the sliding window technique. Subtract this minimum window sum from the total sum, which gives the maximum points possible.

The algorithm uses the following steps:

  1. Compute the total sum of the array.
  2. Compute the sum of the first window of size n - k.
  3. Slide the window across the array while updating the current window sum and tracking the minimum window sum encountered.
  4. Subtract the minimum window sum from the total sum to obtain the maximum points obtainable by taking k cards from the ends.

Data structures used: variables for sum tracking; no additional data structures beyond constant space is required.

Code Solutions

# Function to calculate the maximum points obtainable
def maxScore(cardPoints, k):
    n = len(cardPoints)
    # If k equals the total number of cards, return the total sum of cardPoints
    if k == n:
        return sum(cardPoints)
    
    total_sum = sum(cardPoints)
    window_size = n - k  # Size of the subarray we are leaving behind
    
    # Compute the sum of the first window
    current_window_sum = sum(cardPoints[:window_size])
    min_window_sum = current_window_sum
    
    # Slide the window from index 1 to n - window_size
    for i in range(window_size, n):
        # Subtract the element going out of the window and add the element coming into the window
        current_window_sum += cardPoints[i] - cardPoints[i - window_size]
        # Keep track of the minimum sum we've seen in the window
        if current_window_sum < min_window_sum:
            min_window_sum = current_window_sum
            
    # Maximum points is the total sum minus the minimum window sum
    return total_sum - min_window_sum

# Example usage:
print(maxScore([1,2,3,4,5,6,1], 3))  # Output: 12
← Back to All Questions