Optimal Recipe Combination — Problem Statement & Solution Guide

Two PointersMediumMixed

TimeO(n)

SpaceO(1)

Problem Description

You are given an array flavor of integers representing the taste profile of a sequence of ingredients in a culinary pipeline. A positive integer denotes a sweet ingredient, while a negative integer denotes a savory ingredient. Zero values are considered neutral and do not contribute to either category.

Your task is to determine the minimum length of a contiguous subarray that contains at least one sweet ingredient and at least one savory ingredient. If no such subarray exists in the given sequence, return -1.

The solution must efficiently scan the sequence to identify the shortest window satisfying the dual-condition requirement, leveraging the properties of contiguous segments and sign transitions.

DSA Pattern Breakdown

"Optimal Recipe Combination"

medium

WHY DOES IT MATTER?

The two‑pointer pattern is essential for any problem that asks for the smallest (or largest) contiguous segment meeting a monotonic condition, because it transforms a quadratic search into a linear sweep.

OPTIMIZATION CHALLENGE

Recognizing that once the window satisfies the sign requirement, moving the left pointer inward can only improve (or keep) the length, allowing us to discard elements without re‑examining them, which guarantees each element is processed a constant number of times.

REAL-WORLD CONNECTION

Think of a conveyor belt where you need to pick the shortest batch that contains both a sweet and a savory ingredient before packaging – you slide a start and end marker along the belt, expanding to include missing flavors and contracting to discard excess items.

During an interview, keep two simple counters (posCount, negCount) and update them as you move the pointers; avoid recomputing counts from scratch – this tiny detail often differentiates a clean O(n) solution from a hidden O(n^2) trap.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem reduces to finding the shortest contiguous segment that simultaneously satisfies two opposite sign constraints – at least one positive (sweet) and at least one negative (savory) element. A naïve solution would enumerate every possible subarray, checking the sign condition for each, leading to O(n^2) time which quickly becomes infeasible for large n (10^5 or more). The optimal paradigm leverages the two‑pointer (sliding window) technique: maintain a window [left,right] and expand right until the window becomes valid (contains both signs), then contract left to shrink the window while preserving validity, updating the best length each time. Because each pointer moves at most n steps, the overall runtime is linear, O(n), and only constant extra space is required for counters of positive and negative occurrences.

Interview Questions on This Problem

Q1How would you modify the solution if the requirement changed to contain at least k sweet and l savory ingredients?

Maintain two counters for sweet and savory counts inside the window; expand right until both counters reach k and l respectively, then shrink left while the condition still holds, updating the minimum length. The algorithm remains O(n) because each pointer still moves at most n times.

Q2Can this problem be solved using a prefix‑sum and binary search approach? If so, what would be the trade‑offs?

Yes – compute prefix sums of sign counts and for each index perform a binary search for the earliest index where both counts have increased enough. This yields O(n log n) time and O(n) space, which is slower than the linear two‑pointer method but useful when the array is immutable and many queries are asked.

Q3In a distributed system where the ingredient stream is sharded across nodes, how would you compute the global minimum subarray length?

Each node runs the two‑pointer algorithm locally to find its best candidate and also records the smallest prefix and suffix windows that contain both signs. A coordinator then merges these edge windows across node boundaries to consider subarrays that span shards, yielding the global optimum with O(total n) work and minimal communication.

Examples

Example 1

Input

flavor = [5, -3, 2, -8, 1]

Output

Explanation: The subarray [-3, 2] has length 2 and contains one savory (-3) and one sweet (2). Similarly, [2, -8] and [-8, 1] also have length 2. No subarray of length 1 can contain both types. Thus, the minimum length is 2.

Example 2

Input

flavor = [10, 20, 30, 40]

Output

-1

Explanation: All elements are positive (sweet). There are no savory (negative) elements in the array. Therefore, no subarray can contain both sweet and savory ingredients. Return -1.

Example 3

Input

flavor = [-1, -2, -3, 4, 5, 6]

Output

Explanation: The transition from savory to sweet occurs between index 2 (-3) and index 3 (4). The subarray [-3, 4] has length 2 and contains both types. This is the shortest possible valid subarray. Return 2.

Example 4

Input

flavor = [7, -1, 0, 0, -5, 3]

Output

Explanation: Zeros are neutral and do not count as sweet or savory. The subarray [-1, 0] does not qualify because 0 is not sweet. However, the subarray [-5, 3] at indices 4 and 5 has length 2 and contains one savory (-5) and one sweet (3). Also, [-1, 0, 0, -5] is longer. The minimal valid window is length 2. Return 2.

Constraints

