Find longest subsequence in linked list

Question

Given a singly linked list, write a function to find the longest increasing subsequence of its elements. The function should return the length of this subsequence. The input will be the head node of the linked list, and the output should be an integer representing the length of the longest increasing subsequence.

Codemia · Accepted Answer

To find the longest increasing subsequence (LIS) in a singly linked list, we can leverage dynamic programming (DP). The problem is essentially about identifying the longest sequence of values that are sorted in increasing order. The key pattern here is that for each element in the linked list, we need to compare it with all previous elements to determine if it can extend any existing increasing subsequence. This lends itself well to a DP approach where we maintain an array to store the length of the longest increasing subsequence at each position.

1. Initialize a list `dp` where `dp[i]` will store the length of the longest increasing subsequence that ends with the element at index `i` of the linked list.
2. Set each element of `dp` to 1 because each element is a subsequence of length 1 by itself.
3. Traverse the linked list with two nested loops:
   - The outer loop `i` goes from 0 to n-1 (the length of the linked list).
   - The inner loop `j` goes from 0 to i-1. For each `i`, check if the value at `i` is greater than the value at `j` (i.e., `list[i] > list[j]`). If it is, then update `dp[i]` as `dp[i] = max(dp[i], dp[j] + 1)`, meaning we can extend the subsequence that ends at `j` by including the element at `i`.
4. Finally, the length of the longest increasing subsequence will be the maximum value in the `dp` list.

Here is the Python code implementing the above approach:

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

def longest_increasing_subsequence(head):
    if not head:
        return 0

# Convert linked list to array for easier access
    values = []
    current = head
    while current:
        values.append(current.value)
        current = current.next

n = len(values)
    dp = [1] * n  # Initialize dp array

for i in range(n):
        for j in range(i):
            if values[i] > values[j]:
                dp[i] = max(dp[i], dp[j] + 1)

return max(dp)  # The length of the longest increasing subsequence
```

The time complexity of this approach is O(n^2), where n is the number of nodes in the linked list, because we have a nested loop structure that iterates through the list. The space complexity is O(n) due to the storage of the `dp` array, which holds the lengths of the LIS for each element. However, since we also convert the linked list to an array, this adds an additional O(n) space requirement, leading to a total space complexity of O(n) for both conversions and the `dp` storage.

1. **Empty Linked List**: If the input linked list is empty (head is None), the function should return 0, which is correctly handled in the initial check.
2. **Single Element**: If the linked list contains only one node, the function should return 1, as the longest increasing subsequence is the single element itself.
3. **All Elements Equal**: If all elements in the linked list are equal, the function should return 1 since there are no increasing subsequences longer than 1.
4. **Strictly Increasing or Decreasing**: The function should correctly handle cases where the list is strictly increasing (return the length of the list) or strictly decreasing (return 1).

Find longest subsequence in linked list

DE Shaw

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

DE Shaw Machine Learning 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