I like to read this solution as a small machine: keep the useful information, throw away the noise. For 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit, the solution in this repository is mainly a heap / priority queue solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: heap / priority queue, sliding window, greedy.
The notes already sitting in the source point us in the right direction:
- sliding windows + heap
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are longestSubarray.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//sliding windows + heap
02//Runtime: 364 ms, faster than 14.29% of C++ online submissions for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.
03//Memory Usage: 34.6 MB, less than 100.00% of C++ online submissions for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.
04class Solution {
05public:
06 int longestSubarray(vector<int>& nums, int limit) {
07 int n = nums.size();
08 int ans = 0;
09 int slow = 0;
10
11 // sort(nums.begin(), nums.end());
12
13 // for(int i = 0; i < n; i++){
14 // cout << nums[i] << " ";
15 // }
16 // cout << endl;
17
18 priority_queue<pair<int,int>, vector<pair<int,int>>> pqMax; //max popped first
19 priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pqMin; //min popped first
20
21 int wMaxIdx = 0, wMinIdx = 0;
22 for(int fast = 0; fast < n; fast++){
23 pqMax.push(make_pair(nums[fast], fast));
24 pqMin.push(make_pair(nums[fast], fast));
25
26 //find a valid slow, pop all invalid element from pqMin and pqMax
27 // cout << "before [" << slow << ", " << fast << "]" << endl;
28 // cout << "max: " << pqMax.top().first << ", " << pqMax.top().second << endl;
29 // cout << "min: " << pqMin.top().first << ", " << pqMin.top().second << endl;
30 while(pqMax.top().first - pqMin.top().first > limit){
31 if(pqMax.top().second < pqMin.top().second){
32 //remove max value
33 //can't simply use "slow = pqMax.top().second+1;"
34 slow = max(slow, pqMax.top().second+1);
35 pqMax.pop();
36 }else{
37 slow = max(slow, pqMin.top().second+1);
38 pqMin.pop();
39 }
40 // cout << "max: " << pqMax.top().first << ", " << pqMax.top().second << endl;
41 // cout << "min: " << pqMin.top().first << ", " << pqMin.top().second << endl;
42 }
43
44 // if(fast - slow + 1 > ans){
45 // cout << "after [" << slow << ", " << fast << "]" << endl;
46 // }
47 //fast - slow + 1: window size
48 ans = max(ans, fast - slow + 1);
49
50 //outside the window
51 while(pqMax.top().second < slow){
52 pqMax.pop();
53 }
54 while(pqMin.top().second < slow){
55 pqMin.pop();
56 }
57 }
58
59 return ans;
60 }
61};
62
63//sliding window + deque, revised from 1425. Constrained Subsequence Sum.cpp
64//Runtime: 136 ms, faster than 42.86% of C++ online submissions for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.
65//Memory Usage: 35.1 MB, less than 100.00% of C++ online submissions for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.
66class Solution {
67public:
68 int longestSubarray(vector<int>& nums, int limit) {
69 int n = nums.size();
70 int ans = 0;
71 int slow = 0;
72
73 deque<pair<int,int>> maxQ;
74 deque<pair<int,int>> minQ;
75
76 int wMaxIdx = 0, wMinIdx = 0;
77 for(int fast = 0; fast < n; fast++){
78 while(maxQ.size() > 0 && maxQ.back().first < nums[fast]){
79 maxQ.pop_back();
80 }
81 while(minQ.size() > 0 && minQ.back().first > nums[fast]){
82 minQ.pop_back();
83 }
84 maxQ.push_back(make_pair(nums[fast], fast));
85 minQ.push_back(make_pair(nums[fast], fast));
86
87 //find a valid slow
88 while(maxQ.front().first - minQ.front().first > limit){
89 if(maxQ.front().second < minQ.front().second){
90 //remove max value
91 slow = max(slow, maxQ.front().second+1);
92 maxQ.pop_front();
93 }else{
94 slow = max(slow, minQ.front().second+1);
95 minQ.pop_front();
96 }
97 }
98
99 // cout << slow << ", " << fast << endl;
100 ans = max(ans, fast - slow + 1);
101
102 //outside the window
103 while(maxQ.front().second < slow){
104 maxQ.pop_front();
105 }
106 while(minQ.front().second < slow){
107 minQ.pop_front();
108 }
109 }
110
111 return ans;
112 }
113};
114
115//sliding window + deque, cleaner
116//https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/609771/JavaC%2B%2BPython-Deques-O(N)
117//Runtime: 108 ms, faster than 71.43% of C++ online submissions for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.
118//Memory Usage: 32.8 MB, less than 100.00% of C++ online submissions for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.
119//time: O(N), space: O(N)
120class Solution {
121public:
122 int longestSubarray(vector<int>& nums, int limit) {
123 int n = nums.size();
124 int ans = 0;
125 int slow = 0;
126
127 deque<int> maxQ;
128 deque<int> minQ;
129
130 for(int fast = 0; fast < n; fast++){
131 while(!maxQ.empty() && maxQ.back() < nums[fast]) maxQ.pop_back();
132 while(!minQ.empty() && minQ.back() > nums[fast]) minQ.pop_back();
133 /*
134 we don't need to record the index, why?
135 */
136 maxQ.push_back(nums[fast]);
137 minQ.push_back(nums[fast]);
138
139 //find a valid slow, dealing with the data structure and slow pointer at the same time
140 while(maxQ.front() - minQ.front() > limit){
141 // cout << slow << ", " << fast << endl;
142 if(maxQ.front() == nums[slow])maxQ.pop_front();
143 if(minQ.front() == nums[slow])minQ.pop_front();
144 slow++;
145 }
146
147 // cout << "** " << slow << ", " << fast << " **" << endl;
148 ans = max(ans, fast - slow + 1);
149
150 // the data structure is already processed together with slow
151 // //outside the window
152 // while(maxQ.front().second < slow){
153 // maxQ.pop_front();
154 // }
155 // while(minQ.front().second < slow){
156 // minQ.pop_front();
157 // }
158 }
159 cout << endl;
160
161 return ans;
162 }
163};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.