2

Let's imagine the following:

You have a line that starts at 1 and ends at 10000.

You're given an array of ranges like [{ start: 5, end: 10 }, { start: 15, end: 25 }]

Given an array of ranges, find the inverse.

For the above example, the inverse would be [{ start: 1, end: 4 }, { start: 11, end: 14 }, { start: 26, end: 10000 }]

Notice how the inverse is basically every other range on our line.

Below is my current solution... Is there a more elegant solution that doesn't have to explicitly deal with the edge cases?

Note, in my code ranges are named regions.

const inverseRegions = (regions) => {

  // If no regions, the inverse is the entire line.
  if (regions.length === 0) { 
    return [{ start: 1, end: 10000 }] 
  }

  let result = []

  // If the first region doesn't start at the beginning of the line
  // we need to account for the region from the 1 to the start of
  // first region
  if (regions[0].start !== 1) {
    result.push({
      start: 1,
      end: regions[0].start - 1
    })
  }

  for (let i = 1; i < regions.length; i++) {
    const previousRegion = regions[i-1]
    const region = regions[i]

    result.push({
      start: previousRegion.end + 1,
      end: region.start - 1
    })
  }

  // If the last region doesn't end at the end of the line
  // we need to account for the region from the end of the last
  // region to 10000
  if (regions[regions.length - 1].end !== 10000) {
    result.push({
      start: regions[regions.length - 1].end + 1,
      end: 10000
    })
  }

  return result
}

Expected results:

inverseRegions([]) 
  => [ { start: 1, end: 10000 } ]

inverseRegions([{ start: 1, end: 10 }, { start: 15, end: 20 }]) 
  => [ { start: 11, end: 14 }, 
       { start: 21, end: 10000 } ]

inverseRegions([{ start: 5, end: 10 }, { start: 12, end: 60 }, { start: 66, end: 10000 }]) 
  => [ { start: 1, end: 4 },
       { start: 11, end: 11 },
       { start: 61, end: 65 } ]

inverseRegions([{ start: 8, end: 12 }, { start: 16, end: 20 }, { start: 29, end: 51 }]) 
  => [ { start: 1, end: 7 },
       { start: 13, end: 15 },
       { start: 21, end: 28 },
       { start: 52, end: 10000 } ]
David
  • 7,028
  • 10
  • 48
  • 95
  • Why not `[1,5]` and why `[1,4]` ? because then the range `[4,5]` is skipped. Or have I missed something? – nice_dev Nov 07 '18 at 06:24
  • @vivek_23 The way the regions get generated is that if `[4,5]` existed, it would be part of `[5, 10]` and `[5, 10]` would have been `[4, 10]` when passed into the function. This is why it would be `[1, 4]`. The other edge case is if you have `[10, 13]` and `[15, 17]`, then it is possible to have a single point range like `[14, 14]` – David Nov 07 '18 at 06:29
  • But, then there would always exist a gap on the line which we didn't cover. – nice_dev Nov 07 '18 at 06:33
  • 1
    I get what you're saying. In my problem, what is being generated right now works, in a general case, you're right. We're leaving a gap. – David Nov 07 '18 at 06:42

1 Answers1

2

You can use reduce initialized with an accumulator that contains the entire region and then split that last region as you encounter new ranges:

function inverseRegions(ranges) {
  return ranges.reduce((acc, curr) => {
    let prev = acc.pop();
    if (curr.start > prev.start) 
      acc.push({start: prev.start, end: curr.start - 1})
    if (prev.end > curr.end)
      acc.push({start: curr.end + 1, end: prev.end});
    return acc;
  }, [{start: 1, end: 10000}])
}


console.log(inverseRegions([{ start: 5, end: 10 }, { start: 15, end: 25 }]));
console.log(inverseRegions([]));
console.log(inverseRegions([{ start: 1, end: 10 }, { start: 15, end: 20 }]));
console.log(inverseRegions([{ start: 5, end: 10 }, { start: 12, end: 60 }, { start: 66, end: 10000 }])); 
console.log(inverseRegions([{ start: 8, end: 12 }, { start: 16, end: 20 }, { start: 29, end: 51 }]));

This of course assumes that your intervals are sorted.

slider
  • 12,810
  • 1
  • 26
  • 42
  • 1
    I had a really good feeling I could use reduce to accomplish it and I think this is the way! Will give some more time for different answers, but this looks great. – David Nov 07 '18 at 06:05
  • 1
    You could refactor it even further: Where you do `curr.start - prev.start > 0`, you could just do `curr.start > prev.start` – David Nov 07 '18 at 06:12
  • Your solution definitely reads more elegantly than mine and I like that a lot. It's definitely a micro-optimization, but I wonder how many pushes/pops your solution does relative to mine. If my function gets `n`, then you'll have at most `n+1` pushes. In your solution, I think you'll have `n` pops + `2n` pushes which is `3n` total operations. I guess you can't avoid that with a reducer solution. It looks really nice though :) – David Nov 07 '18 at 06:21
  • @David Also note that you're using `unshift` for an edge case, which I think in most JavaScript implementations is an *O(n)* operation (unlike `push` which is *O(1)* - see https://stackoverflow.com/questions/12250697/time-complexity-of-unshift-vs-push-in-javascript). This takes your array operations to around `2n`. – slider Nov 07 '18 at 06:36
  • Yeah, you're right. I thought about that. I could move it in front of the for-loop with a `push` operation. I'll edit mine. End of the day, I'll prob go with yours. Realistically, the difference between `n` operations and `3n` won't be noticeable at all. – David Nov 07 '18 at 06:41