I figured out how to do this using two loops, but wondering if there is a better way to approach this contiguous subarray question? My hunch is to use the sliding window pattern, but I've been struggling with the set up and whether you can solve this in one-pass. If someone could help out with clear pseudocoding or in Javascript, I'd appreciate it.
You are given an array of integers numbers and an integer k.
Your task is to count the number of contiguous subarrays containing at
least k numbers which appear exactly once in this subarray.
Example
For numbers = [1, 2, 1, 1] and k = 2, the output should be uniquesOnSegment(numbers, k) = 2.
There are 2 subarrays satistfying the criteria of containing at least k = 2 numbers exactly once:
numbers[0..1] = [1, 2]
numbers[1..2] = [2, 1]
Note that the subarray numbers[0..2] = [1, 2, 1] is not counted because
the number 1 appears twice, so only one number appears exactly once in this subarray.
For numbers = [1, 2, 3, 4, 1] and k = 3, the output should be uniquesOnSegment(numbers, k) = 6.
There are 6 subarrays that satisfy the criteria of containing at least k = 3 numbers occuring exactly once:
numbers[0..2] = [1, 2, 3]
numbers[0..3] = [1, 2, 3, 4]
numbers[0..4] = [1, 2, 3, 4, 1]
numbers[1..3] = [2, 3, 4]
numbers[1..4] = [2, 3, 4, 1]
numbers[2..4] = [3, 4, 1]
For numbers = [5, 5, 5, 5] and k = 2, the output should be uniquesOnSegment(numbers, k) = 0.
There are no subarrays with at least k = 2 different numbers.
For numbers = [5, 5, 5, 5] and k = 1, the output should be uniquesOnSegment(numbers, k) = 4.
There are 4 subarrays that satisfy the criteria of containing at least k = 1 occuring exactly once:
numbers[0..0] = [5]
numbers[1..1] = [5]
numbers[2..2] = [5]
numbers[3..3] = [5]
Two loops solution (is there a more optimal way?):
function uniquesOnSegment(arr, k) {
let countUniqueSubarrays = 0;
for (let i = 0; i < arr.length; i++) {
let windowSubarray = new Set();
let subarray = [];
let nonUniques = 0;
for (let j = i; j < arr.length; j++) {
const currentNum = arr[j];
subarray.push(currentNum);
if (windowSubarray.has(currentNum)) {
nonUniques++;
} else {
windowSubarray.add(currentNum);
}
if (windowSubarray.size - nonUniques >= k) {
countUniqueSubarrays++;
}
}
}
return countUniqueSubarrays;
}
console.log(uniquesOnSegment([1, 2, 3, 4, 1], 3)); // 6
console.log(uniquesOnSegment([1, 2, 1, 1], 2)); // 2
Here I could do it in 2 nested loops ( counting searching for max in Object.values ). I think it can be further improved but this is what occurred to me so far.
const numbers = [5,5,5,5]
const k = 1
const numbers1 = [1, 2, 3, 4, 1]
const k1 = 2
const numbers2 = [1, 2, 2, 4, 1]
const k2 = 3
var countSubArray = function(arr, k) {
let base = {}
let count = 1; //We are hoping the next contiguous subarray will have all uniques
for ( let i = 0; i < k; i++ ) {
if(base[arr[i]] === undefined)
base[arr[i]] = 0
else
count -= 1
base[arr[i]] += 1
}
// Now sliding window starting at i = 1
for ( let i = 1; i < arr.length - k + 1; i++ ) {
count += 1;
if ( base[arr[i - 1]] > 0 ){
base[arr[i - 1] ] -= 1
if ( base[arr[i - 1]] > 1 ){
count -= 1
} else {
delete base[arr[i - 1]]
if (base[arr[i + k]] === undefined ) {
base[arr[i + k]] = 1
} else {
count -= 1
}
if ( Math.max(...Object.values(base)) > 1 ) {
count -= 1
}
}
}
}
return count
}
console.log(countSubArray(numbers, k))
console.log(countSubArray(numbers1, k1))
console.log(countSubArray(numbers2, k2))