aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--longest_cont_subarr_abs_diff.c42
-rw-r--r--longest_cont_subarr_abs_diff.py41
2 files changed, 83 insertions, 0 deletions
diff --git a/longest_cont_subarr_abs_diff.c b/longest_cont_subarr_abs_diff.c
new file mode 100644
index 0000000..e9c8a0f
--- /dev/null
+++ b/longest_cont_subarr_abs_diff.c
@@ -0,0 +1,42 @@
+// 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to
+// Limit
+#include "leetcode.h"
+
+/*
+ * given an array of integers 'nums' and an integer 'limit', return the size of
+ * the longest non empty subarray such that the absolute difference between any
+ * two elements of this subarrays is less than equal or equal to 'limit'
+ */
+
+int longestSubarray(int *nums, int numsSize, int limit) {
+ int n = numsSize, r = 0, l = 0, ans = 0, m_front = 0, m_end = 0, _m_front = 0,
+ _m_end = 0;
+ int *m_queue = (int *)malloc(n * sizeof(int));
+ int *_m_queue = (int *)malloc(n * sizeof(int));
+ for (r = 0; r < n; r++) {
+ while (_m_end > _m_front && nums[r] < _m_queue[_m_end - 1])
+ _m_end--;
+ while (m_end > m_front && nums[r] > m_queue[m_end - 1])
+ m_end--;
+ _m_queue[_m_end++] = nums[r];
+ m_queue[m_end++] = nums[r];
+ while ((m_queue[m_front] - _m_queue[_m_front]) > limit) {
+ if (m_queue[m_front] == nums[l])
+ m_front++;
+ if (_m_queue[_m_front] == nums[l])
+ _m_front++;
+ l++;
+ }
+ ans = fmax(ans, r - l + 1);
+ }
+ free(m_queue), free(_m_queue);
+ return ans;
+}
+
+int main() {
+ int n1[] = {8, 2, 4, 7}, n2[] = {10, 1, 2, 4, 7, 2},
+ n3[] = {4, 2, 2, 2, 4, 4, 2, 2};
+ printf("%d\n", longestSubarray(n1, ARRAY_SIZE(n1), 4)); // expect: 2
+ printf("%d\n", longestSubarray(n2, ARRAY_SIZE(n2), 5)); // expect: 4
+ printf("%d\n", longestSubarray(n3, ARRAY_SIZE(n3), 0)); // expect: 3
+}
diff --git a/longest_cont_subarr_abs_diff.py b/longest_cont_subarr_abs_diff.py
new file mode 100644
index 0000000..579a1b7
--- /dev/null
+++ b/longest_cont_subarr_abs_diff.py
@@ -0,0 +1,41 @@
+# 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to
+# Limit
+from collections import deque
+
+"""
+given an array of integers 'nums' and an integer 'limit', return the size of
+the longest non empty subarray such that the absolute difference between any
+two elements of this subarrays is less than equal or equal to 'limit'
+"""
+
+
+class Solution(object):
+ def longestSubarray(self, nums, limit):
+ """
+ :type nums: List[int]
+ :type limit: int
+ :rtype: int
+ """
+ max_d, min_d = deque(), deque()
+ n = 0
+ for i in nums:
+ while len(max_d) and i > max_d[-1]:
+ max_d.pop()
+ while len(min_d) and i < min_d[-1]:
+ min_d.pop()
+ max_d.append(i)
+ min_d.append(i)
+ if max_d[0] - min_d[0] > limit:
+ if max_d[0] == nums[n]:
+ max_d.popleft()
+ if min_d[0] == nums[n]:
+ min_d.popleft()
+ n += 1
+ return len(nums) - n
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.longestSubarray(nums=[8, 2, 4, 7], limit=4))
+ print(obj.longestSubarray(nums=[10, 1, 2, 4, 7, 2], limit=5))
+ print(obj.longestSubarray(nums=[4, 2, 2, 2, 4, 4, 2, 2], limit=0))