Length of the longest integrable subarray

The length of the longest integrable subarray

author ：Grey

Original address : The length of the longest integrable subarray

Topic link

Cattle guest ： The length of the longest integrable subarray

describe

First give the definition of integrable array ： If an array is sorted , The absolute value of the difference between every two adjacent numbers is 1, Or the array length is 1, Then the array is an integrable array . for example ,[5, 3, 4, 6, 2] The order is [2, 3, 4, 5, 6], The absolute value conforming to the difference between every two adjacent numbers is 1, So this array is an integrable array , Given an array arr, Please return the length of the largest integrable subarray .
for example ,[5, 5, 3, 2, 6, 4, 3] The maximum integrable subarray of is [5, 3, 2, 6, 4], So please return to 5

Data range ：0 <n≤100000, Each number in the array satisfies 0≤val≤10^9

requirement ： The time complexity is O(n^2), The space complexity is O(n)
Advanced ： Time complexity O(nlogn), Spatial complexity O(n)

Violence solution

Enumerate each subarray , Then sort each sub array , Then determine whether it is an integrable array , The complete code is as follows

    public static int getLIL1(int[] arr) {
    
        if (arr == null || arr.length == 0) {
    
            return 0;
        }
        int len = 0;
        // O(N^3 * log N)
        for (int start = 0; start < arr.length; start++) {
    
            for (int end = start; end < arr.length; end++) {
    
                if (isIntegrated(arr, start, end)) {
    
                    len = Math.max(len, end - start + 1);
                }
            }
        }
        return len;
    }

    public static boolean isIntegrated(int[] arr, int left, int right) {
    
        int[] newArr = Arrays.copyOfRange(arr, left, right + 1); // O(N)
        Arrays.sort(newArr); // O(N*logN)
        for (int i = 1; i < newArr.length; i++) {
    
            if (newArr[i - 1] != newArr[i] - 1) {
    
                return false;
            }
        }
        return true;
    }

The time complexity of violent solution is O(N^3*logN), Obviously timeout. .

Optimize the solution

If an array belongs to an integrable array , Then this array must meet the following two conditions ：

The first condition ： There are no duplicate elements in the array .

The second condition ： The difference between the maximum and minimum values in the array is equal to Number of array elements -1.

If the above two conditions are satisfied , It must be an integrable array .

We can set up a HashSet To determine whether the element is repeated .

Complete code

    public static int getLIL2(int[] arr) {
    
        if (arr == null || arr.length == 0) {
    
            return 0;
        }
        int len = 0;
        int max = 0;
        int min = 0;
        HashSet<Integer> set = new HashSet<Integer>();
        for (int l = 0; l < arr.length; l++) {
     
            set.clear();
            max = arr[l];
            min = arr[l];
            for (int r = l; r < arr.length; r++) {
    
                if (set.contains(arr[r])) {
    
                    break;
                }
                set.add(arr[r]);
                max = Math.max(max, arr[r]);
                min = Math.min(min, arr[r]);
                if (max - min == r - l) {
    
                    len = Math.max(len, r - l + 1);
                }
            }
        }
        return len;
    }

The time complexity of the whole algorithm O(N*logN), Meet the requirements .

more

Algorithm and data structure notes