Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/eec1916279c137f18f7d409a986677c1 to your computer and use it in GitHub Desktop.
Save jianminchen/eec1916279c137f18f7d409a986677c1 to your computer and use it in GitHub Desktop.
Find subarray length with target elements and order doesn't matter, target can have duplicates
/*
9:00pm
brute force
target [1,2,2,3]
arr[1,1,1,2,2,2,3,1,2,3]
find subarray length with all target elements and order doesn't matter, target can have duplicates,
3,2,2,1
go through -> start position
1 1
2 2
3 1
Find small smll
*/
public static int FindShortestSubArrayLengthContainingAllKeys(int[] numbers, int[] target)
{
if(numbers == null || target == null || numbers.Length < target.Length)
return -1;
var sLength = numbers.Length;
var tLength = target.Length;
var dict = new Dictionary<int, int>();
foreach(var item in target)
{
if(dict.ContainsKey(item))
dict[item]++;
else
dict.Add(item, 1);
}
int minLength = Int.MaxValue;
int numbersFound = 0;
int start = 0;
for(int index = 0; index < numbers; index++)
{
var current = numbers[index];
if(dict.ContainsKey(current))
continue;
if(dict[current] > 0)
{
numbersFound++;
}
dict[current]--;
// slide left pointer
while(numbersFound == tLength)
{
// record the length
var currentLength = index - start + 1;
minLength = currentLength < minLength ? currentLength : minLength;
// skip left if it is ok
var leftValue = numbers[start];
if(dict.ContainsKey(leftValue))
{
if(dict[leftValue] >=0)
numbersFound--;
dict[leftValue]++;
}
start++;
}
}
// return minimum length
return minLength == int.MaxValue? -1 : minLength;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment