Sweet And Savory

Tags

Sweet And Savory

Category

Arrays

Difficulty

Medium

Problem Statement

You are given an array of dish flavors where negative values represent sweet dishes and positive values represent savory dishes. You need to find one sweet and one savory dish whose combined flavor is as close to a given target as possible without exceeding it. If no valid pair exists, return [0, 0]. The target is always non-negative.

Intuition

After sorting the dishes, we can use a two-pointer technique with one pointer on the most negative (sweetest) dish and one on the most positive (most savory) dish. By moving the pointers inward based on whether the current sum is below or above the target, we efficiently explore candidate pairs.

Approach

  1. Sort the array.
  2. Place left at index 0 (most sweet) and right at the last index (most savory).
  3. Initialize bestPair = [0, 0] and bestDiff = infinity.
  4. While left < right and array[left] < 0 and array[right] > 0:
    • Compute sum = array[left] + array[right].
    • If sum <= target:
      • Compute diff = target - sum.
      • If diff < bestDiff, update bestDiff = diff and bestPair = [array[left], array[right]].
      • Move left rightward (increase the sum toward target).
    • Else (sum > target):
      • Move right leftward (decrease the sum toward target).
  5. Return bestPair.

Pseudocode

function sweetAndSavory(dishes, target):
    sort(dishes)
    left = 0
    right = length(dishes) - 1
    bestPair = [0, 0]
    bestDiff = infinity

    while left < right and dishes[left] < 0 and dishes[right] > 0:
        sum = dishes[left] + dishes[right]

        if sum <= target:
            diff = target - sum
            if diff < bestDiff:
                bestDiff = diff
                bestPair = [dishes[left], dishes[right]]
            left += 1
        else:
            right -= 1

    return bestPair

Time & Space Complexity

  • Time: O(n log n) — dominated by sorting. The two-pointer scan is O(n).
  • Space: O(1) — aside from the sort, only a constant number of variables are used.

Key Insights

  • The constraint that we need one sweet (negative) and one savory (positive) dish simplifies pointer management: left stays in the negative region and right in the positive region.
  • We only consider sums at or below the target (never exceeding), so we move left forward when the sum is too small and right backward when too large.
  • If sum == target, that is the best possible result and we can return immediately (though the algorithm handles this naturally).

Edge Cases

  • No sweet dishes or no savory dishes: no valid pair exists, return [0, 0].
  • Target is 0: we want the pair whose sum is the largest non-positive value (closest to zero from below).
  • All pairs exceed the target: return [0, 0].
  • Multiple pairs with the same best difference: the first one found during the sweep is returned.

Linked mentions