Find the Longest Subarray

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?

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.

Answer 1

Here's O(1) space, O(n) time. 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

With this code, we keep looking to the element before the current element, checking if their difference is not bigger than one, and if that element is inside the current range of the subarray we're counting. In the end, we need to increment our total, as we want the length of the array.

Python Code:

def longestSub(arr):
    size = len(arr)
    cMax = cMin = arr[0]
    total = current = 0

    cMax = cMin = arr[0]
    #We will use cMax and cMin to keep track of the range of our current subarray
    for i in range(1,size):
        if(abs(arr[i] - arr[i-1]) <= 1):
            if(arr[i] == cMax or arr[i] == cMin):
                current += 1
            else:
                if(current > total):
                    total = current
                current = 1
                cMax = max(arr[i-1],arr[i])
                cMin = min(arr[i-1],arr[i])
        else:
            if(current > total):
                total = current
            cMin = cMax = arr[i]
    return total+1

if __name__ == "__main__":
    arr = [0, 1, 2, 1, 2, 3]    #length = 4; [1,2,1,2]
    print(longestSub(arr))
    arr = [1, 2, 3, 4, 5]       #length = 2; [1,2]
    print(longestSub(arr))
    arr = [1, 1, 1, 3, 3, 2, 2] #length = 4; [3,3,2,2]
    print(longestSub(arr))

Answer 3

I don't think there is any solution better than O(n).

You didn't specify any language, so the pseudocode should look something like this (I ended up writing a python script):

a = [1, 1, 1, 3, 3, 2, 2]
max_solution_arr = []
cur_sol_arr = []
max_length = 0
cur_len = 0

def min_(a, a_i):
  if len(a) == 0:
      return a_i
  return min(a)

def max_(a, a_i):
  if len(a) == 0:
      return a_i
  return max(a)
for i, a_i in enumerate(a):
    if i == 0:
        cur_sol_arr.append(a_i)
        cur_len += 1
    else:
        if (abs(a[i] - min_(cur_sol_arr, a[i])) <= 1) and (abs(a[i] - max_(cur_sol_arr, a[i])) <= 1):
            # solution extend
            cur_sol_arr.append(a_i)
            cur_len += 1
        else:
            # we need to break, update solution
            if cur_len > max_length:
                max_length = cur_len
                max_solution_arr = cur_sol_arr[:] # make a copy here
                cur_sol_arr = [a_i] # delete
                cur_len = 1
# residual

if cur_len > max_length:
   max_length = cur_len
   max_solution_arr = cur_sol_arr # make a copy here

print(max_solution_arr)

The idea is you'll keep an array where you'll continue appending elements unless the condition is not met (> 1 difference), in that case, compare the current array with the max solution so far if the current solution is better just update the max solution.