An integer K and a non-empty array A consisting of N integers are given.
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A.
A bounded slice is a slice in which the difference between the maximum and minimum values in the slice is less than or equal to K. More precisely it is a slice, such that max(A[P], A[P + 1], ..., A[Q]) − min(A[P], A[P + 1], ..., A[Q]) ≤ K.
The goal is to calculate the number of bounded slices.
For example, consider K = 2 and array A such that:
A[0] = 3 A[1] = 5 A[2] = 7 A[3] = 6 A[4] = 3There are exactly nine bounded slices: (0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (4, 4).
Write a function:
function solution(K, A);
that, given an integer K and a non-empty array A of N integers, returns the number of bounded slices of array A.
If the number of bounded slices is greater than 1,000,000,000, the function should return 1,000,000,000.
For example, given:
A[0] = 3 A[1] = 5 A[2] = 7 A[3] = 6 A[4] = 3the function should return 9, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- K is an integer within the range [0..1,000,000,000];
- each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].
function searchValueIdx(sortedValueArray, value)
{
var searchValueIdx = sortedValueArray.length;
searchValueIdx = (searchValueIdx + 1) >> 1;
var step = searchValueIdx;
if (searchValueIdx >= sortedValueArray.length)
{
searchValueIdx = sortedValueArray.length - 1;
}
var foundValueIdx = undefined;
while (foundValueIdx == undefined)
{
var step = (step + 1) >> 1;
var searchEntry = sortedValueArray[searchValueIdx];
var searchValue = searchEntry.value;
if (searchValue < value)
{
if (step > 1)
{
searchValueIdx += step;
if (searchValueIdx >= sortedValueArray.length)
{
searchValueIdx = sortedValueArray.length - 1;
}
}
else
{
while (searchValueIdx < sortedValueArray.length && sortedValueArray[searchValueIdx].value <= value)
{
foundValueIdx = searchValueIdx;
searchValueIdx++;
}
}
}
else if (searchValue > value)
{
if (step > 1)
{
searchValueIdx -= step;
if (searchValueIdx < 0)
{
searchValueIdx = 0;
}
}
else
{
while (searchValueIdx >= 0 && sortedValueArray[searchValueIdx].value > value)
{
searchValueIdx--;
foundValueIdx = searchValueIdx;
}
}
}
else
{
foundValueIdx = searchValueIdx;
}
}
return foundValueIdx;
}
function insertValue(sortedValueArray, value, idx_A)
{
if (sortedValueArray.length == 0)
{
sortedValueArray.push(
{
value: value,
idx_AList: [ idx_A ]
});
return sortedValueArray;
}
var valueIdx = searchValueIdx(sortedValueArray, value);
if (valueIdx == -1)
{
return [ {
value: value,
idx_AList: [ idx_A ]
} ].concat(sortedValueArray);
}
else if (sortedValueArray[valueIdx].value == value)
{
sortedValueArray[valueIdx].idx_AList.push(idx_A);
}
else
{
sortedValueArray.splice(valueIdx + 1, 0,
{
value: value, idx_AList: [ idx_A ]
});
}
return sortedValueArray;
}
function cleanupDroppedIdx_A(sortedValueArray, tailIdx_A, valueIdx)
{
var droppedEntry = false;
var idx_AList;
var subIdx;
idx_AList = sortedValueArray[valueIdx].idx_AList;
if (idx_AList[0] < tailIdx_A)
{
subIdx = idx_AList.length - 1;
while (subIdx >= 0 && idx_AList[subIdx] >= tailIdx_A)
{
subIdx--;
}
if (subIdx == idx_AList.length - 1)
{
sortedValueArray.splice(valueIdx, 1);
droppedEntry = true;
}
else
{
idx_AList.splice(0, subIdx);
valueIdx++;
}
}
return droppedEntry;
}
function solution(K, A) {
var kMaxSlices = 1000000000;
var headIdx_A;
var tailIdx_A = 0;
var slidingMaxIdx_A = 0;
var slidingMaxValue = A[0];
var sortedValueArray = [ { value: slidingMaxValue, idx_AList: [ slidingMaxIdx_A ] } ];
var slidingMinIdx_A = 0;
var slidingMinValue = A[0];
var slidingRange = 0;
var numBoundedSlices = 1;
var value;
var valueIdx;
var cutOffValue;
var cutOffValueIdx;
var searchTailValueIdx;
var searchMinValueIdx;
var searchMaxValueIdx;
var idx_AList;
var droppingValueIdx_A;
var potentialTailIdx_A;
var searchEntry;
for (headIdx_A = 1; headIdx_A < A.length; headIdx_A++)
{
value = A[headIdx_A];
sortedValueArray = insertValue(sortedValueArray, value, headIdx_A);
if (slidingMaxValue < value)
{
slidingMaxValue = value;
slidingMaxIdx_A = headIdx_A;
slidingRange = slidingMaxValue - slidingMinValue;
if (slidingRange > K)
{
cutOffValue = slidingMaxValue - K - 1;
cutOffValueIdx = searchValueIdx(sortedValueArray, cutOffValue);
searchTailValueIdx = cutOffValueIdx;
while (searchTailValueIdx >= 0)
{
idx_AList = sortedValueArray[searchTailValueIdx].idx_AList;
searchTailValueIdx--;
droppingValueIdx_A = idx_AList[idx_AList.length - 1];
potentialTailIdx_A = droppingValueIdx_A + 1;
if (tailIdx_A < potentialTailIdx_A)
{
tailIdx_A = potentialTailIdx_A;
}
}
if (cutOffValueIdx >= 0)
{
sortedValueArray.splice(0,cutOffValueIdx + 1);
}
searchMinValueIdx = 0;
searchEntry = undefined;
while (searchMinValueIdx < sortedValueArray.length && searchEntry == undefined)
{
droppedEntry = cleanupDroppedIdx_A(sortedValueArray, tailIdx_A, searchMinValueIdx);
if (! droppedEntry)
{
searchEntry = sortedValueArray[searchMinValueIdx];
slidingMinIdx_A = searchEntry.idx_AList[0];
slidingMinValue = searchEntry.value;
}
}
}
}
if (slidingMinValue > value)
{
slidingMinValue = value;
slidingMinIdx_A = headIdx_A;
slidingRange = slidingMaxValue - slidingMinValue;
if (slidingRange > K)
{
cutOffValue = slidingMinValue + K + 1;
cutOffValueIdx = searchValueIdx(sortedValueArray, cutOffValue);
if (cutOffValueIdx < sortedValueArray.length && sortedValueArray[cutOffValueIdx].value < cutOffValue)
{
cutOffValueIdx++;
}
searchTailValueIdx = cutOffValueIdx;
while (searchTailValueIdx < sortedValueArray.length)
{
idx_AList = sortedValueArray[searchTailValueIdx].idx_AList;
searchTailValueIdx++;
droppingValueIdx_A = idx_AList[idx_AList.length - 1];
potentialTailIdx_A = droppingValueIdx_A + 1;
if (tailIdx_A < potentialTailIdx_A)
{
tailIdx_A = potentialTailIdx_A;
}
}
if (cutOffValueIdx < sortedValueArray.length)
{
sortedValueArray.splice(cutOffValueIdx, sortedValueArray.length - cutOffValueIdx);
}
searchMaxValueIdx = sortedValueArray.length - 1;
searchEntry = undefined;
while (searchMaxValueIdx >= 0 && searchEntry == undefined)
{
droppedEntry = cleanupDroppedIdx_A(sortedValueArray, tailIdx_A, searchMaxValueIdx);
if (droppedEntry)
{
searchMaxValueIdx = sortedValueArray.length - 1;
}
else
{
searchEntry = sortedValueArray[searchMaxValueIdx];
slidingMaxIdx_A = searchEntry.idx_AList[0];
slidingMaxValue = searchEntry.value;
}
}
}
}
numBoundedSlices += headIdx_A - tailIdx_A + 1;
if (numBoundedSlices >= kMaxSlices)
{
numBoundedSlices = kMaxSlices;
break;
}
}
return numBoundedSlices;
}
function searchValueIdx(sortedValueArray, value)
{
var searchValueIdx = sortedValueArray.length;
searchValueIdx = (searchValueIdx + 1) >> 1;
var step = searchValueIdx;
if (searchValueIdx >= sortedValueArray.length)
{
searchValueIdx = sortedValueArray.length - 1;
}
var foundValueIdx = undefined;
while (foundValueIdx == undefined)
{
var step = (step + 1) >> 1;
var searchEntry = sortedValueArray[searchValueIdx];
var searchValue = searchEntry.value;
if (searchValue < value)
{
if (step > 1)
{
searchValueIdx += step;
if (searchValueIdx >= sortedValueArray.length)
{
searchValueIdx = sortedValueArray.length - 1;
}
}
else
{
while (searchValueIdx < sortedValueArray.length && sortedValueArray[searchValueIdx].value <= value)
{
foundValueIdx = searchValueIdx;
searchValueIdx++;
}
}
}
else if (searchValue > value)
{
if (step > 1)
{
searchValueIdx -= step;
if (searchValueIdx < 0)
{
searchValueIdx = 0;
}
}
else
{
while (searchValueIdx >= 0 && sortedValueArray[searchValueIdx].value > value)
{
searchValueIdx--;
foundValueIdx = searchValueIdx;
}
}
}
else
{
foundValueIdx = searchValueIdx;
}
}
return foundValueIdx;
}
function insertValue(sortedValueArray, value, idx_A)
{
if (sortedValueArray.length == 0)
{
sortedValueArray.push(
{
value: value,
idx_AList: [ idx_A ]
});
return sortedValueArray;
}
var valueIdx = searchValueIdx(sortedValueArray, value);
if (valueIdx == -1)
{
return [ {
value: value,
idx_AList: [ idx_A ]
} ].concat(sortedValueArray);
}
else if (sortedValueArray[valueIdx].value == value)
{
sortedValueArray[valueIdx].idx_AList.push(idx_A);
}
else
{
sortedValueArray.splice(valueIdx + 1, 0,
{
value: value, idx_AList: [ idx_A ]
});
}
return sortedValueArray;
}
function cleanupDroppedIdx_A(sortedValueArray, tailIdx_A, valueIdx)
{
var droppedEntry = false;
var idx_AList;
var subIdx;
idx_AList = sortedValueArray[valueIdx].idx_AList;
if (idx_AList[0] < tailIdx_A)
{
subIdx = idx_AList.length - 1;
while (subIdx >= 0 && idx_AList[subIdx] >= tailIdx_A)
{
subIdx--;
}
if (subIdx == idx_AList.length - 1)
{
sortedValueArray.splice(valueIdx, 1);
droppedEntry = true;
}
else
{
idx_AList.splice(0, subIdx);
valueIdx++;
}
}
return droppedEntry;
}
function solution(K, A) {
var kMaxSlices = 1000000000;
var headIdx_A;
var tailIdx_A = 0;
var slidingMaxIdx_A = 0;
var slidingMaxValue = A[0];
var sortedValueArray = [ { value: slidingMaxValue, idx_AList: [ slidingMaxIdx_A ] } ];
var slidingMinIdx_A = 0;
var slidingMinValue = A[0];
var slidingRange = 0;
var numBoundedSlices = 1;
var value;
var valueIdx;
var cutOffValue;
var cutOffValueIdx;
var searchTailValueIdx;
var searchMinValueIdx;
var searchMaxValueIdx;
var idx_AList;
var droppingValueIdx_A;
var potentialTailIdx_A;
var searchEntry;
for (headIdx_A = 1; headIdx_A < A.length; headIdx_A++)
{
value = A[headIdx_A];
sortedValueArray = insertValue(sortedValueArray, value, headIdx_A);
if (slidingMaxValue < value)
{
slidingMaxValue = value;
slidingMaxIdx_A = headIdx_A;
slidingRange = slidingMaxValue - slidingMinValue;
if (slidingRange > K)
{
cutOffValue = slidingMaxValue - K - 1;
cutOffValueIdx = searchValueIdx(sortedValueArray, cutOffValue);
searchTailValueIdx = cutOffValueIdx;
while (searchTailValueIdx >= 0)
{
idx_AList = sortedValueArray[searchTailValueIdx].idx_AList;
searchTailValueIdx--;
droppingValueIdx_A = idx_AList[idx_AList.length - 1];
potentialTailIdx_A = droppingValueIdx_A + 1;
if (tailIdx_A < potentialTailIdx_A)
{
tailIdx_A = potentialTailIdx_A;
}
}
if (cutOffValueIdx >= 0)
{
sortedValueArray.splice(0,cutOffValueIdx + 1);
}
searchMinValueIdx = 0;
searchEntry = undefined;
while (searchMinValueIdx < sortedValueArray.length && searchEntry == undefined)
{
droppedEntry = cleanupDroppedIdx_A(sortedValueArray, tailIdx_A, searchMinValueIdx);
if (! droppedEntry)
{
searchEntry = sortedValueArray[searchMinValueIdx];
slidingMinIdx_A = searchEntry.idx_AList[0];
slidingMinValue = searchEntry.value;
}
}
}
}
if (slidingMinValue > value)
{
slidingMinValue = value;
slidingMinIdx_A = headIdx_A;
slidingRange = slidingMaxValue - slidingMinValue;
if (slidingRange > K)
{
cutOffValue = slidingMinValue + K + 1;
cutOffValueIdx = searchValueIdx(sortedValueArray, cutOffValue);
if (cutOffValueIdx < sortedValueArray.length && sortedValueArray[cutOffValueIdx].value < cutOffValue)
{
cutOffValueIdx++;
}
searchTailValueIdx = cutOffValueIdx;
while (searchTailValueIdx < sortedValueArray.length)
{
idx_AList = sortedValueArray[searchTailValueIdx].idx_AList;
searchTailValueIdx++;
droppingValueIdx_A = idx_AList[idx_AList.length - 1];
potentialTailIdx_A = droppingValueIdx_A + 1;
if (tailIdx_A < potentialTailIdx_A)
{
tailIdx_A = potentialTailIdx_A;
}
}
if (cutOffValueIdx < sortedValueArray.length)
{
sortedValueArray.splice(cutOffValueIdx, sortedValueArray.length - cutOffValueIdx);
}
searchMaxValueIdx = sortedValueArray.length - 1;
searchEntry = undefined;
while (searchMaxValueIdx >= 0 && searchEntry == undefined)
{
droppedEntry = cleanupDroppedIdx_A(sortedValueArray, tailIdx_A, searchMaxValueIdx);
if (droppedEntry)
{
searchMaxValueIdx = sortedValueArray.length - 1;
}
else
{
searchEntry = sortedValueArray[searchMaxValueIdx];
slidingMaxIdx_A = searchEntry.idx_AList[0];
slidingMaxValue = searchEntry.value;
}
}
}
}
numBoundedSlices += headIdx_A - tailIdx_A + 1;
if (numBoundedSlices >= kMaxSlices)
{
numBoundedSlices = kMaxSlices;
break;
}
}
return numBoundedSlices;
}
function searchValueIdx(sortedValueArray, value)
{
var searchValueIdx = sortedValueArray.length;
searchValueIdx = (searchValueIdx + 1) >> 1;
var step = searchValueIdx;
if (searchValueIdx >= sortedValueArray.length)
{
searchValueIdx = sortedValueArray.length - 1;
}
var foundValueIdx = undefined;
while (foundValueIdx == undefined)
{
var step = (step + 1) >> 1;
var searchEntry = sortedValueArray[searchValueIdx];
var searchValue = searchEntry.value;
if (searchValue < value)
{
if (step > 1)
{
searchValueIdx += step;
if (searchValueIdx >= sortedValueArray.length)
{
searchValueIdx = sortedValueArray.length - 1;
}
}
else
{
while (searchValueIdx < sortedValueArray.length && sortedValueArray[searchValueIdx].value <= value)
{
foundValueIdx = searchValueIdx;
searchValueIdx++;
}
}
}
else if (searchValue > value)
{
if (step > 1)
{
searchValueIdx -= step;
if (searchValueIdx < 0)
{
searchValueIdx = 0;
}
}
else
{
while (searchValueIdx >= 0 && sortedValueArray[searchValueIdx].value > value)
{
searchValueIdx--;
foundValueIdx = searchValueIdx;
}
}
}
else
{
foundValueIdx = searchValueIdx;
}
}
return foundValueIdx;
}
function insertValue(sortedValueArray, value, idx_A)
{
if (sortedValueArray.length == 0)
{
sortedValueArray.push(
{
value: value,
idx_AList: [ idx_A ]
});
return sortedValueArray;
}
var valueIdx = searchValueIdx(sortedValueArray, value);
if (valueIdx == -1)
{
return [ {
value: value,
idx_AList: [ idx_A ]
} ].concat(sortedValueArray);
}
else if (sortedValueArray[valueIdx].value == value)
{
sortedValueArray[valueIdx].idx_AList.push(idx_A);
}
else
{
sortedValueArray.splice(valueIdx + 1, 0,
{
value: value, idx_AList: [ idx_A ]
});
}
return sortedValueArray;
}
function cleanupDroppedIdx_A(sortedValueArray, tailIdx_A, valueIdx)
{
var droppedEntry = false;
var idx_AList;
var subIdx;
idx_AList = sortedValueArray[valueIdx].idx_AList;
if (idx_AList[0] < tailIdx_A)
{
subIdx = idx_AList.length - 1;
while (subIdx >= 0 && idx_AList[subIdx] >= tailIdx_A)
{
subIdx--;
}
if (subIdx == idx_AList.length - 1)
{
sortedValueArray.splice(valueIdx, 1);
droppedEntry = true;
}
else
{
idx_AList.splice(0, subIdx);
valueIdx++;
}
}
return droppedEntry;
}
function solution(K, A) {
var kMaxSlices = 1000000000;
var headIdx_A;
var tailIdx_A = 0;
var slidingMaxIdx_A = 0;
var slidingMaxValue = A[0];
var sortedValueArray = [ { value: slidingMaxValue, idx_AList: [ slidingMaxIdx_A ] } ];
var slidingMinIdx_A = 0;
var slidingMinValue = A[0];
var slidingRange = 0;
var numBoundedSlices = 1;
var value;
var valueIdx;
var cutOffValue;
var cutOffValueIdx;
var searchTailValueIdx;
var searchMinValueIdx;
var searchMaxValueIdx;
var idx_AList;
var droppingValueIdx_A;
var potentialTailIdx_A;
var searchEntry;
for (headIdx_A = 1; headIdx_A < A.length; headIdx_A++)
{
value = A[headIdx_A];
sortedValueArray = insertValue(sortedValueArray, value, headIdx_A);
if (slidingMaxValue < value)
{
slidingMaxValue = value;
slidingMaxIdx_A = headIdx_A;
slidingRange = slidingMaxValue - slidingMinValue;
if (slidingRange > K)
{
cutOffValue = slidingMaxValue - K - 1;
cutOffValueIdx = searchValueIdx(sortedValueArray, cutOffValue);
searchTailValueIdx = cutOffValueIdx;
while (searchTailValueIdx >= 0)
{
idx_AList = sortedValueArray[searchTailValueIdx].idx_AList;
searchTailValueIdx--;
droppingValueIdx_A = idx_AList[idx_AList.length - 1];
potentialTailIdx_A = droppingValueIdx_A + 1;
if (tailIdx_A < potentialTailIdx_A)
{
tailIdx_A = potentialTailIdx_A;
}
}
if (cutOffValueIdx >= 0)
{
sortedValueArray.splice(0,cutOffValueIdx + 1);
}
searchMinValueIdx = 0;
searchEntry = undefined;
while (searchMinValueIdx < sortedValueArray.length && searchEntry == undefined)
{
droppedEntry = cleanupDroppedIdx_A(sortedValueArray, tailIdx_A, searchMinValueIdx);
if (! droppedEntry)
{
searchEntry = sortedValueArray[searchMinValueIdx];
slidingMinIdx_A = searchEntry.idx_AList[0];
slidingMinValue = searchEntry.value;
}
}
}
}
if (slidingMinValue > value)
{
slidingMinValue = value;
slidingMinIdx_A = headIdx_A;
slidingRange = slidingMaxValue - slidingMinValue;
if (slidingRange > K)
{
cutOffValue = slidingMinValue + K + 1;
cutOffValueIdx = searchValueIdx(sortedValueArray, cutOffValue);
if (cutOffValueIdx < sortedValueArray.length && sortedValueArray[cutOffValueIdx].value < cutOffValue)
{
cutOffValueIdx++;
}
searchTailValueIdx = cutOffValueIdx;
while (searchTailValueIdx < sortedValueArray.length)
{
idx_AList = sortedValueArray[searchTailValueIdx].idx_AList;
searchTailValueIdx++;
droppingValueIdx_A = idx_AList[idx_AList.length - 1];
potentialTailIdx_A = droppingValueIdx_A + 1;
if (tailIdx_A < potentialTailIdx_A)
{
tailIdx_A = potentialTailIdx_A;
}
}
if (cutOffValueIdx < sortedValueArray.length)
{
sortedValueArray.splice(cutOffValueIdx, sortedValueArray.length - cutOffValueIdx);
}
searchMaxValueIdx = sortedValueArray.length - 1;
searchEntry = undefined;
while (searchMaxValueIdx >= 0 && searchEntry == undefined)
{
droppedEntry = cleanupDroppedIdx_A(sortedValueArray, tailIdx_A, searchMaxValueIdx);
if (droppedEntry)
{
searchMaxValueIdx = sortedValueArray.length - 1;
}
else
{
searchEntry = sortedValueArray[searchMaxValueIdx];
slidingMaxIdx_A = searchEntry.idx_AList[0];
slidingMaxValue = searchEntry.value;
}
}
}
}
numBoundedSlices += headIdx_A - tailIdx_A + 1;
if (numBoundedSlices >= kMaxSlices)
{
numBoundedSlices = kMaxSlices;
break;
}
}
return numBoundedSlices;
}
The solution obtained perfect score.