Finding all pairs of non-consecutive number in unsorted array

Asked By: Anonymous

Given an array of unsorted numbers, need to get all pairs of non-consecutive elements.

Input [2,3,4,5,9,8,10,13]
Desired output (2,5)(8,10)(13,13)

Explanation:

Input = [2,3,4,5,9,8,10,13]

if we create sequence in increasing order of given array then it will be:

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

now, if break down into groups wheres the sequence get breaks:

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

then, output would be first & last number of the groups, if there is only number in group then it’ll be treated as fast & last.

Output:

[2,5][8,10][13,13]

My workaround :

var array = [2,3,4,5,9,8,10,13]
var input = array.sort((a,b)=>{return a-b});
var group = [];
var start = input[0];
for(let i = 0; i<input.length; i++){
    if(input[i+1] - input[i] > 1){
        group.push([start,input[i]])
        start = input[i+1];
    }
}
console.log(group);

Output:

[ [ 2, 5 ], [ 8, 10 ] ]

Solution

Answered By: Anonymous

My approach

Here’s an implementation that does exactly the steps you suggest above. First we sort numerically. Then we use reduce to break this down into groups of consecutive numbers. Then we map the arrays in that result to take the first and last values.

Because we will need it several times, we write a simple helper function, last to get the final element in an array.

const last = (xs) => 
  xs [xs .length - 1]

const nonConsecutives = (ns) =>
  [...ns] 
    .sort ((a, b) => a - b) 
    .reduce (
      (r, n, i) => (i == 0 || n > last (last (r)) + 1)
        ? r .concat ([[n]])
        : r .slice (0, -1) .concat ([last (r) .concat (n)]),
      []
    ) 
    .map (ns => [ns [0], last (ns)])


console .log (
  nonConsecutives ([2, 3, 4, 5, 9, 8, 10, 13])
)

x000D

Fixing your approach

If you’re more wondering where your approach went wrong, the problem is at the boundaries (as is so often true in much programming!) The line if (input [i + 1] - input [i] > 1) will have an issue at the last i, since there will be no input [i + 1]. Similarly, you don’t want to perform this update start = input [i + 1] on the first iteration.

This similar version seems to work. We test between the current index and the previous one. (We also add a pre-check that the current index is 0, which is not technically necessary, since the input [i] - input [i - 1] would yield input [i] - undefined, which is NaN, and NaN > 1 is false, so we couldn’t enter the body of the if statement. But, while not technically necessary, it’s much cleaner.) We don’t push a new group on the first index, but after the loop is completed we push a final group.

Here’s an implementation:

const array = [2, 3, 4, 5, 9, 8, 10, 13]
const input = array .sort ((a, b) => a - b)
const group = []
let start = input [0]
for (let i = 0; i < input .length; i++){
    if (i == 0 || input [i] - input [i - 1] > 1) {
        if  (i > 0) {
          group .push ([start, input [i - 1]])
        }
        start = input [i]
    }
}
group .push ([start, input [input .length - 1]])

console.log(group);

x000D

Differences

The differences in approaches here is substantial. Of course one is that I wrap my manipulation in a function. Those who prefer functional programming will almost always do this. Another is that I build mine as a series of distinct transformations. I would usually do this more explicitly (more on that below) but it’s still pretty clear here: first we sort, then we group, then we capture the endpoints. This is often not the most efficient method, but it’s often the clearest.

The biggest difference is that in my version, we don’t mutate any variables along the way, only creating new ones. (That’s even true inside the reduce callback, although sometimes performance concerns will make me choose otherwise here.) This is a central tenet of functional programming: never mutate input data.

Using Ramda

I’m one of the founders of the Ramda functional programming library. It has a number of useful helper functions; and it’s designed around the notion of pipelines of simple transformation, none of which mutate their data. In Ramda, we might write this more simply:

const {pipe, sortBy, identity, groupWith, map, juxt, head, last} = R

const nonConsecutives = pipe (
  sortBy (identity),
  groupWith ((a, b) => b - a <= 1),
  map (juxt ([head, last]))
)

console .log (
  nonConsecutives ([2, 3, 4, 5, 9, 8, 10, 13])
)

<a href="//cdnjs.cloudflare.com/ajax/libs/ramda/0.27.1/ramda.min.js">//cdnjs.cloudflare.com/ajax/libs/ramda/0.27.1/ramda.min.js</a>

x000D

I won’t get into the details of how this works. And I’m not trying to sell Ramda. But the idea is that breaking problems down into smaller problems can make for very clean code. If you can capture those smaller parts in pure functions, you are well on your way to doing functional programming.