Find longest occurrence of same number in array

Question

Using JavaScript, I'm trying to find a way to find the longest occurrence of the same number (in this case, 1) in an array.

For instance, here's a sample array: [2,5,3,1,1,1,3,7,9,6,4,1,1,1,1,1,4,7,2,3,1,1,4,3]

I'd like to write a function that would return "5", since the number 1 occurs 5 times in a row. (It also occurs 3 and 2 times in a row, but I'm after the longest occurrence).

So far, I have written:

function streak(arr) {
    var i,
        temp,
        streak,
        length = arr.length;

    for(i=0; i<length; i++) {
        if (arr[i] === 1) {
            streak += 1;
        } else {
            temp = streak;
            break;
        }
    }
}

I know I need some way of knowing where I left off if I find an occurrence, but I'm feeling kind of stuck.

Any pointers?

Answer 1

I've modified your function slightly. You need to store the highest streak as a separate variable from the current streak, and overwrite that where necessary in your loop - finally returning that variable at the end of your function.

function streak(arr) {
    var i,
        temp,
        streak,
        length = arr.length,
        highestStreak = 0;

    for(i = 0; i < length; i++) {
        // check the value of the current entry against the last
        if(temp != '' && temp == arr[i]) {
            // it's a match
            streak++;
        } else {
            // it's not a match, start streak from 1
            streak = 1;
        }

        // set current letter for next time
        temp = arr[i];

        // set the master streak var
        if(streak > highestStreak) {
            highestStreak = streak;
        }
    }

    return highestStreak;
}

var array = [2,5,3,1,1,1,3,7,9,6,4,1,1,1,1,1,4,7,2,3,1,1,4,3];

console.log(streak(array)); // 5

And if you want to also track what the value of the highest streak was, define another variable at the start of your function, save the value of it when you save the highest streak, and return it as an array:

    // set the master streak var
    if(streak > highestStreak) {
        highestStreakValue = temp;
        highestStreak = streak;
    }
}

return [highestStreak, highestStreakValue];


var array = [2,5,3,1,1,1,3,7,9,6,4,'a','a','a','a','a',4,7,2,3,1,1,4,3];
console.log(streak(array)); // [5, "a"]

Demo returning both

Answer 2

An alternative approach. I'm converting the array to a string. The regular expression has a backrefence, which ensures that only sequences of the same character are matched. Also when exec is used with the g flag, repeated executions will continue from the end of last match, and not from the beginning.

var arr = [2,5,3,1,1,1,3,7,9,6,4,1,1,1,1,1,4,7,2,3,1,1,4,3];
var str = arr.join('');
var regex = /(.)\1*/g;
var match;
var largest = '';

while (match = regex.exec(str)) {
  largest = match[0].length > largest.length ? match[0] : largest;
}

console.log(largest.length);

Answer 3

Your problems:

• You don't store current streak
• You don't specify when streak is more then older streak

Use this:

function streak(arr) {
    var i,
        temp,
        streak = 1,
        maxStreak = 0,
        prevNumber,
        length = arr.length;

    for(i=1; i<length; i++) {
        prevNumber = arr[i-1];
        if (arr[i] == prevNumber) {
            streak += 1;
        } else {
            if(streak > maxStreak) {
                maxStreak = streak;
                streak = 1;
            }
        }
    }
    return maxStreak;
}

Demo

Answer 4

You will need another two arrays here.

1. Store the distinct numbers from your source array using a loop
2. Make a second set of array which is equal to the length of the first set of array which has the distinct numbers.
3. Make a loop equal to the length of the first set of array and then push the values to the second set of array according to its index.
4. Make a loop again using the second set of array and there you will find the most occurence using the index of the second array
5. Finally, get from the first set of array the number using the index you got from step 4.

I did not make the code for you to try it yourself first since you are asking only for some pointers

Answer 5

Alternative: use regexp and converting the array to a string.

