Detect subsequence in array

Question

Given an array of integers and a subsequence, determine if the subsequence can be found within the array in the same order, but not necessarily consecutively. The function should return a boolean value indicating the presence of the subsequence. For example, given the array [1, 2, 3, 4, 5] and the subsequence [2, 4], the output should be true.

Codemia · Accepted Answer

This problem can be effectively solved using the **two pointers** technique. The reason this method applies here is that we need to check if the elements of the subsequence appear in the main array in the same order. We can maintain one pointer for the main array and another for the subsequence, iterating through the arrays simultaneously. This allows us to efficiently track the progress of matching elements without needing to use additional data structures or complex algorithms.

1. Initialize two pointers: `i` for the array and `j` for the subsequence, both starting at 0.
   2. Iterate through the main array until either pointer reaches its respective length:
      - If the current element of the array matches the current element of the subsequence (`array[i] == subsequence[j]`), increment `j` to check the next element of the subsequence.
      - Always increment `i` to continue scanning through the array.
   3. If `j` equals the length of the subsequence by the end of the loop, it means all elements of the subsequence were found in order, and we return `True`. Otherwise, return `False`.

**Example:** For the input `array = [1, 2, 3, 4, 5]` and `subsequence = [2, 4]`, we proceed as follows:
- Start with `i = 0`, `j = 0`: `1 != 2` → Increment `i`.
- `i = 1`, `j = 0`: `2 == 2` → Increment both `i` and `j`.
- `i = 2`, `j = 1`: `3 != 4` → Increment `i`.
- `i = 3`, `j = 1`: `4 == 4` → Increment both `i` and `j`.
- `i = 4`, `j = 2`: `j` equals the length of the subsequence, hence return `True`.

Here is the Python implementation for this specific problem:
```python
def is_subsequence(array, subsequence):
    i, j = 0, 0
    while i < len(array) and j < len(subsequence):
        if array[i] == subsequence[j]:
            j += 1
        i += 1
    return j == len(subsequence)
```
This code checks if all elements of `subsequence` are found in `array` in the correct order.

The time complexity of this solution is **O(n)**, where `n` is the length of the main array. This is because we potentially traverse the entire array once. The space complexity is **O(1)** since we are using a constant amount of extra space (only two pointers). This efficiency is particularly important given that the input array can be large.

1. **Empty Subsequence:** If the subsequence is empty (`subsequence = []`), the function should return `True`, as an empty subsequence is trivially found in any array.
2. **Array and Subsequence are Empty:** Both being empty should also return `True`.
3. **Subsequence Longer than Array:** If the subsequence is longer than the array (`subsequence = [1, 2, 3, 4, 5, 6]` and `array = [1, 2, 3]`), it should return `False`.
4. **Duplicates in Array:** If the array contains duplicates (e.g., `array = [1, 2, 2, 3]` and `subsequence = [2, 3]`), it should still return `True` as the order is maintained.
5. **Non-Existent Elements:** If the subsequence contains elements not present in the array (e.g., `array = [1, 2, 3]` and `subsequence = [4]`), it should return `False`.

Detect subsequence in array

Jump Trading

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Jump Trading Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string