Longest Continuous Sequence with difference K in Linked List
Given a linked list and given an integer K, the task is to find the length of the longest continuous sequence in a linked list that has a difference of k.
Examples:
Input: 4 -> 1 -> 8 -> 5 -> 2 -> 4, K = 3
Output: 3
Explanation: The longest continuous sequence with a difference of 3 in linked list is 8 -> 5 -> 2 has a difference of 3. Therefore, the function should return 3.Input: 12 -> 3 -> 7 -> 1, K = 5
Output: 0
Explanation: There is no continuous sequence of list with a difference of 5 in linked list. Hence, the function should return 0.
Approach: To solve the problem follow the below idea:
The idea behind the approach is to use a Hashset to keep track of the values encountered in the Linked List.
Follow the steps to solve the problem:
- For each node, check if the current node value + K exists in the hash set. If it does, we enter a loop to increment the length of the continuous sequence. Start with a length of 1 and a current value of the current node value.
- Inside the loop, keep incrementing the current value by K and check if the updated value exists in the hash set. If it does, increment the length and update the current value.
- After the loop, compare the length with maxLength and update maxLength if the length is greater.
- Repeat steps 3-5 for checking if the current node value – K exists in the hash set, and if it does, enter a similar loop to find the length of the continuous sequence in the decreasing direction.
- Finally, insert the current node value into the hash set and move to the next node in the linked list.
- Once have traversed the entire linked list, return the maxLength as the length of the longest continuous sequence.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; struct Node { int data; Node* next; }; // Function to insert a node // at the beginning of the // linked list void insert(Node** head, int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = *head; *head = newNode; } // Function to find the length // of the longest continuous sequence // with a difference of k int findLongestContinuousSequence(Node* head, int k) { unordered_set< int > hashSet; int maxLength = 0; // Traverse the linked list while (head != nullptr) { // Check if current node + k // exists in the hash set if (hashSet.find(head->data + k) != hashSet.end()) { int length = 1; int curr = head->data; // Increment the length of // the continuous sequence while (hashSet.find(curr + k) != hashSet.end()) { length++; curr += k; } // Update the maximum length maxLength = std::max(maxLength, length); } // Check if current node - k // exists in the hash set if (hashSet.find(head->data - k) != hashSet.end()) { int length = 1; int curr = head->data; // Increment the length of the // continuous sequence while (hashSet.find(curr - k) != hashSet.end()) { length++; curr -= k; } // Update the maximum length maxLength = max(maxLength, length); } // Insert the current node // value into the hash set hashSet.insert(head->data); head = head->next; } return maxLength; } // Drivers code int main() { // Create the linked list Node* head = nullptr; insert(&head, 4); insert(&head, 3); insert(&head, 8); insert(&head, 5); insert(&head, 2); insert(&head, 4); int k = 3; // Find the length of the longest // continuous sequence with a // difference of k int maxLength = findLongestContinuousSequence(head, k); cout << "Length of the longest continuous sequence: " << maxLength << endl; return 0; } |
Java
// Java code for the above approach: import java.io.*; import java.util.HashSet; class Node { int data; Node next; } public class Main { // Function to insert a node // at the beginning of the // linked list static void insert(Node[] head, int data) { Node newNode = new Node(); newNode.data = data; newNode.next = head[ 0 ]; head[ 0 ] = newNode; } // Function to find the length // of the longest continuous sequence // with a difference of k static int findLongestContinuousSequence(Node head, int k) { HashSet<Integer> hashSet = new HashSet<>(); int maxLength = 0 ; // Traverse the linked list while (head != null ) { // Check if current node + k // exists in the hash set if (hashSet.contains(head.data + k)) { int length = 1 ; int curr = head.data; // Increment the length of // the continuous sequence while (hashSet.contains(curr + k)) { length++; curr += k; } // Update the maximum length maxLength = Math.max(maxLength, length); } // Check if current node - k // exists in the hash set if (hashSet.contains(head.data - k)) { int length = 1 ; int curr = head.data; // Increment the length of the // continuous sequence while (hashSet.contains(curr - k)) { length++; curr -= k; } // Update the maximum length maxLength = Math.max(maxLength, length); } // Insert the current node // value into the hash set hashSet.add(head.data); head = head.next; } return maxLength; } // Driver code public static void main(String[] args) { // Create the linked list Node[] head = new Node[ 1 ]; insert(head, 4 ); insert(head, 3 ); insert(head, 8 ); insert(head, 5 ); insert(head, 2 ); insert(head, 4 ); int k = 3 ; // Find the length of the longest // continuous sequence with a // difference of k int maxLength = findLongestContinuousSequence(head[ 0 ], k); System.out.println( "Length of the longest continuous sequence: " + maxLength); } } |
Python
class Node: def __init__( self , data): self .data = data self . next = None def insert(head, data): new_node = Node(data) new_node. next = head head = new_node return head # Function to find the length # of the longest continuous sequence # with a difference of k def find_longest_continuous_sequence(head, k): hash_set = set () max_length = 0 while head is not None : if head.data + k in hash_set: length = 1 curr = head.data while curr + k in hash_set: length + = 1 curr + = k max_length = max (max_length, length) if head.data - k in hash_set: length = 1 curr = head.data while curr - k in hash_set: length + = 1 curr - = k max_length = max (max_length, length) hash_set.add(head.data) head = head. next return max_length # Driver code head = None head = insert(head, 4 ) head = insert(head, 3 ) head = insert(head, 8 ) head = insert(head, 5 ) head = insert(head, 2 ) head = insert(head, 4 ) k = 3 max_length = find_longest_continuous_sequence(head, k) print ( "Length of the longest continuous sequence:" , max_length) |
C#
// C# code for the above approach: using System; using System.Collections.Generic; class Node { public int data; public Node next; } public class MainClass { // Function to insert a node // at the beginning of the // linked list static void Insert(Node[] head, int data) { Node newNode = new Node(); newNode.data = data; newNode.next = head[0]; head[0] = newNode; } // Function to find the length // of the longest continuous sequence // with a difference of k static int FindLongestContinuousSequence(Node head, int k) { HashSet< int > hashSet = new HashSet< int >(); int maxLength = 0; // Traverse the linked list while (head != null ) { // Check if current node + k // exists in the hash set if (hashSet.Contains(head.data + k)) { int length = 1; int curr = head.data; // Increment the length of // the continuous sequence while (hashSet.Contains(curr + k)) { length++; curr += k; } // Update the maximum length maxLength = Math.Max(maxLength, length); } // Check if current node - k // exists in the hash set if (hashSet.Contains(head.data - k)) { int length = 1; int curr = head.data; // Increment the length of the // continuous sequence while (hashSet.Contains(curr - k)) { length++; curr -= k; } // Update the maximum length maxLength = Math.Max(maxLength, length); } // Insert the current node // value into the hash set hashSet.Add(head.data); head = head.next; } return maxLength; } // Driver code public static void Main( string [] args) { // Create the linked list Node[] head = new Node[1]; Insert(head, 4); Insert(head, 3); Insert(head, 8); Insert(head, 5); Insert(head, 2); Insert(head, 4); int k = 3; // Find the length of the longest // continuous sequence with a // difference of k int maxLength = FindLongestContinuousSequence(head[0], k); Console.WriteLine( "Length of the longest continuous sequence: " + maxLength); } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
class Node { constructor(data) { this .data = data; this .next = null ; } } // Function to insert a node at the beginning of // the linked list function insert(head, data) { const newNode = new Node(data); newNode.next = head; return newNode; } // Function to find the length of the // longest continuous sequence with a difference of k function findLongestContinuousSequence(head, k) { const hashSet = new Set(); let maxLength = 0; // Traverse the linked list while (head !== null ) { // Check if current node + k exists in the hash set if (hashSet.has(head.data + k)) { let length = 1; let curr = head.data; // Increment the length of the continuous sequence while (hashSet.has(curr + k)) { length++; curr += k; } // Update the maximum length maxLength = Math.max(maxLength, length); } // Check if current node - k exists in the hash set if (hashSet.has(head.data - k)) { let length = 1; let curr = head.data; // Increment the length of the continuous sequence while (hashSet.has(curr - k)) { length++; curr -= k; } // Update the maximum length maxLength = Math.max(maxLength, length); } // Insert the current node value into the hash set hashSet.add(head.data); head = head.next; } return maxLength; } // Drivers code // Create the linked list let head = null ; head = insert(head, 4); head = insert(head, 3); head = insert(head, 8); head = insert(head, 5); head = insert(head, 2); head = insert(head, 4); const k = 3; // Find the length of the // longest continuous sequence with a difference of k const maxLength = findLongestContinuousSequence(head, k); console.log( "Length of the longest continuous sequence: " , maxLength); |
Length of the longest continuous sequence: 3
Time Complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(N), where N is the number of nodes in the linked list.
Contact Us