var arr = [2,5,3,1,1,1,3,7,9,6,4,1,1,1,1,1,4,7,2,3,1,1,4,3];
var str = arr.join('').match(/1+/g);
console.log(process ? process.sort().pop() : "No ocurrences");

Answer 6

You could take Array#reduce and return the start index of the actual same item sequence. Then check and update the counter if the item is not equal.

var array = [2, 5, 3, 1, 1, 1, 3, 7, 9, 6, 4, 1, 1, 1, 1, 1, 4, 7, 2, 3, 1, 1, 4, 3],
    maxCount = 0,
    maxValues;

array.reduce(function (j, a, i, aa) {
    if (aa[j] === a) {
        return j;
    }
    if (i - j === maxCount){
        maxValues.push(aa[j]);
    }            
    if (i - j > maxCount) {
        maxCount = i - j;
        maxValues = [aa[j]];
    }
    return i;
}, -1);

console.log(maxCount);
console.log(maxValues);

Answer 7

My proposal:

function getLongestRow(inputArray) {
    // Initialize dummy variables
    var start = inputArray[0], curRowLen = 0, maxRowLen = 0, maxRowEle = 0;

    // Run through the array
    for(var i = 0;i < inputArray.length;i++) {
        // If current Element does not belong to current row
        if(inputArray[i] != start) {
            // If current row is longer than previous rows, save as new longest row
            if(curRowLen > maxRowLen) {
                maxRowLen = curRowLen;
                maxRowEle = start;
                curRowLen = 1;
            }
            // Start new row
            start = inputArray[i];
        } else {
            // Current element does belongt to current row, increase length
            curRowLen++;
        }
    }

    // Check whether last row was longer than previous rows
    if(curRowLen > maxRowLen) {
        maxRowLen = curRowLen;
        maxRowEle = start;
    }

    // Return longest row & element longest row consits of
    console.log('The longest row in your array consists of '+maxRowLen+' elements of '+maxRowEle+'.');
}

JsFiddle: http://jsfiddle.net/hdwp5/

Answer 8

Here's a way to do it:

var values = function(obj) {
  var res = [];
  for (var i in obj) {
    if (obj.hasOwnProperty(i)) {
      res.push(obj[i]);
    }
  }
  return res;
};

var countStreak = function(xs) {
  var res = xs.reduce(function(acc, x, i) {
    if (x === xs[i+1]) {
      acc[x] = acc[x]+1 || 2;
    } else {
      acc[x] = acc[x]-1 || 0;
    }
    return acc;
  },{})
  return Math.max.apply(0, values(res));
};

var ns = [2,5,3,1,1,1,3,7,9,6,4,1,1,1,1,1,4,7,2,3,1,1,4,3]
countStreak(ns) //=> 5

Answer 9

You can use fewer iterations by looking ahead at all matches from a given index, and jumping ahead to the next non-matching item's index.

You can also quit when there are less items left than the maximum you have found.

function maxRepeats(arr){
    var L= arr.length, i= 0, 
    max= 1, count= 0;
    while(L-i > max){
        while(arr[i+count]=== arr[i])++count;
        if(count > max) max= count;
        i+= count;
        count= 0;
    }
    return max;
}
var A= [2, 5, 3, 1, 1, 1, 3, 7, 9, 6, 4, 1, 
1, 1, 1, 1, 4, 7, 2, 3, 1, 1, 4, 3];

maxRepeats(A); returns 5

Finding multiple items that repeat the max number of times is not so easy, since you have to find the max number before you can list them. If you really only need the max number, ignore this:

function mostRepeats(arr, maximum){
    var i= 0, max= maximum || 1, 
    L= arr.length-max, 
    count= 0, index= [];
    while(i<L){
        while(arr[i+count]=== arr[i])++count;
        if(count=== maximum) index.push(arr[i]+' starting at #'+i);
        else if(count > max) max= count;
        i+= count;
        count= 0;
    }
    if(max===1) return 'No repeats';
    return maximum? max+' repeats of: '+index.join(', '): mostRepeats(arr, max);
}

