Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find longest occurrence of same number in array

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?

like image 778
Damon Bauer Avatar asked May 16 '14 00:05

Damon Bauer


People also ask

How do you find the first and last occurrence of an array?

A simple solution for this problem is to, one by one, pick each element from the array and find its first and last occurrence in the array and take the difference between the first and last occurrence for maximum distance. The time complexity for this approach is O (n 2 ).

How to find the maximum distance between two occurrences of same element?

We will pick each element from the array starting from the left. Then we will find the last occurrence of that same number and store the difference between indexes. Now if this difference is maximum then return it. Output −Maximum distance between two occurrences of same element in array − 4

How to count number of occurrences (or frequency) in a sorted array?

Count number of occurrences (or frequency) in a sorted array 1 Use Binary search to get index of the first occurrence of x in arr []. Let the index of the first occurrence be i. 2 Use Binary search to get index of the last occurrence of x in arr []. Let the index of the last occurrence be j. 3 Return (j – i + 1); More ...

How do you find the most common number in an array?

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. 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 Finally, get from the first set of array the number using the index you got from step 4.


2 Answers

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

like image 197
scrowler Avatar answered Nov 14 '22 23:11

scrowler


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);
like image 43
sabof Avatar answered Nov 15 '22 00:11

sabof