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

Question

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?

Answer 1

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:

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));
}

Answer 2

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); 
    }
}