Q:

Range-based intersection of n-number of arrays

Lets say I have the following three arrays:
[
  [100, 110, 200, 300, 400],
  [40, 90, 99, 150, 200],
  [101, 202, 404, 505]
]

how would I go about writing a function getIntersectingRanges(arrays, range) which would return all ranges of max 'width' of range containing 1 or more elements from all arrays.
So, if range=15 then it would return [[100, 90, 99, 101], [100, 110, 99, 101], [200, 200, 202]]. Each of those arrays contains at least one element from each input range and the total 'width' of the range is less or equal to 15 (first one is 11, second one 11 as well and the third one just 3).
It's conceptually incredibly simple but I have been having a really hard to figuring out how to write such a function. Like I am not looking for a fully fleshed out solution, all I need is the basis of the algorithm allowing me to do so (though I will obviously also gladly accept a fully written function).

As some people seem to have a problem understanding this, let me give a few more simple examples (though writing these by hand is a bit hard, so excuse me if I make a mistake somewhere):

input:   [[10, 20, 30, 40, 50, 60, 70, 80, 90], [55, 84]]
range:  5
output: [[50, 55], [55, 60], [80, 84]]
input:   [[10, 20, 30], [40, 50]]
range:  10
output: [[30, 40]]
input:   [[15, 30, 699], [16, 800], [10, 801], [11, 803]]
range:  10
output: [[15, 16, 10, 11]]

So my approach has been to first only take the first two arrays, next search for all elements from the first array in the second array ± range. So far it seems to make sense, but given this start it seems impossible to match both the first and the second result from the example above... so any help would be greatly appreciated.

A:

This solution features an object with the values as key and as value the indices of the array of the given arrays.
The additional approach is the speeding of the lookup items, which have a short circuit if the index is outside the area of a possible finding.

Example
Given array:
[
    [100, 110, 200, 300, 400],
    [40, 90, 99, 150, 200],
    [101, 202, 404, 505]
]

Given range: 15
First sort the given values ascending.  
Then iterate from the smallest value to the highest and look if values in range are in all arrays.  
Array Values                                               Comment
----- ---------------------------------------------------- --------------------------------------
0                100     110     200     300 400
1     40  90  99             150 200
2                    101             202         404 505
       1                                                   here is no other value in this range
           1   1   0   2                                <- first group, values are in all arrays
               1   0   2   0                            <- second group, values are in all arrays
                   0   2   0                               only values of two arrays
                       2   0                               only values of two arrays
                               1                           here is no other value in this range
                                  01   2                <- third group, values are in all arrays
                                       2                   here is no other value in this range
                                           0               here is no other value in this range
                                               0   2       only values of two arrays
                                                      2    here is no other value in this range

Result:
[
    [[100], [90, 99], [101]],
    [[100, 110], [99], [101]],
    [[200], [200], [202]]
]

function intersection(arrays, range) {
    var result = [],                   // result array
        items = [],                    // all distinct items from arrays
        indices = {},                  // object for the array indices
        temp,                          // temp array, for pushing a result
        i,                             // counter for pushing values to temp
        left = 0, pos = 0, lastPos,    // look up range
        allArrays,                     // temporary array for indicating if index is included
        arraysLength = arrays.length,  // arrays length
        itemLength,                    // length of all items
        leftValue,                     // literally the value from the left range
        emptyArrays;                   // template for the test if all arrays are used

    emptyArrays = Array.apply(Array, { length: arraysLength });
    arrays.forEach(function (a, i) {
        a.forEach(function (item) {
            indices[item] = indices[item] || [];
            indices[item].push(i);
        });
    });
    items = Object.keys(indices).map(Number).sort(function (a, b) { return a - b; });
    itemLength = items.length;
    do {
        temp = [];
        allArrays = emptyArrays.slice(0);
        leftValue = items[left];
        pos = left;
        while (pos < itemLength && items[pos] <= range + leftValue) {
            temp.push(items[pos]);
            indices[items[pos]].forEach(function (i) {
                allArrays[i] = true;
            });
            pos++;
        }
        pos !== lastPos && allArrays.every(function (a) { return a; }) && result.push(temp);
        left++;
        lastPos = pos;
    } while (pos < itemLength);
    return result;
}

function test(arrays, range) {
    var result = intersection(arrays, range);
    document.write("<br>arrays:", JSON.stringify(arrays));
    document.write("<br>range:", range);
    document.write("<br>result:", JSON.stringify(result));
    document.write("<br>---");
}


test([[100, 110, 200, 300, 400], [40, 90, 99, 150, 200], [101, 202, 404, 505]], 15);
test([[10, 20, 30, 40, 50, 60, 70, 80, 90], [55, 84]], 5);
test([[10, 20, 30], [40, 50]], 10);
test([[15, 30, 699], [16, 800], [10, 801], [11, 803]], 10);

