Maximum distance between Peaks in given Linked List
Given a linked list lis of length N, the task is to determine the maximum distance between two consecutive peaks of the given linked list. A peak is defined as a node having a value greater than its neighbours. The distance between two nodes is defined as the number of nodes present between them.
Examples:
Input: lis = 1 -> 2 -> 3 -> 1 -> 5 -> 4 -> 4 -> 10 -> 7
Output: 2
Explanation: The peaks in the linkedlist are 3, 5, 10
The distance between 3 and 5 is 1.
The distance between 5 and 10 is 2.
The maximum distance is 2.Input: lis = 1 -> 3 -> 1 -> 1 ->1 -> 1 -> 4 -> 2 -> 7
Output: 4
Explanation: The peaks in the linkedlist are 3, 4, 7
The distance between 3 and 4 is 4.
The distance between 4 and 7 is 1.
The maximum distance is 4.
Approach: The solution is based on greedy approach. Follow the steps mentioned below to solve the problem:
- Iterate over the linkedlist and find nodes that are peaks.
- Keep a record of previousIndex that is peak and current index if its a peak
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Class(struct) for the structure of a node struct Node { int data; Node* next; Node( int data, Node* next) : data(data) , next(next) { } }; // Function to find the maximum distance void findMaxGap(Node* head) { // Pre points to previous of current node Node* pre = new Node(-1, head); // Current is initially head Node* cur = head; int lastIndex = -1, currentIndex = 0, maxGap = 0, gap = 0; // Loop till current is not NULL while (cur != NULL) { // Find next of current Node* next = cur->next; // One node only if (pre->next == head && next == NULL) { cout << maxGap; return ; } // For the 1st node check only next else if (pre->next == head && next->data < cur->data) { lastIndex = currentIndex; } // For the last node check // only the prev node else if (next == NULL && pre->data < cur->data) { if (lastIndex != -1) { lastIndex = currentIndex; } else { gap = currentIndex - lastIndex - 1; maxGap = max(gap, maxGap); lastIndex = currentIndex; } } // Check prev and next nodes for all // intermediate nodes else if (pre->data < cur->data && next->data < cur->data) { if (lastIndex != -1) { lastIndex = currentIndex; } else { gap = currentIndex - lastIndex - 1; maxGap = max(gap, maxGap); lastIndex = currentIndex; } } // Move pre and cur pointer pre = pre->next; cur = cur->next; currentIndex++; } cout << maxGap << "\n" ; } // Driver code int main() { // Create the linkedlist Node* head = new Node(1, NULL); head->next = new Node(2, NULL); head->next->next = new Node(3, NULL); head->next->next->next = new Node(1, NULL); head->next->next->next->next = new Node(5, NULL); head->next->next->next->next->next = new Node(4, NULL); head->next->next->next->next->next->next = new Node(4, NULL); head->next->next->next->next->next->next->next = new Node(10, NULL); head->next->next->next->next->next->next->next->next = new Node(7, NULL); // Function call findMaxGap(head); } // This code is contributed by Aneshka Goyal // Time complexity is O(n) while space is O(1), so no need // of another data structure |
Java
// Java code to implement the above approach import java.io.*; import java.util.*; // Class for the structure of a node class Node { int data; Node next; public Node( int data, Node next) { this .data = data; this .next = next; } } class GFG { // Driver code public static void main(String[] args) { // Create the linkedlist Node head = new Node( 1 , null ); head.next = new Node( 2 , null ); head.next.next = new Node( 3 , null ); head.next.next.next = new Node( 1 , null ); head.next.next.next.next = new Node( 5 , null ); head.next.next.next.next.next = new Node( 4 , null ); head.next.next.next.next.next.next = new Node( 4 , null ); head.next.next.next.next.next.next.next = new Node( 10 , null ); head.next.next.next.next.next.next.next.next = new Node( 7 , null ); // Function call findMaxGap(head); } // Function to find the maximum distance static void findMaxGap(Node head) { // Create a set to store // all the peak nodes Set<Node> peaks = new HashSet<>(); // Pre points to previous of current node Node pre = new Node(- 1 , head); // Current is initially head Node cur = head; // Loop till current is not null while (cur != null ) { // Find next of current Node next = cur.next; // One node only if (pre.next == head && next == null ) peaks.add(cur); // For the 1st node check only next else if (pre.next == head && next.data < cur.data) peaks.add(cur); // For the last node check // only the prev node else if (next == null && pre.data < cur.data) peaks.add(cur); // Check prev and next nodes for all // intermediate nodes else if (pre.data < cur.data && next.data < cur.data) peaks.add(cur); // Move pre and cur pointer pre = pre.next; cur = cur.next; } // Initialize int lastPeakIndex = - 1 , currentIndex = 0 , maxGap = 0 , gap = 0 ; cur = head; // Iterate through the linkedlist while (cur != null ) { // If current node is a peak if (peaks.contains(cur)) { // If current node is first peak // then update lastPeakIndex // and move ahead if (lastPeakIndex == - 1 ) lastPeakIndex = currentIndex; // If current node peak then // calculate gap and update // lastPeakIndex and move ahead else { gap = currentIndex - lastPeakIndex - 1 ; maxGap = Math.max(gap, maxGap); lastPeakIndex = currentIndex; } } // Increment currentIndex // move current node ahead currentIndex++; cur = cur.next; } System.out.println(maxGap); } } |
Python3
# Python Code to implement the above approach class Node: def __init__( self , data, next ): self .data = data # Assign data self . next = next # Initialize next as null # Function to find maximum difference def findMaxGap(): # Create a set to store all peak nodes peaks = set () # Pre points to previous of current node pre = Node( - 1 , head) # Current is pointed to head cur = head while (cur): next_node = cur. next # One node only if (pre. next = = head and next_node = = None ): peaks.add(cur) # For the 1st node check only next elif (pre. next = = head and next_node.data < cur.data): peaks.add(cur) # For the last node check # only the prev node elif (next_node = = None and pre.data < cur.data): peaks.add(cur) # Check prev and next nodes for all # intermediate nodes elif (pre.data < cur.data and next_node.data < cur.data): peaks.add(cur) pre = pre. next cur = cur. next lastPeakIndex = - 1 currentIndex = 0 maxGap = 0 gap = 0 cur = head while (cur): # If current node is a peak if (cur in peaks): # If current node is first peak then # update lastPeakIndex and move ahead if (lastPeakIndex = = - 1 ): lastPeakIndex = currentIndex # If current node peak then calculate # gap and update lastPeakIndex and move ahead else : gap = currentIndex - lastPeakIndex - 1 maxGap = max (gap, maxGap) lastPeakIndex = currentIndex currentIndex + = 1 cur = cur. next print (maxGap) # Create linked list. head = Node( 1 , None ) head. next = Node( 2 , None ) head. next . next = Node( 3 , None ) head. next . next . next = Node( 1 , None ) head. next . next . next . next = Node( 5 , None ) head. next . next . next . next . next = Node( 4 , None ) head. next . next . next . next . next . next = Node( 4 , None ) head. next . next . next . next . next . next . next = Node( 10 , None ) head. next . next . next . next . next . next . next . next = Node( 7 , None ) # function call findMaxGap() # This code is contributed by lokesh (lokeshmvs21). |
C#
// C# code to implement the above approach using System; using System.Collections.Generic; // Class for the structure of a node class Node { public int data; public Node next; public Node( int data, Node next) { this .data = data; this .next = next; } } public class GFG { // Driver code public static void Main(String[] args) { // Create the linkedlist Node head = new Node(1, null ); head.next = new Node(2, null ); head.next.next = new Node(3, null ); head.next.next.next = new Node(1, null ); head.next.next.next.next = new Node(5, null ); head.next.next.next.next.next = new Node(4, null ); head.next.next.next.next.next.next = new Node(4, null ); head.next.next.next.next.next.next.next = new Node(10, null ); head.next.next.next.next.next.next.next.next = new Node(7, null ); // Function call findMaxGap(head); } // Function to find the maximum distance static void findMaxGap(Node head) { // Create a set to store // all the peak nodes HashSet<Node> peaks = new HashSet<Node>(); // Pre points to previous of current node Node pre = new Node(-1, head); // Current is initially head Node cur = head; // Loop till current is not null while (cur != null ) { // Find next of current Node next = cur.next; // One node only if (pre.next == head && next == null ) peaks.Add(cur); // For the 1st node check only next else if (pre.next == head && next.data < cur.data) peaks.Add(cur); // For the last node check // only the prev node else if (next == null && pre.data < cur.data) peaks.Add(cur); // Check prev and next nodes for all // intermediate nodes else if (pre.data < cur.data && next.data < cur.data) peaks.Add(cur); // Move pre and cur pointer pre = pre.next; cur = cur.next; } // Initialize int lastPeakIndex = -1, currentIndex = 0, maxGap = 0, gap = 0; cur = head; // Iterate through the linkedlist while (cur != null ) { // If current node is a peak if (peaks.Contains(cur)) { // If current node is first peak // then update lastPeakIndex // and move ahead if (lastPeakIndex == -1) lastPeakIndex = currentIndex; // If current node peak then // calculate gap and update // lastPeakIndex and move ahead else { gap = currentIndex - lastPeakIndex - 1; maxGap = Math.Max(gap, maxGap); lastPeakIndex = currentIndex; } } // Increment currentIndex // move current node ahead currentIndex++; cur = cur.next; } Console.WriteLine(maxGap); } } // This code is contributed by 29AjayKumar |
Javascript
// Javascript code to implement the above approach // Class for the structure of a node class Node { constructor(data, next) { this .data = data; this .next = next; } } // Driver code // Create the linkedlist let head = new Node(1, null ); head.next = new Node(2, null ); head.next.next = new Node(3, null ); head.next.next.next = new Node(1, null ); head.next.next.next.next = new Node(5, null ); head.next.next.next.next.next = new Node(4, null ); head.next.next.next.next.next.next = new Node(4, null ); head.next.next.next.next.next.next.next = new Node(10, null ); head.next.next.next.next.next.next.next.next = new Node(7, null ); // Function call findMaxGap(head); // Function to find the maximum distance function findMaxGap(head) { // Create a set to store // all the peak nodes let peaks = new Set(); // Pre points to previous of current node let pre = new Node(-1, head); // Current is initially head let cur = head; // Loop till current is not null while (cur != null ) { // Find next of current let next = cur.next; // One node only if (pre.next == head && next == null ) peaks.add(cur); // For the 1st node check only next else if (pre.next == head && next.data < cur.data) peaks.add(cur); // For the last node check // only the prev node else if (next == null && pre.data < cur.data) peaks.add(cur); // Check prev and next nodes for all // intermediate nodes else if (pre.data < cur.data && next.data < cur.data) peaks.add(cur); // Move pre and cur pointer pre = pre.next; cur = cur.next; } // Initialize let lastPeakIndex = -1, currentIndex = 0, maxGap = 0, gap = 0; cur = head; // Iterate through the linkedlist while (cur != null ) { // If current node is a peak if (peaks.has(cur)) { // If current node is first peak // then update lastPeakIndex // and move ahead if (lastPeakIndex == -1) lastPeakIndex = currentIndex; // If current node peak then // calculate gap and update // lastPeakIndex and move ahead else { gap = currentIndex - lastPeakIndex - 1; maxGap = Math.max(gap, maxGap); lastPeakIndex = currentIndex; } } // Increment currentIndex // move current node ahead currentIndex++; cur = cur.next; } console.log(maxGap); } |
2
Time Complexity: O(N)
Auxiliary Space: O(N)