All prompts are owned by LeetCode. To view the prompt, click the title link above.
First completed : July 05, 2024
Last updated : July 05, 2024
Related Topics : Linked List
Acceptance Rate : 69.62 %
To find the critical points, we can simply iterate through each to see see if that node is a critical point, storing its index if it is in fact a critcal point.
We also know that we can't have a crit pt if the array length is less than 3 or if we don't have at least 2 points.
Notes on my Versions
Versions 1 and 2 make use of lists to keep track of the critical points, making a second pass through them afterwards to determine the output. This use of a list/arraylist could be removed however. Notably, in my C++ version (Version 3), I decided to make use of additional variables instead of a vector, saving heavily on space and partially in runtime as well. This is permitted due to us only needing to keep track of the following: 1. the smallest gap between consecutive crit points 2. the largest gap, aka the difference of indices betweeen the first and last critical point.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
def helper(prevPrev: int,
prev: int,
curr: Optional[ListNode],
output: List[int],
indx: int = 0) -> None :
if (prev > curr.val and prev > prevPrev) \
or (prev < curr.val and prev < prevPrev) :
output.append(indx - 1)
if curr.next :
helper(prev, curr.val, curr.next, output, indx + 1)
critPts = []
if head and head.next and head.next.next :
helper(head.val, head.next.val, head.next.next, critPts)
if len(critPts) < 2 :
return [-1] * 2
return [min([critPts[i] - critPts[i - 1] for i in range(1, len(critPts))]),
critPts[-1] - critPts[0]]# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
if not head or not head.next or not head.next.next :
return [-1, -1]
critPts = []
indx = 0
prev = head.next.val
prevprev = head.val
head = head.next.next
while head :
if (prev > head.val and prev > prevprev) \
or (prev < head.val and prev < prevprev) :
critPts.append(indx - 1)
prevprev = prev
prev = head.val
head = head.next
indx += 1
if len(critPts) < 2 :
return [-1] * 2
return [min([critPts[i] - critPts[i - 1] for i in range(1, len(critPts))]),
critPts[-1] - critPts[0]]/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public int[] nodesBetweenCriticalPoints(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return new int[]{-1, -1};
}
ArrayList<Integer> critPts = new ArrayList<>();
int indx = 0;
int prevprev = head.val;
int prev = head.next.val;
head = head.next.next;
int minSpace = Integer.MAX_VALUE;
while (head != null) {
if ((prev > head.val && prev > prevprev) ||
(prev < head.val && prev < prevprev)) {
if (critPts.size() > 0 && indx - critPts.getLast() < minSpace) {
minSpace = indx - critPts.getLast();
}
critPts.add(indx);
}
prevprev = prev;
prev = head.val;
head = head.next;
indx++;
}
if (critPts.size() < 2) {
return new int[]{-1, -1};
}
return new int[]{minSpace, critPts.getLast() - critPts.get(0)};
}
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
vector<int> nodesBetweenCriticalPoints(ListNode* head) {
vector<int> output;
if (!head || !head->next || !head->next->next) {
output.push_back(-1);
output.push_back(-1);
return output;
}
int earliestIndx = 0;
int latestIndx = 0;
int prevIndx = 0;
int indx = 1;
int prevprev = head->val;
int prev = head->next->val;
head = head->next->next;
int minSpace = INT_MAX;
while (head) {
if ((prev > head->val && prev > prevprev) ||
(prev < head->val && prev < prevprev)) {
if (!earliestIndx) {
earliestIndx = indx;
}
if (latestIndx && indx - latestIndx < minSpace) {
minSpace = indx - latestIndx;
}
latestIndx = indx;
}
prevprev = prev;
prev = head->val;
head = head->next;
indx++;
}
if (minSpace == INT_MAX) {
output.push_back(-1);
output.push_back(-1);
return output;
}
output.push_back(minSpace);
output.push_back(latestIndx - earliestIndx);
return output;
}
};