Longest Continuous Subarray with Absolute Diff Less than or Equal to Limit in Java
Longest Continuous Subarray with Absolute Diff Less than or Equal to Limit in Java
In this tutorial, we are going to learn about longest continuous subarray with absolute diff less than or equal to limit in Java. An array of integers is provided by the problem. The objective is to determine how long the longest non-empty contiguous subarray (a row of neighboring elements from the array) is, provided that the absolute difference between any two subarray elements does not above the limit value.
Examples:
Example 1:
Input: nums = [1, 3, 6, 2, 5], limit = 3
Output: 3
Explanation: All subarrays are:
[1] with maximum absolute diff |1-1| = 0 <= 3.
[1, 3] with maximum absolute diff |3-1| = 2 <= 3.
[1, 3, 6] with maximum absolute diff |6-1| = 5 > 3.
[1, 3, 6, 2] with maximum absolute diff |6-1| = 5 > 3.
[1, 3, 6, 2, 5] with maximum absolute diff |6-1| = 5 > 3.
[3] with maximum absolute diff |3-3| = 0 <= 3.
[3, 6] with maximum absolute diff |6-3| = 3 <= 3.
[3, 6, 2] with maximum absolute diff |6-2| = 4 > 3.
[3, 6, 2, 5] with maximum absolute diff |6-2| = 4 > 3.
[6] with maximum absolute diff |6-6| = 0 <= 3.
[6, 2] with maximum absolute diff |6-2| = 4 > 3.
[6, 2, 5] with maximum absolute diff |6-2| = 4 > 3.
[2] with maximum absolute diff |2-2| = 0 <= 3.
[2, 5] with maximum absolute diff |5-2| = 3 <= 3.
[5] with maximum absolute diff |5-5| = 0 <= 3.
Therefore, the size of the longest subarray is 3 ([1, 3, 6] or [3, 6, 2]).
Example 2:
Input: nums = [10, 5, 2, 8, 7], limit = 5
Output: 4
Explanation: All subarrays are:
[10] with maximum absolute diff |10-10| = 0 <= 5.
[10, 5] with maximum absolute diff |10-5| = 5 <= 5.
[10, 5, 2] with maximum absolute diff |10-2| = 8 > 5.
[10, 5, 2, 8] with maximum absolute diff |10-2| = 8 > 5.
[10, 5, 2, 8, 7] with maximum absolute diff |10-2| = 8 > 5.
[5] with maximum absolute diff |5-5| = 0 <= 5.
[5, 2] with maximum absolute diff |5-2| = 3 <= 5.
[5, 2, 8] with maximum absolute diff |8-2| = 6 > 5.
[5, 2, 8, 7] with maximum absolute diff |8-2| = 6 > 5.
[2] with maximum absolute diff |2-2| = 0 <= 5.
[2, 8] with maximum absolute diff |8-2| = 6 > 5.
[2, 8, 7] with maximum absolute diff |8-2| = 6 > 5.
[8] with maximum absolute diff |8-8| = 0 <= 5.
[8, 7] with maximum absolute diff |8-7| = 1 <= 5.
[7] with maximum absolute diff |7-7| = 0 <= 5.
Therefore, the size of the longest subarray is 4 ([10, 5, 2, 8] or [5, 2, 8, 7]).
Example 3 :
Input: nums = [4, 6, 1, 3, 7], limit = 2
Output: 2
Explanation: All subarrays are:
[4] with maximum absolute diff |4-4| = 0 <= 2.
[4, 6] with maximum absolute diff |6-4| = 2 <= 2.
[4, 6, 1] with maximum absolute diff |6-1| = 5 > 2.
[4, 6, 1, 3] with maximum absolute diff |6-1| = 5 > 2.
[4, 6, 1, 3, 7] with maximum absolute diff |6-1| = 5 > 2.
[6] with maximum absolute diff |6-6| = 0 <= 2.
[6, 1] with maximum absolute diff |6-1| = 5 > 2.
[6, 1, 3] with maximum absolute diff |6-1| = 5 > 2.
[6, 1, 3, 7] with maximum absolute diff |6-1| = 5 > 2.
[1] with maximum absolute diff |1-1| = 0 <= 2.
[1, 3] with maximum absolute diff |3-1| = 2 <= 2.
[1, 3, 7] with maximum absolute diff |7-1| = 6 > 2.
[3] with maximum absolute diff |3-3| = 0 <= 2.
[3, 7] with maximum absolute diff |7-3| = 4 > 2.
[7] with maximum absolute diff |7-7| = 0 <= 2.
Therefore, the size of the longest subarray is 2 ([4, 6] or [1, 3]).
Approach 1: Using the sliding window technique
ALGORITHM:
Step 1: Set up two deques: increase to monitor the lowest values and decrease to track the highest values. We should also initialize the variables max to store the maximum length of the subarray to track the sliding window's left border.
Step 2: Iterate through the array, updating the deques for each element n by adding n to both deques after removing elements from the rear of decrease if they are less than n and from the back of increase if they are larger than n.
Step 3: Move the left boundary to the right to change the window's size while the difference between the initial elements of the reduction and increase above the specified limit. If the elements in the deques match the element at the left boundary, the corresponding elements from the deques are removed.
Step 4: Determine the size of the window as it is now, then update the maximum if it is larger. Return max, the length of the longest subarray satisfying the criteria, once all elements have been processed.
Filename: ContinuousSubarray.java
import java.util.LinkedList; public class ContinuousSubarray { public int longestSubarray(int[] numbers, int limit) { LinkedListminDeque = new LinkedList<>(); LinkedList maxDeque = new LinkedList<>(); int maxLength = 0; int leftIndex = 0; for (int a = 0; a < numbers.length; a++) { int x = numbers[a]; while (minDeque.size() > 0 && x < minDeque.getLast()) { minDeque.removeLast(); } minDeque.add(x); while (maxDeque.size() > 0 && x > maxDeque.getLast()) { maxDeque.removeLast(); } maxDeque.add(x); while (maxDeque.getFirst() - minDeque.getFirst() > limit) { if (numbers[leftIndex] == maxDeque.getFirst()) { maxDeque.removeFirst(); } if (numbers[leftIndex] == minDeque.getFirst()) { minDeque.removeFirst(); } leftIndex++; } int n = a - leftIndex + 1; maxLength = Math.max(maxLength, n); } return maxLength; } public static void main(String[] args) { ContinuousSubarray s = new ContinuousSubarray(); // Test case 1 int[] numbers1 = {8, 2, 4, 7}; int limit1 = 4; System.out.println("Longest subarray length (Test case 1): " + s.longestSubarray(numbers1, limit1)); // Test case 2 int[] numbers2 = {10, 1, 2, 4, 7, 2}; int limit2 = 5; System.out.println("Longest subarray length (Test case 2): " + s.longestSubarray(numbers2, limit2)); // Test case 3 int[] numbers3 = {4, 2, 2, 2, 4, 4, 2, 2}; int limit3 = 0; System.out.println("Longest subarray length (Test case 3): " + s.longestSubarray(numbers3, limit3)); } }
Output:
Longest subarray length (Test case 1): 2 Longest subarray length (Test case 2): 4 Longest subarray length (Test case 3): 3
Complexity analysis:
Time complexity: O(n), where the array's length is n. Time complexity is linear since each element is added to and removed from the deques only once.
Space complexity: In the worst case, O(n) will be used for the deques' space.
Approach 2: Using sliding window with priority queues
ALGORITHM:
Step 1: Begin with two arrows. Set both to 0 to indicate the current window's limits.
Step 2: Moreover, set the result's starting value to 0 to record the longest valid subarray length that was discovered.
Step 3: Make use of the minHeap and maxHeap priority queues:
A min-heap called minHeap records the tiniest components in the open window.
maxHeap is a max-heap that tracks the largest elements in the current window. It is implemented in reverse order.
Filename: ContinuousSubarray.java
import java.util.PriorityQueue; import java.util.Collections; public class ContinuousSubarray { public int longestSubarray(int[] nums, int limit) { int left = 0, right = 0; int result = 0; PriorityQueueminHeap = new PriorityQueue<>(); PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder()); while (right < nums.length) { minHeap.add(nums[right]); maxHeap.add(nums[right]); while ((!minHeap.isEmpty() && !maxHeap.isEmpty()) && maxHeap.peek() - minHeap.peek() > limit) { int num = nums[left]; maxHeap.remove(num); minHeap.remove(num); left++; } result = Math.max(result, right - left + 1); right++; } return result; } public static void main(String[] args) { ContinuousSubarray cs = new ContinuousSubarray(); // Test case 1 int[] numbers1 = {8, 2, 4, 7}; int limit1 = 4; System.out.println("Longest subarray length (Test case 1): " + cs.longestSubarray(numbers1, limit1)); // Test case 2 int[] numbers2 = {10, 1, 2, 4, 7, 2}; int limit2 = 5; System.out.println("Longest subarray length (Test case 2): " + cs.longestSubarray(numbers2, limit2)); // Test case 3 int[] numbers3 = {4, 2, 2, 2, 4, 4, 2, 2}; int limit3 = 0; System.out.println("Longest subarray length (Test case 3): " + cs.longestSubarray(numbers3, limit3)); } }
Output:
Longest subarray length (Test case 1): 2 Longest subarray length (Test case 2): 4 Longest subarray length (Test case 3): 3
Complexity analysis:
Time complexity: O(n), where the array's length is n. Time complexity is linear since each element is added to and removed from the deques only once.
Space complexity: In the worst case, O(n) will be used for the deques' space.
Approach 3: Using sliding window with ordered map
ALGORITHM:
Step 1: Create a TreeMap called freqMap to store the frequency of each element in the current window.
Step 2: Initialize an integer maximumLength to store the length of the longest valid subarray.
Step 3: Set an integer l to 0, representing the left pointer of the sliding window.
Step 4: Use a for-loop with r as the right pointer, starting from 0 to the end of the array.
Step 5: Check if the difference between the maximum and minimum keys in freqMap is greater than the limit.
Step 6: If the difference exceeds the limit, enter a while-loop.
Step 7: Inside the while-loop, reduce the frequency of the element at index l in freqMap.
Step 8: If the frequency of this element drops to 0, remove it from freqMap.
Step 9: Increment the left pointer l to shrink the window until the condition is met.
Step 10: After adjusting the window, calculate the current window length (r - l + 1).
Step 11: Update maximumLength if the current window length is greater than maximumLength
Step 12: After processing all elements, return the value of maximumLength.
Filename: ContinuousSubarray.java
import java.util.TreeMap; public class ContinuousSubarray { public int longestSubarray(int[] numbers, int limit) { // Create a TreeMap to keep track of the frequency of each number TreeMapfrequencyMap = new TreeMap<>(); // Stores the maximum length of the subarray int maximumLength = 0; int l = 0; for (int r = 0; r < numbers.length; r++) { // Update the frequency of the current number frequencyMap.put(numbers[r], frequencyMap.getOrDefault(numbers[r], 0) + 1); while (frequencyMap.lastKey() - frequencyMap.firstKey() > limit) { frequencyMap.put(numbers[l], frequencyMap.get(numbers[l]) - 1); if (frequencyMap.get(numbers[l]) == 0) { frequencyMap.remove(numbers[l]); } // To make the window smaller, move the left pointer to the right. l++; } maximumLength = Math.max(maximumLength, r - l + 1); } return maximumLength; } public static void main(String[] args) { ContinuousSubarray s = new ContinuousSubarray(); // Test cases int[] numbers1 = {8, 2, 4, 7}; int limit1 = 4; System.out.println("Longest subarray length (Test case 1): " + s.longestSubarray(numbers1, limit1)); // Output: 2 int[] numbers2 = {10, 1, 2, 4, 7, 2}; int limit2 = 5; System.out.println("Longest subarray length (Test case 2): " + s.longestSubarray(numbers2, limit2)); int[] numbers3 = {4, 2, 2, 2, 4, 4, 2, 2}; int limit3 = 0; System.out.println("Longest subarray length (Test case 3): " + s.longestSubarray(numbers3, limit3)); } }
Output:
Longest subarray length (Test case 1): 2 Longest subarray length (Test case 2): 4 Longest subarray length (Test case 3): 3
Complexity analysis:
Time complexity: The time complexity of the program is O(n log k).
Space complexity: The space complexity of the program is O(n).