mediumBinary SearchPattern: Mixed
Sequence Index Finder Solution
Problem Statement
Given a sorted array `elements` of length `n` and a target sequence `target` of length `m`, find the index of the first occurrence of the sequence in `elements`. If the sequence is not found, return -1.
Examples
Example 1:
Input:{"arr":[1,2,3,4,5,6],"seq":[2,3,4]}
Output:1
Explanation: The sequence [2, 3, 4] starts at index 1 in the array [1, 2, 3, 4, 5, 6]
Example 2:
Input:{"arr":[1,2,3,4,5,6],"seq":[7,8,9]}
Output:-1
Explanation: The sequence [7, 8, 9] is not found in the array [1, 2, 3, 4, 5, 6]
Constraints
- The input array arr will be sorted in ascending order.
- The target sequence seq will have a length m less than or equal to half the length of the input array arr.
- The sequence seq may contain duplicate elements.
Time: O(n) Space: O(m)
The optimized approach involves using binary search to find the first occurrence of the sequence in the array with a time complexity of O(n + m)
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.