How can I detect breaks in intervals?

Question

How can I detect breaks in intervals?

Consider the following ranges as examples:

const ranges = [
  [
    0,
    10,
  ],
  [
    20,
    30,
  ],
  [
    40,
    50,
  ],
];

In this scenario, I am looking to identify the missing ranges between two given values. For instance, if the input range was [-10, 60], the expected output should be as follows:

const islands = [
  [
    -10,
    -1,
  ],
  [
    11,
    19,
  ],
  [
    31,
    39,
  ],
  [
    51,
    60,
  ],
];

I attempted to search for terms like "disjoint ranges" and "non-intersecting ranges" but did not come across a solution. It seems like a common problem that may have been addressed numerous times in the past. Perhaps I am using incorrect search terms.

javascript arrays algorithm range

Answer 1

Answer №1

When it comes to searching for intersections within intervals, one of the primary data structures you can rely on is the Interval Tree. By creating an interval tree based on ranges, you can easily identify intersections between the input range and the tree through queries. Then, a sweep from left to right of the input range can help pinpoint any gaps.

For those looking to implement an interval tree in JavaScript, there are a variety of options available, such as the one provided in this repository.

Answer 2

When it comes to searching for intersections within intervals, one of the primary data structures you can rely on is the Interval Tree. By creating an interval tree based on ranges, you can easily identify intersections between the input range and the tree through queries. Then, a sweep from left to right of the input range can help pinpoint any gaps.

For those looking to implement an interval tree in JavaScript, there are a variety of options available, such as the one provided in this repository.

Answer 3

Answer №2

function findMissingNumbers(arr, ranges) {
  let [min, max] = arr;
  return ranges.reduce((acc, range, index) => {
    if (range[0] < min) return acc;
    if (min < range[0]) acc.push([min, range[0] - 1]);
    if (index === ranges.length - 1 && max > range[1]) acc.push([range[1] + 1, max]);
    min = range[1] + 1;
    return acc;
  }, []);
}

let ranges = [ [2, 10], [5, 7], [40, 50] ];
console.log(findMissingNumbers([-10, 60], ranges));

ranges = [ [0, 10],[20, 30],[40, 50]];
console.log(findMissingNumbers([-10, 60], ranges));

Answer 4

function findMissingNumbers(arr, ranges) {
  let [min, max] = arr;
  return ranges.reduce((acc, range, index) => {
    if (range[0] < min) return acc;
    if (min < range[0]) acc.push([min, range[0] - 1]);
    if (index === ranges.length - 1 && max > range[1]) acc.push([range[1] + 1, max]);
    min = range[1] + 1;
    return acc;
  }, []);
}

let ranges = [ [2, 10], [5, 7], [40, 50] ];
console.log(findMissingNumbers([-10, 60], ranges));

ranges = [ [0, 10],[20, 30],[40, 50]];
console.log(findMissingNumbers([-10, 60], ranges));

Answer 5

Answer №3

I successfully implemented a solution that accounts for all possible edge cases that crossed my mind.

I wanted to share this code in case nobody else comes up with a more efficient solution:

function identifyGaps(rangesList) {
  const gapsList = [];

  for (let i = 0; i < rangesList.length - 1; i++) {
    const startRange = rangesList[i][1];
    const endRange = rangesList[i + 1] ? rangesList[i + 1][0] : null;

    if (startRange < endRange) {
      gapsList.push([startRange + 1, endRange - 1]);
    }
  }

  return gapsList;
}

function findMissingRanges(rangesList, fromNum, toNum) {
  if (rangesList.length === 0) {
    return [[fromNum, toNum]];
  }

  const gapsList = [
    [Number.NEGATIVE_INFINITY, rangesList[0][0] - 1],
    ...identifyGaps(rangesList),
    [rangesList[rangesList.length - 1][1] + 1, Number.POSITIVE_INFINITY],
  ];

  return gapsList
    .filter((gap) => {
      return isRangeOverlapping(gap, [fromNum, toNum]);
    })
    .map((gap) => {
      return [Math.max(gap[0], fromNum), Math.min(gap[1], toNum)];
    });
}

Answer 6

I successfully implemented a solution that accounts for all possible edge cases that crossed my mind.

I wanted to share this code in case nobody else comes up with a more efficient solution:

function identifyGaps(rangesList) {
  const gapsList = [];

  for (let i = 0; i < rangesList.length - 1; i++) {
    const startRange = rangesList[i][1];
    const endRange = rangesList[i + 1] ? rangesList[i + 1][0] : null;

    if (startRange < endRange) {
      gapsList.push([startRange + 1, endRange - 1]);
    }
  }

  return gapsList;
}

function findMissingRanges(rangesList, fromNum, toNum) {
  if (rangesList.length === 0) {
    return [[fromNum, toNum]];
  }

  const gapsList = [
    [Number.NEGATIVE_INFINITY, rangesList[0][0] - 1],
    ...identifyGaps(rangesList),
    [rangesList[rangesList.length - 1][1] + 1, Number.POSITIVE_INFINITY],
  ];

  return gapsList
    .filter((gap) => {
      return isRangeOverlapping(gap, [fromNum, toNum]);
    })
    .map((gap) => {
      return [Math.max(gap[0], fromNum), Math.min(gap[1], toNum)];
    });
}

How can I detect breaks in intervals?

Answer №1

Answer №2

Answer №3

Similar questions

Having trouble with publishing to npm as public with the --access flag not functioning properly?

Leverage the power of AJAX for fetching data from a database in Node.js

"Exploring the differences between request.body, request.params, and request.query

What could be causing the "Error - Only secure origins are permitted" message to appear for my service worker?

transforming JSON into CSV structure

How can we track and record NaN values in JavaScript/TypeScript as they occur in real-time?

The execution of JQuery/Javascript is restricted to only the initial condition within a Visualforce page utilizing the apex:outputpanel tag

The error message "TypeError: Cannot set property 'href' of undefined" occurred at angular.js line 12520 when trying to set $window.location.href

Introducing the new default in Google Chrome: Now accessing window.opener for target="_blank" links after rel="noopener" is the standard feature

Navigate back to the previous route within the Vue router hierarchy

Double execution of code in Swift to validate and store data

Error in Javascript programming | tracking progress bar

What is the best way to initialize firebase with context in a React application?

Looking for the optimal method to display numerous lines of text in HTML, one by one, at intervals of 60 seconds?

Convert former function to use async and await system

Transfer data from a child component to a parent component in a React application

Creating duplicates of an array by dereferencing pointers

Mongoose sparks a confrontation following the preservation of a single document in the database

Personalized FullCalendar header title

Tips for enabling item draggability following AJAX filtering operations