Longest Subarray

 Given an array of integers, what is the length of the longest subarray containing no more than two distinct values such that the distinct values differ by no more than 1?

Example

arr = [0,1,2,1,2,3]

The largest such subarray has length 4: [1,2,1,2].

 

arr = [1, 1, 1, 3, 3, 2, 2]

The largest such subarray has length 4: [3, 3, 2, 2]. The values 1 and 3 differ by more than 1 so [1, 1, 1, 3, 3] is not valid.

 

Function Description

Complete the function longestSubarray in the editor below.

 

longestSubarray has the following parameter(s):

    int arr[n]:  an array of integers

Returns:

    int:  the length of the longest subarray

Constraints

• The longest subarray will have fewer than 35 elements.
• 1 ≤ n ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁹

Input Format For Custom Testing

The first line contains an integer, n, denoting the number of elements in arr.
Each line i of the n subsequent lines contains a single integer denoting arr[i].

Sample Case 0

Sample Input For Custom Testing

5
1
2
3
4
5

Sample Output

2

Explanation

n = 5

arr = [1, 2, 3, 4, 5]

 

All elements are distinct, so any subarray of length 2 is the maximum.

Sample Case 1

Sample Input For Custom Testing

3
2
2
1

Sample Output

3

Explanation

n = 3

arr = [2, 2, 1]

The maximum subarray is length 3 (i.e. the entire array), as it contains only 2 distinct values

Solution(Java):-

import java.io.*;

import java.math.*;

import java.security.*;

import java.text.*;

import java.util.*;

import java.util.concurrent.*;

import java.util.function.*;

import java.util.regex.*;

import java.util.stream.*;

import static java.util.stream.Collectors.joining;

import static java.util.stream.Collectors.toList;

class Result {

    /*

     * Complete the 'longestSubarray' function below.

     *

     * The function is expected to return an INTEGER.

     * The function accepts INTEGER_ARRAY arr as parameter.

     */

    public static int longestSubarray(List<Integer> arr) {

    // Write your code here

        int m = 0;

        Set<Integer> s = new HashSet<>();

        int i = 0;

        int j = 1;

        if(arr.size()==1)

        return 1;

        while (i < arr.size() - 1)

         {

            s.add(arr.get(i));

            while (j < arr.size() && Math.abs(arr.get(i) - arr.get(j)) < 2)

             {

                if (!s.contains(arr.get(j))) {

                    if (s.size() == 2) {

                        break;

                    } else {

                        s.add(arr.get(j));

                    }

                }

                ++j;

            }

            m = Math.max(m, j - i);

            j = ++i + 1;

            s.clear();

        }

        return m;

    }

}

public class Solution {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int arrCount = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> arr = IntStream.range(0, arrCount).mapToObj(i -> {

            try {

                return bufferedReader.readLine().replaceAll("\\s+$", "");

            } catch (IOException ex) {

                throw new RuntimeException(ex);

            }

        })

            .map(String::trim)

            .map(Integer::parseInt)

            .collect(toList());

        int result = Result.longestSubarray(arr);

        bufferedWriter.write(String.valueOf(result));

        bufferedWriter.newLine();

        bufferedReader.close();

        bufferedWriter.close();

    }

}