How to match two integer arrays, so the smallest one expands to closest neighbour from larger one

Question

Let's say I have two array pairs:

let a1 = [2000, 4000, 6000, 8000, 10000, 12000],
    b1 = [2000, 4000, 6000, 8000, 10000, 12000, 14000];

and

let a2 = [10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000, 50000, 55000],
    b2 = [10000, 20000, 30000, 40000, 50000, 60000];

or any arbitrary pair of integers.

The task is to expand the smallest array in the pair to largest size in this way, keeping smallest domain the same as well as values:

b1 =          [2000, 4000, 6000, 8000, 10000, 12000, 14000];
expanded_a1 = [2000, 4000, 6000, 8000, 10000, 12000, 12000];

a2 =          [10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000, 50000, 55000]
expanded_b2 = [10000, 20000, 20000, 30000, 30000, 40000, 40000, 50000, 50000, 60000];

invalid_expanded_b2 = [10000, 15000, 20000, 30000, 30000, 40000, 40000, 50000, 50000, 60000];

//second value is invalid

And once again, example with the third pair:

let a3 = [10, 15, 20, 25, 30, 35];
let b3 = [10, 20, 30];

So, expanded b3 should have only 10,20,30 values and its domain have to be [10,30]

              [10, 15, 20, 25, 30, 35]
                ↓   ↓   ↓   ↓   ↓   ↓
expanded_b3 = [10, 20, 20, 30, 30, 30]

Pretty sure, that, first of all, I need to clone the largest array and go through its every element and compare it with integers from the smallest array and if values don't match replace it with the closest left (or if there is no such, the right) integer from the smallest array.

Answer 1

This seems tricky to do at first but it's actually not that hard. You just have to go through both arrays together. Think of it as getting two pointers and then moving them along:

a2 =      [10000, 15000, 20000]
           ^^^^^
             |
pointer 1 ----

b2 =      [10000, 20000]
           ^^^^^
             |
pointer 2 ----       

• If the current value assigned to each pointer is equal, then you have a match - just return the value and move both pointers

a2 =      [10000, 15000, 20000]
                  ^^^^^
                    |
pointer 1 -----------

b2 =      [10000, 20000]
                  ^^^^^
                    |
pointer 2 -----------       

• If the current values don't match, then only advance the pointer belonging to the longer array but return the value from the shorter

a2 =      [10000, 15000, 20000]
                         ^^^^^
                           |
pointer 1 ------------------

b2 =      [10000, 20000]
                  ^^^^^
                    |
pointer 2 -----------       

Repeat until you finish the longer array.

You can do this in O(n) time.

Here is an implementation using a Generator and the ES6 array Iterators to walk both arrays. It is slightly more convenient than using pointers, since you can directly generate an array using Array.from

let a1 = [2000, 4000, 6000, 8000, 10000, 12000],
    b1 = [2000, 4000, 6000, 8000, 10000, 12000, 14000];
    
let a2 = [10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000, 50000, 55000],
    b2 = [10000, 20000, 30000, 40000, 50000, 60000];
    
function equaliseLength(arr1, arr2) {
  //equal length, nothing to do, just return
  if (arr1.length === arr2.length) return;
  
  //setup what to work with
  let longerArray;
  let arrayToExpand;
  
  if (arr1.length > arr2.length) {
    longerArray = arr1;
    arrayToExpand = arr2;
  } else {
    longerArray = arr2;
    arrayToExpand = arr1;
  }
  
  const generator = generateMissingSlots(arrayToExpand, longerArray);
  
  //convert to array
  const result = Array.from(generator);
  
  return result;
}

function* generateMissingSlots(shorter, longer) {
  //start two iterators for each array
  const shortIterator = shorter[Symbol.iterator]();
  const longIterator = longer[Symbol.iterator]();
  
  //get the initial values
  let shortCurrent = shortIterator.next();
  let longCurrent = longIterator.next();
  
  let lastShortValue = shortCurrent.value;
  
  //go through both until the longer is exhausted
  while(!longCurrent.done) {
    //produce the current value of the shorter array
    yield lastShortValue;
    
    //only advance the short iterator if the two have "caught up" 
    if (shortCurrent.value === longCurrent.value){
      shortCurrent = shortIterator.next();
      
      //update the value unless the iterator is exhausted
      //in case of `short = [a, b]` and `long = [a, b, c]` which will produce `undefined` for the last values
      if(!shortCurrent.done) {
        lastShortValue = shortCurrent.value
      }
    }
    
    //always advance the long iterator
    longCurrent = longIterator.next();
  }
}

expanded_a1 = equaliseLength(a1, b1);
console.log(expanded_a1);

expanded_b2 = equaliseLength(a2, b2);
console.log(expanded_b2);

Answer 2

Not sure, but something like this clumsy solution.

Number.prototype.between = function (domain_) {

     var min = Math.min.apply(Math, domain_);
     var max = Math.max.apply(Math, domain_);

     return this >= min && this <= max;

   };
      
  let a1 = [2000, 4000, 6000, 8000, 10000, 12000];
  let b1 = [2000, 4000, 6000, 8000, 10000, 12000, 14000];
      
  let result = matchArrays(a1, b1); 
  console.log(result);

  let a2 = [10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000, 50000, 55000];
  let b2 = [10000, 20000, 30000, 40000, 50000, 60000];

  result = matchArrays(a2, b2); 
  console.log(result)
  
 function matchArrays(a_, b_){
      
      if(a_.length == b_.length) { return [a_, b_]; }
      else if(a_.length > b_.length){
          
          if(a_.length - b_.length == 1) { b_.push(b_[b_.length - 1]); return [a_, b_]; }
 
          let b2 = a_.slice(0, a_.length);
          b2.forEach((d_, i_) => { 
          
              for(let i = 1; i < b_.length; i++){
                  
                  if(d_ != b_[i - 1] && d_ != b_[i] && d_.between([b_[i - 1], b_[i]])){
                    
                     b2[i_] = b_[i];
                      
                  }
                  
                  if(d_ > b_[b_.length - 1]) { b2[i_] = b_[b_.length - 1] }
                  
              }

          
          });
          
          return [a_, b2]
          
      }
      else{
          
          if(b_.length - a_.length == 1) { a_.push(a_[a_.length - 1]); return [a_, b_]; }
          let a2 = b_.slice(0, b_.length);
          
          a2.forEach((d_, i_) => { 
          
              for(let i = 1; i < a_.length; i++){
                  
                  if(d_ != a_[i - 1] && d_ != a_[i] && d_.between([a_[i - 1], a_[i]])){
                      
                     a2[i_] = a_[i];
                      
                  }
                  
              }
              
              if(d_ > a_[a_.length - 1]) { a2[i_] = a_[a_.length - 1] }
          
          });
          
          return [a2, b_]
          
      }
      
  }