algoadvance

Leetcode 2706. Buy Two Chocolates

Problem Statement

You are given an integer array, prices, representing the prices of various chocolates in a store. You also have a certain amount of money in your wallet. You need to find out whether you can buy exactly two different chocolates such that the total cost does not exceed the amount of money you have. Return true if you can buy the chocolates and false otherwise.

Clarifying Questions

  1. Input Constraints:
    • What is the range of the prices in the prices array? (e.g., 1 to 1000)
    • What is the maximum length of the prices array?
    • What is the range of the money you have?
  2. Edge Cases:
    • What if the prices array has fewer than 2 elements?
    • Are the prices always positive integers?

For the sake of this solution, let’s assume:

Strategy

To solve this problem efficiently, we can use a two-pointer technique:

  1. Sort the prices array.
  2. Use two pointers: One at the start (left) and one at the end (right) of the sorted array.
  3. Sum Direction: Check the sum of the prices at these pointers:
    • If the sum is less than or equal to the amount of money, return true.
    • If the sum is greater, move the right pointer to the left to reduce the sum.
    • If the sum is less, move the left pointer to the right to increase the sum.
  4. Continue this until the left pointer is less than the right pointer.

The idea is to find any two distinct elements whose sum is less than or equal to the given amount of money.

Code

#include <iostream>
#include <vector>
#include <algorithm>

bool canBuyTwoChocolates(std::vector<int>& prices, int money) {
    int n = prices.size();
    // Early return if there are less than 2 chocolates to buy
    if (n < 2) {
        return false;
    }

    // Sort the price array
    std::sort(prices.begin(), prices.end());

    // Two pointers technique
    int left = 0;
    int right = n - 1;

    while (left < right) {
        int sum = prices[left] + prices[right];
        if (sum <= money) {
            return true; // Found two chocolates within the budget
        } else if (sum > money) {
            --right; // Decrease sum by moving right pointer to the left
        } else {
            ++left; // Increase sum by moving left pointer to the right
        }
    }

    // If we exit the loop, it means we couldn't find such a pair
    return false;
}

// Example to test the function
int main() {
    std::vector<int> prices = {12, 7, 22, 10, 5};
    int money = 17;

    if (canBuyTwoChocolates(prices, money)) {
        std::cout << "Yes, can buy two chocolates" << std::endl;
    } else {
        std::cout << "No, cannot buy two chocolates" << std::endl;
    }

    return 0;
}

Explanation

  1. Sorting: We sort the prices array to apply the two-pointer technique efficiently.
  2. Two Pointers Approach:
    • Initialize left at the beginning and right at the end of the sorted array.
    • Check the sum of elements at these indices.
    • Adjust pointers based on the sum compared to the given amount of money.

Time Complexity

Thus, the overall time complexity is (O(n \log n)), where (n) is the number of elements in the prices array. This is efficient for the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI