Max consecutive items of numbers in array with +1 difference

user_10905832 0
Viewed 125

I am trying to return the max number of consecutive numbers or same numbers which difference is no more than + 1.

Example*

const array = [1,2,3,5,5,6,6,6,6,7,8]
solution= 556666

const array2 = [2,2,3,4,4,5,5]
solution= 4455

I am a new coder and seems like there should be a simpler way to solve this but I am stuck at this point.

function getMaximumNumberItems(arr) {
    let initial = {'0': 0, '1':0, '2':0, '3':0, '4':0, '5':0, '6':0, '7':0, '8':0, '9':0 }
    let counts = {}
    arr.forEach((element) => {
       counts[element] = (counts[element] || 0) + 1
    })
    const numbers = {...initial,...counts}
    const arrValues = Object.values(numbers)
    let sum = []
    for (let i = 0; i < arrValues.length; i++) {
      arrValues[i] === arrValues[arrValues.length - 1] ? null : sum.push(arrValues[i] + arrValues[i + 1])
    }
    console.log(sum)
    let maxIndex = sum.indexOf(Math.max(...sum))
  }

What I have done is set a count for each number which is numbers, then I add each element with next element to see the max number of elements that are consecutive and add them to an array which is sum. The index of this maximum number should also be the index of the first element that should be returned from counts.

Mi idea was to return key from object and access how many times this number has appeared and add it some way and then use next element of numbers the same way to get the solution.

Obviously I see that this is the worst way of doing it, so would appreciate any help.

Thanks!

arrays javascript
1 Answers

You can do it in O(n) time. Take number, match all numbers after that, which difference with it is 1 or smaller. If you find number, which difference is bigger, than 1, then you need to remember the current result and repeat the previous steps, fixing the number of the element from which the best sequence begins and its length.

function maxSubsequence(array) {
    let ind = 0;
    let bestInd = 0;
    let cnt = 1;
    let maxCnt = 0;

    for (let i = 1; i < array.length; i++) {
        if (Math.abs(array[ind] - array[i]) <= 1) {
            cnt++;
        } else {
            if(cnt > maxCnt) {
                bestInd = ind;
                maxCnt = cnt;
            }
            cnt = 1;
            ind = i;
        }
    }

    if (cnt > maxCnt) {
        bestInd = ind;
        maxCnt = cnt;
    }

    return array.slice(bestInd, bestInd + maxCnt);
}

Output:

maxSubsequence(array)
[5, 5, 6, 6, 6, 6]

maxSubsequence(array2)
[4, 4, 5, 5]
user_157773700
Related