Longest subArray with no more than two distinct values that differ by no more than 1

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

For Example:

arr = [0, 1, 2, 1, 2, 3] -> length = 4; [1,2,1,2]

arr = [1, 2, 3, 4, 5] -> length = 2; [1,2]

arr = [1, 1, 1, 3, 3, 2, 2] -> length = 4; [3,3,2,2]

I have such code

 public static int longestSubarray(List<Integer> arr) {
        int max = 0;
        Set<Integer> set = new HashSet<>();
        int i = 0;
        int j = 1;
        while (i < arr.size() - 1) {
            set.add(arr.get(i));
            while (j < arr.size() && Math.abs(arr.get(i) - arr.get(j)) < 2) {
                if (!set.contains(arr.get(j))) {
                    if (set.size() == 2) {
                        break;
                    } else {
                        set.add(arr.get(j));
                    }
                }
                ++j;
            }
            max = Math.max(max, j - i);
            j = ++i + 1;
            set.clear();
        }
        return max;
    }

Can there be a better solution?

Yes. Here's a dynamic program with O(n) time and O(1) space. The idea is that we can get the answer for the sequence ending at A[i] by looking at the best sequence ending at A[i-1] that possibly included higher elements, and the best sequence ending at A[i-1] that possibly included lower elements.

JavaScript code:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function f(A){
  if (A.length < 2)
    return A.length;
    
  let best = 1;
  let bestLower = 1;
  let bestHigher = 1;
  
  for (let i=1; i<A.length; i++){
    if (A[i] == A[i-1]){
      bestLower = bestLower + 1;
      bestHigher = bestHigher + 1;
    
    } else if (A[i] - 1 == A[i-1]){
      bestLower = 1 + bestHigher;
      bestHigher = 1;
    
    } else if (A[i] + 1 == A[i-1]){
      bestHigher = 1 + bestLower;
      bestLower = 1;
    
    } else {
      bestLower = 1;
      bestHigher = 1;
    }

    best = Math.max(best, bestLower, bestHigher);
  }
  
  return best;
}

arrays = [
  [0, 1, 2, 1, 2, 3], // length = 4; [1,2,1,2]
  [1, 2, 3, 4, 5], // length = 2; [1,2]
  [1, 1, 1, 3, 3, 2, 2] // length = 4; [3,3,2,2]
];

for (let arr of arrays){
  console.log(JSON.stringify(arr));
  console.log(f(arr));
}

<!-- end snippet -->

C# code:

using System.IO;
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> arr = new List<int>(){ 0, 1, 2, 1, 2, 3};
        List<int> set = new List<int>(); 
        int n = arr.Count;
        int max = 1;
        int i,j;
        for(i=0 ; i<n-1; i++)
        {
            set.Add(arr[i]);
            for(j=i+1; j<n; )
            {
                if(Math.Abs(arr[i]-arr[j])<2)
                {
                    if(!set.Contains(arr[j]))
                    {
                        if(set.Count == 2)
                        break;
                        else
                        set.Add(arr[j]);
                    }  
                }
                else
                break;
            j++;
            }
            max = Math.Max(max,j-i);
            set.Clear();
        }
        Console.WriteLine(max); 
    }
}

refer to this GFG Post
and there replace X by 1

Link : https://www.geeksforgeeks.org/longest-subarray-in-which-absolute-difference-between-any-two-element-is-not-greater-than-x/

Java solution with O(n) time complexity

static int solution(List<Integer> arr) {

	int subArrStart = 0;
	int changedSubArrStart = 0;

	int longSubArrayLen = 0;
	int currSubArrayLen = 0;

	for (int i = 0; i < arr.size(); i++) {

		if (arr.get(subArrStart) == arr.get(i)) {
			currSubArrayLen++;
		} else if (Math.abs(arr.get(subArrStart) - arr.get(i)) == 1) {
			if (subArrStart == changedSubArrStart) {
				changedSubArrStart = i;
			}
			currSubArrayLen++;
		} else if (Math.abs(arr.get(changedSubArrStart) - arr.get(i)) == 1) {
			subArrStart = changedSubArrStart;
			currSubArrayLen = i - subArrStart + 1;
		} else {
			subArrStart = i;
			changedSubArrStart = i;
			currSubArrayLen = 1;
		}

		longSubArrayLen = Math.max(longSubArrayLen, currSubArrayLen);
	}
	return longSubArrayLen;
}