Spend Required for Gift Card

There are n products begin sold on the Amazon Online shopping app. The price of the ithproduct is price[i]. The developers at Amazon decided to give special gift cards to innovative customers. A gift card will be given if any customer buys a contiguous subsegment of products and at least 2 of the products have a matching price. Find the minimum amount of money a customer needs to spend in order to get the gift card. If is is not possible for any customer to get a gift card, return -1.

Constraints 02 1 <= n <= 5 . 10 ^ 5 1 <= price[i] <= 10 ^ 6, 0 <= i < n Samples 02 assert(findMinimumPrice([1, 2, 3, 1, 2, 1]) == 4) assert(findMinimumPrice([1, 2, 1, 2]) == 4) assert(findMinimumPrice([1, 100, 1, 7, 7]) == 14)

Here is an optimized Python solution to find the minimum price needed to get a gift card based on the problem constraints:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import sys

def findMinimumPrice(prices):

  n = len(prices)

  # Handle edge case
  if n < 2:
    return -1

  min_price = sys.maxsize

  prefix_sum = [0] * (n+1)

  for i in range(1, n+1):
    prefix_sum[i] = prefix_sum[i-1] + prices[i-1]

  for i in range(n-1):
    for j in range(i+1, n):
      
      price_range = prefix_sum[j+1] - prefix_sum[i]
      
      # Check if at least 2 matching prices  
      if (j-i+1 - len(set(prices[i:j+1]))) >= 2:
        min_price = min(min_price, price_range) 
        
  if min_price != sys.maxsize:  
    return min_price
  else:
    return -1

The key optimizations are:

  • Store prefix sums to efficiently compute range sums
  • Use a set to check for 2+ matching prices
  • Minimize comparisons needed

This reduces the runtime to O(n^2) while keeping O(n) space complexity.

The most optimal solution for this problem of finding the minimum price for a gift card with matching prices in O(n) time complexity is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def findMinimumPrice(prices):

  n = len(prices)
  min_price = float('inf')

  last_match = {}

  for i in range(n):

    if prices[i] in last_match:
      start = last_match[prices[i]]
      min_price = min(min_price, prices[start] + prices[i])

    last_match[prices[i]] = i

  if min_price == float('inf'):
    return -1
  
  return min_price

The key ideas are:

  • Use a hashmap to track the last index of each seen price

  • When a duplicate price is found, calculate segment price using stored index

  • This avoids nested loops, reducing time to O(n)

  • Space complexity is O(n) for the hashmap

By tracking last duplicate indices, we can linearly scan and immediately compute matching segment prices when a duplicate is found. This algorithm optimization avoids the quadratic nested loop solution.