Detect subsequence in linked list

Question

Given a linked list and a sequence of integers, determine if the sequence is a subsequence of the values in the linked list. The function should return true if the subsequence exists and false otherwise. The input will consist of the head of the linked list and an array representing the subsequence to be checked.

Codemia · Accepted Answer

To determine if a given sequence of integers is a subsequence of a linked list, we can use the two-pointer technique. This approach is suitable here because we need to traverse the linked list while checking if each element of the sequence is found in order. The two pointers will help us iterate through both the linked list and the sequence concurrently, ensuring we respect the order of the elements in the sequence.

1. Initialize two pointers: one (`list_ptr`) for traversing the linked list starting from the head, and another (`seq_ptr`) for traversing the sequence starting from index 0.
2. Traverse the linked list using `list_ptr`. For each node's value in the linked list:
   - If the value matches the current value pointed to by `seq_ptr`, increment `seq_ptr`.
   - Always increment `list_ptr`.
3. If `seq_ptr` reaches the length of the sequence, it means all elements of the sequence have been found in the linked list in order, so return true.
4. If `list_ptr` reaches the end of the linked list and `seq_ptr` has not reached the end of the sequence, return false.

**Example:** For a linked list with values [1, 2, 3, 4, 5] and a sequence [2, 4], the algorithm will:
- Start with `list_ptr` at 1 and `seq_ptr` at 0 (value 2).
- Move to 2 (increment `seq_ptr` to 1).
- Move to 3 (not matching, continue).
- Move to 4 (increment `seq_ptr` to 2, which is the length of the sequence).
- Return true.

```python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def is_subsequence(head: ListNode, sequence: list) -> bool:
    list_ptr = head
    seq_ptr = 0
    seq_length = len(sequence)

while list_ptr:
        if seq_ptr < seq_length and list_ptr.val == sequence[seq_ptr]:
            seq_ptr += 1
        list_ptr = list_ptr.next

return seq_ptr == seq_length
```

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. This is because we traverse each node exactly once. The space complexity is O(1) since we only use a constant amount of extra space for the pointers. This is efficient given the problem's constraints.

1. **Empty Linked List**: If the linked list is empty (head is None) and the sequence is also empty, return true since an empty sequence is a subsequence of any list.
2. **Sequence Longer Than Linked List**: If the sequence length is greater than the number of nodes in the linked list, return false immediately as it's impossible to find a longer sequence in a shorter list.
3. **Single Element Matches**: If the linked list has one element and the sequence is a single element, ensure to handle cases where they may or may not match.
4. **Non-Sequential Matches**: Ensure that the algorithm correctly identifies that the order must be preserved, so a sequence that matches the list but in a different order should return false.

Detect subsequence in linked list

Grafana Labs

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

Grafana Labs 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