1 <= flavor.length <= 10^5
-10^9 <= flavor[i] <= 10^9
flavor[i] != 0 is not guaranteed; zeros may be present
The time complexity must be O(n) where n is the length of the array
The space complexity must be O(1)

Optimal Approach & Strategy

Use two pointers to maintain a sliding window, expanding right until both signs appear, then contracting left while preserving validity, updating the best length – O(n) time.

Brute Force Approach

Check every possible subarray, count positives and negatives, and keep the shortest that satisfies the condition – O(n^2) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} flavor
 * @return {number}
 */
var minLength = function(flavor) {
    const n = flavor.length;
    if (n < 2) return -1;
    
    let left = 0;
    let minLen = Infinity;
    let posCount = 0;
    let negCount = 0;
    
    for (let right = 0; right < n; right++) {
        if (flavor[right] > 0) posCount++;
        else if (flavor[right] < 0) negCount++;
        
        while (posCount > 0 && negCount > 0) {
            minLen = Math.min(minLen, right - left + 1);
            if (flavor[left] > 0) posCount--;
            else if (flavor[left] < 0) negCount--;
            left++;
        }
    }
    
    return minLen === Infinity ? -1 : minLen;
};

// Example usage
const flavor = [5, -3, 2, -8, 1];
console.log(minLength(flavor));

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

class Solution {
public:
    int minLength(vector<int>& flavor) {
        int n = flavor.size();
        if (n < 2) return -1;
        
        int left = 0;
        int minLen = INT_MAX;
        int posCount = 0;
        int negCount = 0;
        
        for (int right = 0; right < n; right++) {
            if (flavor[right] > 0) posCount++;
            else if (flavor[right] < 0) negCount++;
            
            while (posCount > 0 && negCount > 0) {
                minLen = min(minLen, right - left + 1);
                if (flavor[left] > 0) posCount--;
                else if (flavor[left] < 0) negCount--;
                left++;
            }
        }
        
        return minLen == INT_MAX ? -1 : minLen;
    }
};

int main() {
    vector<int> flavor = {5, -3, 2, -8, 1};
    Solution sol;
    cout << sol.minLength(flavor) << endl;
    return 0;
}

import java.util.*;

class Solution {
    public int minLength(int[] flavor) {
        int n = flavor.length;
        if (n < 2) return -1;
        
        int left = 0;
        int minLen = Integer.MAX_VALUE;
        int posCount = 0;
        int negCount = 0;
        
        for (int right = 0; right < n; right++) {
            if (flavor[right] > 0) posCount++;
            else if (flavor[right] < 0) negCount++;
            
            while (posCount > 0 && negCount > 0) {
                minLen = Math.min(minLen, right - left + 1);
                if (flavor[left] > 0) posCount--;
                else if (flavor[left] < 0) negCount--;
                left++;
            }
        }
        
        return minLen == Integer.MAX_VALUE ? -1 : minLen;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] flavor = {5, -3, 2, -8, 1};
        Solution sol = new Solution();
        System.out.println(sol.minLength(flavor));
    }
}

from typing import List

class Solution:
    def min_length(self, flavor: List[int]) -> int:
        n = len(flavor)
        if n < 2:
            return -1
        
        left = 0
        min_len = float('inf')
        pos_count = 0
        neg_count = 0
        
        for right in range(n):
            if flavor[right] > 0:
                pos_count += 1
            elif flavor[right] < 0:
                neg_count += 1
            
            while pos_count > 0 and neg_count > 0:
                min_len = min(min_len, right - left + 1)
                if flavor[left] > 0:
                    pos_count -= 1
                elif flavor[left] < 0:
                    neg_count -= 1
                left += 1
        
        return -1 if min_len == float('inf') else min_len

if __name__ == "__main__":
    flavor = [5, -3, 2, -8, 1]
    sol = Solution()
    print(sol.min_length(flavor))

/**
 * @param {number[]} flavor
 * @return {number}
 */
var minLength = function(flavor) {
    const n = flavor.length;
    if (n < 2) return -1;
    
    let left = 0;
    let minLen = Infinity;
    let posCount = 0;
    let negCount = 0;
    
    for (let right = 0; right < n; right++) {
        if (flavor[right] > 0) posCount++;
        else if (flavor[right] < 0) negCount++;
        
        while (posCount > 0 && negCount > 0) {
            minLen = Math.min(minLen, right - left + 1);
            if (flavor[left] > 0) posCount--;
            else if (flavor[left] < 0) negCount--;
            left++;
        }
    }
    
    return minLen === Infinity ? -1 : minLen;
};

// Example usage
const flavor = [5, -3, 2, -8, 1];
console.log(minLength(flavor));

Asked in Top Tech Interviews

Flipkart

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Optimal Recipe Combination Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Two Pointers

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Optimal Recipe Combination — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor