mediumStackPattern: Mixed
Valid Subsequence Verification Solution
Problem Statement
Given two arrays, determine if one array representing a sequence of ingredients is a valid subsequence of another array representing a recipe, using a stack data structure.
Examples
Example 1:
Input:{"recipe":[1,2,3,4],"ingredients":[1,3]}
Output:true
Explanation: The ingredients sequence [1, 3] is a subsequence of the recipe [1, 2, 3, 4].
Example 2:
Input:{"recipe":[1,2,3,4],"ingredients":[4,3,2]}
Output:false
Explanation: The ingredients sequence [4, 3, 2] is not a subsequence of the recipe [1, 2, 3, 4].
Constraints
- 1 <= sequence length <= 100
- 1 <= recipe length <= 500
Time: O(n) Space: O(n)
The optimal approach involves using a stack data structure to keep track of the sequence elements that have been found in the recipe array so far, resulting in a time complexity of O(n). This approach is efficient and should be used to solve the problem.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.