Valid Recipe Ingredient Sequence — Problem Statement & Solution Guide

StackMediumMixed

TimeO(N+M)

SpaceO(1)

Problem Description

Given two integer arrays recipeSteps and requiredSequence, determine whether requiredSequence appears as a subsequence of recipeSteps. A subsequence is formed by removing zero or more elements from recipeSteps without reordering the remaining elements. Return true if every element of requiredSequence can be matched to an element in recipeSteps in the same relative order, otherwise return false.

DSA Pattern Breakdown

"Valid Recipe Ingredient Sequence"

medium

WHY DOES IT MATTER?

The subsequence pattern is fundamental in string matching, log analysis, and sequence alignment. It teaches the importance of greedy strategies and single-pass algorithms, which are critical for optimizing performance in large-scale systems.

OPTIMIZATION CHALLENGE

The key insight is to avoid nested loops by using a single pointer for the target sequence and iterating through the source sequence once. This reduces the time complexity from O(N*M) to O(N+M).

REAL-WORLD CONNECTION

This pattern is analogous to verifying a sequence of events in a distributed system, such as checking if a specific order of API calls occurred in a user's session. It is also used in DNA sequence alignment and version control systems to detect changes.

In interviews, emphasize the greedy nature of the solution and why it is optimal. Mention that you must inspect every element in the source array in the worst case, so O(N+M) is the lower bound. Also, handle edge cases like empty sequences or missing elements.

COMPLEXITY AT A GLANCE

⏱ Time:O(N+M)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem of determining if one sequence is a subsequence of another is a classic linear scanning challenge. The naive approach involves nested loops, where for each element in the target sequence, we scan the source sequence from the beginning to find a match. This results in O(N*M) time complexity, which becomes prohibitive for large inputs (e.g., N=10^5, M=10^5). The optimal paradigm relies on a single-pass greedy strategy: we iterate through the source array once, maintaining a pointer to the current expected element in the target array. Whenever a match is found, we advance the target pointer. If the target pointer reaches the end of the target array, the subsequence exists. This reduces the time complexity to O(N+M), which is optimal as we must inspect every element in the source array at least once in the worst case.

Interview Questions on This Problem

Q1At a fintech platform, we need to verify if a user's transaction history contains a specific fraud pattern (a subsequence of transaction IDs). How would you design this check to handle millions of transactions efficiently?

I would use a single-pass greedy algorithm. I'll iterate through the transaction history once, maintaining an index for the fraud pattern. For each transaction, I check if it matches the current expected pattern element. If it does, I advance the pattern index. If the pattern index reaches the end, I flag the fraud. This runs in O(N+M) time and O(1) space, ensuring real-time processing even with large datasets.

Q2In a high-growth startup's log analysis system, we need to detect if a specific sequence of error codes appears in a user's session logs. How would you optimize this for memory-constrained edge devices?

I would implement the subsequence check using a single pointer for the error code sequence and iterate through the logs once. This approach uses O(1) extra space, which is critical for edge devices. The time complexity is O(N+M), which is acceptable for log analysis. I would also handle edge cases like empty sequences or missing elements gracefully.

Q3At a global product company, we need to verify if a user's action sequence matches a known phishing pattern. How would you extend this to handle multiple patterns simultaneously?

For multiple patterns, I would use a state machine or a trie-like structure to track the progress of each pattern. However, for a single pattern, the greedy single-pass approach is optimal. If patterns are dynamic, I would preprocess them into a finite automaton to allow O(1) state transitions per input element, reducing the per-pattern check to O(N) total.

Examples

Example 1

Input

recipeSteps = [5,1,22,25,6,8,10,12], requiredSequence = [1,6,10,12]

Output

true

Explanation: Traverse recipeSteps while looking for the next needed value from requiredSequence. The values 1,6,10,12 are found at indices 1,4,6,7 respectively, preserving order, so the result is true.

Example 2

Input

recipeSteps = [5,1,22,25,6,8,10,12], requiredSequence = [1,6,12,10]

Output

false

Explanation: The element 12 appears after 10 in recipeSteps (indices 7 vs 6). RequiredSequence demands 12 before 10, breaking the order, thus it is not a subsequence.

Example 3

Input

recipeSteps = [7,3,9,5], requiredSequence = [7,9,5,3]

Output

false