var A= [2, 5, 3, 1, 1, 1, 3, 7, 9, 6, 4, 1, 1, 1, 
1, 1, 4, 7, 2, 3, 3, 3, 3, 3, 1, 1, 4, 3];

mostRepeats(A);returns:

5 repeats of: 1 starting at #11, 3 starting at #19

Answer 10

Unfortunately I can't comment yet due to lack of reputation so I will post this as an answer. For my task Robbie Averill's solution was perfect, but it contains a little bug. I had array that consisted of 2 values - 0 & 1.5, but above-mentioned code was counting only "1.5" values although I had "0" repeating in a higher streak. Problem was that value wasn't doing strict comparison here:

if(temp != '' && temp == arr[i]) {

and the fix was simple: if(temp !== '' && temp == arr[i]) {

I've updated Robbie's jsfiddler with this fix: http://jsfiddle.net/d5X2k/5/

Answer 11

Unfortunatly, a question has been marked as duplicate, but it was not the same as this one. So I must put my answer here, sorry…

let tab = [0,0,0,1,1,1,0,0,0,0,1,0,1,1,1,1,1]
  , arr = []
  , n = 0
  , res = null ;

for(let i of tab)
{
    if ( i ) { ++ n }
    else if ( n ) { arr.push(n) ; n = 0 }
}
arr.push(n) ;

res = Math.max(...arr);

console.log("Streak with 1 is ", Math.max(...arr));

It's a better solution than with reduce, slower, as you can see:

let tab = [0,0,0,1,1,1,0,0,0,0,1,0,1,1,1,1,1];
let arr = [];
let n = 0;
let res = null;

let loop = 0;
let start = new Date().getTime();

while (loop < 1000000){
  ++ loop;
  
  arr = [];
  for(let i of tab)
  {
      if ( i ) { ++ n }
      else if ( n ) { arr.push(n) ; n = 0 }
  }
  arr.push(n);
  res = Math.max(...arr);
}
let end = new Date().getTime();
console.log("laps old fashion = ", end - start);

loop = 0;
let streaks = null;
start = new Date().getTime();
while (loop < 1000000){
  ++ loop;
  streaks = tab.reduce((res, n) => 
    (n ? res[res.length-1]++ : res.push(0), res)
  , [0]);
  res = Math.max(...streaks);
}
end = new Date().getTime();
console.log("laps reduce = ", end - start);

console.log("Streak with 1 is ", Math.max(...arr));

Answer 12

Input array:

const seq = [
0, 0, 0,
1, 1, 1,
1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1,
];

Shortest solutions:

console.log(Math.max(...Array.from(seq.join("").matchAll(/(.)\1+/g), m=>m[0].length)))

Alternative with regexp (spoiler: it's ~25%, slower than solution with reduce(). See "Modern approach with reduce()" below):

const longestSeq = (seq) => {
    let max = 0;
    seq.join("").replace(/(.)\1+/g, m=> max = Math.max(max, m.length));
    return max;
};

Straightforward, old-school style, human readable and fastest solution:

let longestSeq = () => {
    let maxCount = 0,
        curCount = 0,
        curItem, prevItem,
        l = seq.length+2, // +1+1 to finish last sequence and compare 'undefined' with previous
        i = 0;
    for (; i < l; ++i) {
      curItem = seq[i];
      if (curItem === prevItem) ++curCount;
      else {
        if (curCount > maxCount) maxCount = curCount;
        curCount = 1;
        prevItem = curItem;
      }
    }
    return maxCount;
}

Modern approach with reduce() (just very little slower than old-school code above):

const longestSeq = (seq) => seq
    .reduce(
        ({count, max}, item) => item === 0
        ? { count: ++count, max: Math.max(count, max) }
        : { count: 0, max: max },
      { count: 0, max: 0} )
    .max;

Performance test, Reduce() vs old-school for(): https://jsbench.me/ifkgsin56z/1