_1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.md

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 24, 2024

Last updated : July 04, 2024

---

Related Topics : Array, Queue, Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue

Acceptance Rate : 56.65 %

---

    Notes
    We can store the max and min value going in each direction

    Option 1: Brute force all options
    Option 2: Sliding window
        If we're above limit, we shift whichever pointer is leftmost += 1

---

Solutions

• m1438 Daily.java

Java

m1438 Daily.java

 class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int output = 0;

        PriorityQueue<Pair<Integer, Integer>> max = new PriorityQueue<>(Comparator.comparing(Pair::getValue)); // * -1
        PriorityQueue<Pair<Integer, Integer>> min = new PriorityQueue<>(Comparator.comparing(Pair::getValue)); // Default min 

        int indxLeft   = 0;
        int indexRight = 0;

        while (indexRight < nums.length) {
            max.add(new Pair<>(indexRight, -1 * nums[indexRight]));
            min.add(new Pair<>(indexRight, nums[indexRight]));

            while (max.peek().getKey() < indxLeft) {
                max.remove();
            }
            while (min.peek().getKey() < indxLeft) {
                min.remove();
            }

            int maxVal = -1 * max.peek().getValue();
            int maxIndx = max.peek().getKey();

            int minVal = min.peek().getValue();
            int minIndx = min.peek().getKey();
            
            if (maxVal - minVal > limit) {
                if (maxIndx > minIndx) {
                    indxLeft = minIndx + 1;
                    continue;
                } else {
                    indxLeft = maxIndx + 1;
                    continue;
                }
            } else {
                if (indexRight - indxLeft + 1 > output) {
                    output = indexRight - indxLeft + 1;
                }
                indexRight++;
            }
        }

        return output;
    }
}