Multidimensional array replace with close range Javascript

40
October 18, 2021, at 04:30 AM

Let's say we have a List of ranges expressed in arrays with two elements [from, to].

When we add a new array range like [5,8], it should check in List if there is a closest range and then replace it with the new range value. An example is provided below:

Example 1

var List = [[1,2], [3,4], [6,7], [9,10]]
var newData = [5,8]

Expected Output:

[[1,2], [3,4], [5,8], [9,10]]

The [6,7] range is already included in [5,8]

Example 2

var List = [[1,3], [4,6], [8,10]]
var newData = [5,9]

Expected Output:

[[1,3], [4,10]]
Answer 1

Assuming the initial list is well-formed, with its pairs sorted and non-overlapping, you could use binary search to find the end points of a new pair in the array and so determine any overlap. If overlap, splice the array accordingly:

function addSegments(segments, ...pairs) {
    for (let pair of pairs) {
        let [start, end] = pair.map(function (x, i) { // Binary search
            let low = 0, 
                high = segments.length;
                side = 1 - i;
            while (low < high) {
                let mid = (low + high) >> 1;
                if (x < segments[mid][side]) high = mid;
                else low = mid + 1;
            }
            return low - (side && segments[low-1]?.[side] === x);
        });
        if (start < end) {
            pair = [
                Math.min(segments[start][0], pair[0]),
                Math.max(segments[end-1][1], pair[1])
            ];
        }
        segments.splice(start, end - start, pair);
    }
}
// Demo
let list = [[1, 2], [3, 4], [6, 7], [9, 10]];
addSegments(list, [5, 8]);
console.log(JSON.stringify(list));
list = [[1, 3], [4, 6], [8, 10]];
addSegments(list, [5, 9]);
console.log(JSON.stringify(list));

Answer 2

If we have two arrays containing all the integers included in the ranges, then we can intersect and see if they overlap. If they do, we create a new range from the union of the two ranges, and use that in the output instead.

So to that end, we define three helper functions, range(), intersect() and union(), and then we use those to generate the output array. If the intersection exists, we overwrite any overlapped range with the new union of the two. I assumed that if two ranges just touched they weren't meant to be combined, so the overwrite is only triggered if the intersection contains more than one element. Also, I added an initial sort.

function add(list, data) {
  
  let buffer = [], idx;
  const range=(a,b)=>Array.from({length:b-a+1}, (_, i)=>(a+i));
  const intersect=(a,b)=>a.filter(x=>b.includes(x));
  const union=(a,b)=>[...new Set([...a, ...b])].sort((a,b)=>a-b);
  list.sort((a,b)=>a[0]-b[0]);
  
  list.forEach(el=>{
    
    let x = range(el[0], el[1]);
    let y = range(data[0], data[1]);
    let i = intersect(x, y);
    
    if(i.length>1) {
      let d = union(x,y);
      data = [d[0], d[d.length-1]];
      if(idx) { buffer[idx] = data; }
      else { idx = buffer.push(data)-1; }
    } 
    else { buffer.push(el); };
    
  });
  
  return buffer;
  
}

// DEMO
let List = [[1,2], [3,4], [6,7], [9,10]];
let newData = [5,8];
console.log(JSON.stringify(List));
console.log(JSON.stringify(newData));
console.log(JSON.stringify(add(List, newData)));
console.log('');
List = [[1,3], [4,6], [8,10]];
newData = [5,9];
console.log(JSON.stringify(List));
console.log(JSON.stringify(newData));
console.log(JSON.stringify(add(List, newData)));
console.log('');
// DEMO WITH UNORDERED ELEMENTS
List = [[3,4], [9,10], [6,7], [1,2]];
newData = [5,8];
console.log(JSON.stringify(List));
console.log(JSON.stringify(newData));
console.log(JSON.stringify(add(List, newData)));
console.log('');

READ ALSO
bootstrap 5 bs-gutter-x throws off div&#39;s

bootstrap 5 bs-gutter-x throws off div's

My div alignment is being thrown off by the defaultrow class

35
Tkinter image not adding to text widget

Tkinter image not adding to text widget

I am trying to make text widget that get images from reddit then displaying it on a text widget, but for some reason, with no error, the image is not displaying on the widget

60
I&#39;m having a little trouble implementing the Strategy pattern

I'm having a little trouble implementing the Strategy pattern

I confess that I'm having a bit of difficulty implementing the strategy pattern in a program that aims to display a different message daily (ExMessage of the day

48
is there a way to recover some android data after factory reset and Dr Fone eraser?

is there a way to recover some android data after factory reset and Dr Fone eraser?

my android device was voluntary damaged by someone to delete the data on it

65