Maximum distance between Peaks in given Linked List in Java
In the following article, we explore the idea of identifying peaks in linked lists and the methods used to increase the separation between these peaks. Nodes with a higher value than their neighboring nodes are called peaks in a linked list. Gaining knowledge about and effectively locating these peaks can provide insights into the distribution and structure of the data within the list.
Example 1:
Input: Linked list: 1 -> 2 -> 3 -> 2 -> 7 -> 1 -> 6 -> 9 -> 8 -> NULL
Output: 2
Explanation: Here, the peaks are located at the third node (3), fifth node (7), and eighth (9). We will return 2 because there is a difference of 1 between the 3rd and 5th nodes and a difference of 2 between the 5th and 8th nodes.
Example 2:
Input: Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Output: 0
Explanation: There is no peak here because all of the node values are in increasing order. Consequently, we will return 0.
Using Optimized Approach
Algorithm
Linked List Scanning Approach
Step 1: Linear scanning through the linked list.
Step 2: Detecting peaks at each node.
Step 3: Peaks are identified by comparing node values with adjacent nodes.
Step 4: Peak distance calculated, maximum distance updated.
Here is an implementation of finding the maximum distance between peaks in a given linkedlist using an optimized approach:
FileName: MaxDistanceBetweenPeaks.java
class Node { int val; Node next; Node(int data, Node next_ptr) { val = data; next = next_ptr; } } public class MaxDistanceBetweenPeaks { static void printLL(Node head) { Node temp = head; while (temp != null) { System.out.print(temp.val + " -> "); temp = temp.next; } System.out.println("NULL"); } // Function to find the maximum distance between two consecutive peaks in the linked list static int findDistance(Node head) { Node temp = head; int curP = -1, prevP = -1; int ans = 0; // Variable to store the maximum distance between peaks int prev = Integer.MAX_VALUE; int cur = 0; while (temp.next != null) { if (temp.val > prev && temp.val > temp.next.val) { // Check if the current node is a peak if (prevP == -1) { // If it's the first peak encountered prevP = cur; // Update the previous peak index } curP = cur; // Update the current peak index ans = Math.max(ans, curP - prevP - 1); // Update the maximum distance between peaks prevP = curP; } prev = temp.val; temp = temp.next; cur++; } return ans; // Return the maximum distance between peaks } public static void main(String[] args) { // Creating head of the linked list Node head = new Node(1, null); // Adding data to the linked list head.next = new Node(2, null); head.next.next = new Node(3, null); head.next.next.next = new Node(2, null); head.next.next.next.next = new Node(7, null); head.next.next.next.next.next = new Node(1, null); head.next.next.next.next.next.next = new Node(6, null); head.next.next.next.next.next.next.next = new Node(9, null); head.next.next.next.next.next.next.next.next = new Node(8, null); System.out.println("The distance between the two peaks of the given linked list is: " + findDistance(head)); } }
Output:
The distance between the two peaks of the given linked list is: 2
Complexity analysis: The above approach's time complexity is O(n) because it iterates through each node once, and its space complexity is O(1) because it uses a constant amount of extra space regardless of the input size.
Using an Optimized Iterative Approach
Algorithm
Step 1: Initialize variables for maximum distance (`maxDistance`), current node (`current`), and index (`index`).
Step 2: Traverse the linked list.
Step 3: Identify peaks by comparing node values with adjacent nodes.
Step 4: Calculate the distance between consecutive peaks and update `maxDistance`.
Step 5: Return `maxDistance` after traversal.
Here is an implementation of finding the maximum distance between peaks in a given linkedlist using an optimized Iterative approach:
FileName: MaxDistanceBetweenPeak1.java
class Node { int val; Node next; Node prev; // New field to maintain a reference to the previous node int index; // New field to maintain the index of each node Node(int data, Node next_ptr, Node prev_ptr, int index) { val = data; next = next_ptr; prev = prev_ptr; this.index = index; } } public class MaxDistanceBetweenPeaks1 { // Function to find the maximum distance between two consecutive peaks in the linked list static int findDistance(Node head) { if (head == null || head.next == null || head.next.next == null) { return 0; } int maxDistance = 0; // Variable to store the maximum distance between peaks Node current = head.next; // Start from the second node int index = 1; Node peak1 = null; Node peak2 = null; while (current.next != null) { if (current.val > current.next.val && current.val > current.prev.val) { // If the current node is a peak if (peak1 == null) { peak1 = current; } else if (peak2 == null) { peak2 = current; maxDistance = Math.max(maxDistance, peak2.index - peak1.index - 1); peak1 = peak2; peak2 = null; } } current = current.next; index++; // Increment index } return maxDistance; } public static void main(String[] args) { // Creating head of the linked list Node head = new Node(1, null, null, 0); // Set index of head node to 0 Node prev = head; // Set previous node for head // Adding data to the linked list head.next = new Node(2, null, prev, 1); prev = head.next; head.next.next = new Node(3, null, prev, 2); prev = head.next.next; head.next.next.next = new Node(2, null, prev, 3); prev = head.next.next.next; head.next.next.next.next = new Node(7, null, prev, 4); prev = head.next.next.next.next; head.next.next.next.next.next = new Node(1, null, prev, 5); prev = head.next.next.next.next.next; head.next.next.next.next.next.next = new Node(6, null, prev, 6); prev = head.next.next.next.next.next.next; head.next.next.next.next.next.next.next = new Node(9, null, prev, 7); prev = head.next.next.next.next.next.next.next; head.next.next.next.next.next.next.next.next = new Node(8, null, prev, 8); System.out.println("The distance between the two peaks of the given linked list is: " + findDistance(head)); } }
Output:
The distance between the two peaks of the given linked list is: 2
Complexity analysis: The above approach's complexity analysis reveals that it has a time complexity of O(n), where n is the number of nodes in the linked list, and a space complexity of O(n), where n is the number of nodes in the linked list.