Maximum distance between Peaks in given Linked List

0 0 8 minutes read

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);
}

Output

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 zambiatek!