← All problems

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

MediumOpen on LeetCodeProblem statement

Problem Statement

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

Medium

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 subarray is less than or equal to limit.

 

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

 

Constraints:

Java

Source file
class Solution {
    private class DblPriorityQ {
        TreeMap<Integer, Integer> pq = new TreeMap<>();

        public DblPriorityQ() {
        }

        public void insert(int key) {
            this.pq.put(key, this.pq.getOrDefault(key, 0) + 1);
        }

        public int getMin() {
            return this.pq.firstEntry().getKey();
        }

        public int getMax() {
            return this.pq.lastEntry().getKey();
        }

        public void remove(int key) {
            int freq = this.pq.get(key);
            if (freq > 1)
                this.pq.put(key, freq - 1);
            else
                this.pq.remove(key);
        }

        public int findAbsDiff() {
            return (getMax() - getMin());
        }

        public String toString() {
            StringBuilder buffer = new StringBuilder();
            for (Map.Entry<Integer, Integer> e : this.pq.entrySet())
                for (int i = 0; i < e.getValue(); i++)
                    buffer.append(e.getKey()).append(", ");
            if (buffer.length() > 0)
                buffer.setLength(buffer.length() - 2);
            return buffer.toString();
        }
    }

    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length, lt = 0, rt = 0, maxLen = 0;
        DblPriorityQ pq = new DblPriorityQ();
        while (rt < n) {
            pq.insert(nums[rt++]);
            while (pq.findAbsDiff() > limit)
                pq.remove(nums[lt++]);
            maxLen = Math.max(maxLen, rt - lt);
            // System.out.println(pq.toString());
        }
        return maxLen;
    }
}