// taken from the answer of http://stackoverflow.com/a/32868439/1447675 from DzinX
var LARGE_TEST_SIZE = 1000,
    largeTest = function () {
        var array = [];
        for (var i = 0; i < LARGE_TEST_SIZE; ++i) {
            var innerArray = [];
            for (var j = 0; j < LARGE_TEST_SIZE; ++j) {
                innerArray.push((i + j) * 10);
            }
            array.push(innerArray);
        }
        return array;
    }(),
    startTime;

startTime = Date.now();
document.write('<br>' + intersection(largeTest, 20).length + '<br>');
document.write('Duration [ms]: ' + (Date.now() - startTime) + '<br>');

Comparision with the solution from DzinX
I just changed the console.log to document.write('<br>' ....
Please watch Duration in the result windows.

function findRanges(arrays, range) {

    // Gather all items into one array:
    var items = [];
    arrays.forEach(function (array, arrayNumber) {
        array.forEach(function (item) {
            items.push({
                value: item,
                arrayNumber: arrayNumber
            });
        });
    });

    items.sort(function (left, right) {
        return left.value - right.value;
    });

    var countByArray = [];
    arrays.forEach(function () {
        countByArray.push(0);
    });

    var arraysIncluded = 0;

    var i = 0,
      j = 0, // inclusive
      spread = 0,
      arrayCount = arrays.length,
      itemCount = items.length,
      result = [];

    function includeItem(pos) {
        var arrayNumber = items[pos].arrayNumber;
        ++countByArray[arrayNumber];
        if (countByArray[arrayNumber] === 1) {
            ++arraysIncluded;
        }
    }

    function excludeItem(pos) {
        var arrayNumber = items[pos].arrayNumber;
        --countByArray[arrayNumber];
        if (countByArray[arrayNumber] === 0) {
            --arraysIncluded;
        }
    }

    function allArraysIncluded() {
        return arraysIncluded === arrayCount;
    }

    function extractValue(item) {
        return item.value;
    }

    function saveSpread(start, end) {
        result.push(items.slice(start, end).map(extractValue));
    }

    // First item is already included.
    includeItem(0);

    while (j < (itemCount - 1)) {

        // grow j while you can
        while ((spread <= range) && (j < (itemCount - 1))) {
            ++j;
            spread += items[j].value - items[j - 1].value;
            includeItem(j);
        }
        if (spread <= range) {
            // We ran out of items and the range is still OK, break out early:
            break;
        }
        // Don't include the last item for checking:
        excludeItem(j);
        if (allArraysIncluded()) {
            saveSpread(i, j);
        }

        // Include the violating item back and try to reduce the spread:
        includeItem(j);
        while ((spread > range) && (i < j)) {
            spread -= items[i + 1].value - items[i].value;
            excludeItem(i);
            ++i;
        }
    }

    // last check after exiting the loop (j === (itemCount - 1))
    if (allArraysIncluded()) {
        saveSpread(i, j + 1);
    }

    return result;
}


function test(arrays, range) {
    var result = findRanges(arrays, range);
    document.write("<br>arrays:", JSON.stringify(arrays));
    document.write("<br>range:", range);
    document.write("<br>result:", JSON.stringify(result));
    document.write("<br>---");
}


test([[100, 110, 200, 300, 400], [40, 90, 99, 150, 200], [101, 202, 404, 505]], 15);
test([[10, 20, 30, 40, 50, 60, 70, 80, 90], [55, 84]], 5);
test([[10, 20, 30], [40, 50]], 10);
test([[15, 30, 699], [16, 800], [10, 801], [11, 803]], 10);

// A large test (1 million items):
var LARGE_TEST_SIZE = 1000;

var largeTest = (function () {
    var array = [];
    for (var i = 0; i < LARGE_TEST_SIZE; ++i) {
        var innerArray = [];
        for (var j = 0; j < LARGE_TEST_SIZE; ++j) {
            innerArray.push((i + j) * 10);
        }
        array.push(innerArray);
    }
    return array;
})();
var startTime
startTime = Date.now();
document.write('<br>' + findRanges(largeTest, 20).length); // 3        
document.write('<br>Duration [ms]: ' + (Date.now() - startTime));

Speed comparison, with different browsers
Machine: Win 7/64, Core i7-2600 3.40 GHz
Version      IE 11       Chrome 45.0  Firefox 40.0.3
------- -------------- -------------- --------------
DzinX        375 ms         688 ms        1323 ms
Nina         335 ms         122 ms         393 ms