Explanation: Although all numbers exist in recipeSteps, the required order 7→9→5→3 cannot be satisfied because 3 occurs before 9 and 5 in the original array.

Constraints

1 <= recipeSteps.length <= 100000
0 <= requiredSequence.length <= recipeSteps.length
-10^9 <= recipeSteps[i] <= 10^9
-10^9 <= requiredSequence[i] <= 10^9

Optimal Approach & Strategy

Use a single pointer for requiredSequence and iterate through recipeSteps once. Advance the pointer when a match is found. This results in O(N+M) time complexity and O(1) space.

Brute Force Approach

Use nested loops: for each element in requiredSequence, scan recipeSteps from the beginning to find a match. This results in O(N*M) time complexity.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N+M)

/**
 * @param {number[]} recipeSteps
 * @param {number[]} requiredSequence
 * @return {boolean}
 */
function isSubsequence(recipeSteps, requiredSequence) {
    let j = 0;
    const n = requiredSequence.length;
    
    if (n === 0) return true;
    
    for (let i = 0; i < recipeSteps.length && j < n; i++) {
        if (recipeSteps[i] === requiredSequence[j]) {
            j++;
        }
    }
    
    return j === n;
}

// Driver code
const recipeSteps = [5, 1, 22, 25, 6, 8, 10, 12];
const requiredSequence = [1, 6, 10, 12];

const result = isSubsequence(recipeSteps, requiredSequence);
console.log(result);

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    bool isSubsequence(vector<int>& recipeSteps, vector<int>& requiredSequence) {
        int j = 0;
        int n = requiredSequence.size();
        
        if (n == 0) return true;
        
        for (int i = 0; i < recipeSteps.size() && j < n; i++) {
            if (recipeSteps[i] == requiredSequence[j]) {
                j++;
            }
        }
        
        return j == n;
    }
};

int main() {
    vector<int> recipeSteps = {5, 1, 22, 25, 6, 8, 10, 12};
    vector<int> requiredSequence = {1, 6, 10, 12};
    
    Solution sol;
    bool result = sol.isSubsequence(recipeSteps, requiredSequence);
    
    if (result) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    
    return 0;
}

import java.util.*;

class Solution {
    public boolean isSubsequence(int[] recipeSteps, int[] requiredSequence) {
        int j = 0;
        int n = requiredSequence.length;
        
        if (n == 0) return true;
        
        for (int i = 0; i < recipeSteps.length && j < n; i++) {
            if (recipeSteps[i] == requiredSequence[j]) {
                j++;
            }
        }
        
        return j == n;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] recipeSteps = {5, 1, 22, 25, 6, 8, 10, 12};
        int[] requiredSequence = {1, 6, 10, 12};
        
        Solution sol = new Solution();
        boolean result = sol.isSubsequence(recipeSteps, requiredSequence);
        
        System.out.println(result);
    }
}

from typing import List

class Solution:
    def isSubsequence(self, recipeSteps: List[int], requiredSequence: List[int]) -> bool:
        j = 0
        n = len(requiredSequence)
        
        if n == 0:
            return True
        
        for i in range(len(recipeSteps)):
            if j >= n:
                break
            if recipeSteps[i] == requiredSequence[j]:
                j += 1
        
        return j == n

if __name__ == "__main__":
    recipeSteps = [5, 1, 22, 25, 6, 8, 10, 12]
    requiredSequence = [1, 6, 10, 12]
    
    sol = Solution()
    result = sol.isSubsequence(recipeSteps, requiredSequence)
    print(result)

/**
 * @param {number[]} recipeSteps
 * @param {number[]} requiredSequence
 * @return {boolean}
 */
function isSubsequence(recipeSteps, requiredSequence) {
    let j = 0;
    const n = requiredSequence.length;
    
    if (n === 0) return true;
    
    for (let i = 0; i < recipeSteps.length && j < n; i++) {
        if (recipeSteps[i] === requiredSequence[j]) {
            j++;
        }
    }
    
    return j === n;
}

// Driver code
const recipeSteps = [5, 1, 22, 25, 6, 8, 10, 12];
const requiredSequence = [1, 6, 10, 12];

const result = isSubsequence(recipeSteps, requiredSequence);
console.log(result);

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.

Valid Recipe Ingredient Sequence Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Stack

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Valid Recipe Ingredient Sequence — 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