Codesignal | longestInversionalSubarray

You are given three arrays of integers a, b, and c. Your task is to find the longest contiguous subarray of a containing only elements that appear in b but do not appear in c.

Return this longest subarray. If there is more than one longest subarray satisfying these conditions, return any of these possible subarrays.

Example

  1. For a = [2, 1, 7, 1, 1, 5, 3, 5, 2, 1, 1, 1], b = [1, 3, 5], and c = [2, 3], the output can be longestInversionalSubarray(a, b, c) = [1, 1, 5].

There is no contiguous subarray of length 4 satisfying all the requirements:

a[0..3] = [2, 1, 7, 1] contains the number a[2] = 7, which doesn't appear in b;
a[1..4] = [1, 7, 1, 1] contains the number a[2] = 7, which doesn't appear in b;
a[2..5] = [7, 1, 1, 5] contains the number a[2] = 7, which doesn't appear in b;
a[3..6] = [1, 1, 5, 3] contains the number a[6] = 3, which does appear in c (which is prohibited);
a[4..7] = [1, 5, 3, 5] contains the number a[6] = 3, which does appear in c;
a[5..8] = [5, 3, 5, 2] contains the number a[6] = 3, which does appear in c;
a[6..9] = [3, 5, 2, 1] contains the number a[6] = 3, which does appear in c;
a[7..10] = [5, 2, 1, 1] contains the number a[8] = 2, which doesn't appear in b;
a[8..11] = [2, 1, 1, 1] contains the number a[8] = 2, which doesn't appear in b.
There are two possible contiguous subarrays of length 3 satisfying all the requirements:

a[3..5] = [1, 1, 5]: both numbers 1 and 5 appear in b, and both of these numbers don't appear in c.
a[9..11] = [1, 1, 1]: the number 1 appears in b, and doesn't appear in c.
example

As you can see, the longest consecutive subarrays of a that fulfill the conditions are a[3..5] = [1, 1, 5] and a[9..11] = [1, 1, 1]. Both of these answers are acceptable.

  1. For a = [1, 2, 3], b = [], and c = [], the output should be longestInversionalSubarray(a, b, c) = [].

Since b is empty, there are no elements that appear in b and not c. So the answer is [].


My solution below didnt pass all the hidden test cases, could someone help thinking of exs that wouldnt pass and the correct approach? What I'm doing is keeping track of the maxLength of a contiguous subarr that meets the conditions and updating it whenever we fnd a contiguous subarr that's longer. Keeping track of the start index as well when we fiind the maxLen subarray

def longestInversionalSubarray(a, b, c):
	b = set(b).difference(set(c))

	maxLen, start_i_max, start_i, currLen = 0, 0, 0, 0

	for i, num in enumerate(a):      
		if num in b:
			currLen += 1
		else:
			if maxLen < currLen:
				maxLen = currLen
				start_i_max = start_i
			currLen = 0
			start_i = i+1

	# if we end on a num in set b:
	if maxLen < currLen:
		maxLen = currLen
		start_i_max = start_i

	return a[start_i_max:start_i_max+maxLen]
Comments (2)