-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathLC_2058.cpp
106 lines (91 loc) · 2.38 KB
/
LC_2058.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
using namespace std;
class Node{
public:
int val;
Node* next;
Node(int data = 0){
this->val = data;
this->next = NULL;
}
~Node(){
cout<<"Deleted: "<<this->val<<endl;
this->next = NULL;
delete next;
}
};
void print(Node* &head){
Node* temp = head;
while(temp){
cout<<temp->val<<" ";
temp = temp->next;
}
cout<<endl;
}
vector<int> nodesBetweenCriticalPoints(Node* head) {
// 0 node present
Node* prev = head;
if(!prev) return {-1,-1};
// 1 node present
Node* curr = head->next;
if(!curr) return {-1,-1};
// 2 nodes present
Node* nxt = head->next->next;
if(!nxt) return {-1,-1};
// 3 nodes present
if(!nxt->next) return {-1,-1};
int firstCP = -1;
int lastCP = -1;
int minDist = INT32_MAX;
int i = 0;
while(nxt){
// Check if CP is present or not
bool isCP = ((curr->val < prev->val && curr->val < nxt->val) ||
(curr->val > prev->val && curr->val > nxt->val))
? true : false;
// CP found and it's a first CP
if(isCP && firstCP == -1){
firstCP = i;
lastCP = i;
}
else if(isCP){
minDist = min(minDist,i-lastCP);
lastCP = i;
}
i++;
prev = prev->next;
curr = curr->next;
nxt = nxt->next;
}
// it means only one CP is present
if(lastCP == firstCP)
return {-1,-1};
return {minDist,lastCP-firstCP};
}
int main(){
Node* head = new Node(1);
Node* sec = new Node(3);
Node* third = new Node(2);
Node* forth = new Node(2);
Node* fifth = new Node(3);
Node* sixth = new Node(2);
Node* seventh = new Node(2);
Node* eighth = new Node(2);
Node* ninth = new Node(7);
Node* tenth = new Node(1);
head->next = sec;
sec->next = third;
third->next = forth;
forth->next = fifth;
fifth->next = sixth;
sixth->next = seventh;
seventh->next = eighth;
eighth->next = ninth;
ninth->next = tenth;
tenth->next = NULL;
print(head);
vector<int> ans = nodesBetweenCriticalPoints(head);
for(auto i : ans) cout<<i<<" ";
return 0;
}