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 nodestruct Node { int data; Node* next; Node(int data, Node* next) : data(data) , next(next) { }};// Function to find the maximum distancevoid 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 codeint 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 approachimport java.io.*;import java.util.*;// Class for the structure of a nodeclass 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 approachclass Node: def __init__(self, data, next): self.data = data # Assign data self.next = next # Initialize next as null# Function to find maximum differencedef 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 callfindMaxGap()# This code is contributed by lokesh (lokeshmvs21). |
C#
// C# code to implement the above approachusing System;using System.Collections.Generic;// Class for the structure of a nodeclass 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 nodeclass Node { constructor(data, next) { this.data = data; this.next = next; }}// Driver code// Create the linkedlistlet 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 callfindMaxGap(head);// Function to find the maximum distancefunction 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);} |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
