CODEWITHSUNDEEP
javascriptarraysalgorithm
EugenSunic
EugenSunic

Reputation: 13703

How to properly count occurrence in arrays?

I've got an in depth array (arrays of arrays). I'm trying to make a decent function without using any extra methods and JS designs (like closures).

This is a working solution (but a bad one because of the global variable)

  var counter = 0;

  function findArray(array, item) {
      for (var i = 0; i < array.length; i++) {
          if (array[i] == item) {
              counter++;
          } else if (array[i].constructor === Array) {
              findArray(array[i], item);
          }
      }
      return counter;
  }

This is a none working solution with trying to avoid the global counter variable.

  function findArray(array, item, counter) {
    for (var i = 0; i < array.length; i++) {
        if (array[i] == item) {
            ++counter;
        }
        if (array[i].constructor === Array) {
            findArray(array[i], item, counter);
        }
    }
    return counter;
}

I would also like to avoid the counter input parameter since parameters should only be inputs and output variables shouldn't be inside the function params. Also I would like to avoid built in methods for instance slice etc.

NOTE: The optimal performance of the algorithm should not be taken into consideration.

Is there a way to make this work with the counter being inside the function?

function call looks like this: 

findArray([1,[1,2,3],1,[5,9,1],6],  1,0);

The output should be number 4, in this example (integer 1 is the number to be searched in the array).

Upvotes: 4

Views: 423

Answers (5)

EugenSunic
EugenSunic

Reputation: 13703

Another, maybe more comprehensible solution:

function sumValues(array) {
    let counter = 0;
    for (let item of array) {
      if (Array.isArray(item)) {
        counter += sumValues(item);
      }
      else {
        counter += item;
      }
    }
    return counter;
  }

Upvotes: 0

BluePill
BluePill

Reputation: 515

Working JSBin: http://jsbin.com/sayimecezo/edit?html,js,console,output

You could simply flatten the nested arrays and just filter on it. (Overriding prototype here just for convenience). 

Array.prototype.countDeep = function (n) {
  return [].concat.apply([], this).filter(function (f) {
    return f === n;
  }).length;
}

console.log(([1,[1,2,3],1,[5,9,1],6]).countDeep(1));
//prints 4

Seeding to a memoised value is trivial (although unnecessary);

Array.prototype.countDeep = function (n, seed) {
  return (seed || 0) + [].concat.apply([], this).filter(function (f) {
    return f === n;
  }).length;
}

console.log(([1,[1,2,3],1,[5,9,1],6]).countDeep(1, 200));
//prints 204

Upvotes: 0

primq
primq

Reputation: 11

I believe this is the best solution yet:

const countOccurs = (arr, val) =>
  arr.reduce((prev, curr) => {
    if (Array.isArray(curr)) {
       return prev + countOccurs(curr, val);
    }

    if (curr !== val) {
      return prev;
    }

    return prev + curr;
  }, 0);

console.log(countOccurs([1,[1,2,3],1,[5,9,1],6], 1)); // 4

What we are doing here is, we are going throughout provided array with Array.prototype.reduce and checking for any occurances of the value. If the actual value of the array (curr) is an array, the function is calling itself in order to check it and add the result to the counter (prev).

Upvotes: 0

John Bupit
John Bupit

Reputation: 10618

You have the right idea. You can modify the first recursive function like this:

function findArray(array, item) {
  var occurrences = 0;

  for (var i = 0; i < array.length; i++) {
    if (array[i] == item) {
      // Found an occurrence.
      occurrences++;
    } else if (array[i].constructor === Array) {
      // Add all occurrences in the sub-array i
      occurrences += findArray(array[i], item);
    }
  }

  return occurrences;
}


console.log(findArray([1, [1, 2, 3], 1, [5, 9, 1], 6], 1, 0));

Or shorten it using a reduce call, which has the same idea as above:

function findArray(array, item) {
  return array.reduce((occur, e) =>
    occur + ((Array.isArray(e)) ? findArray(e, item) : (e == item)), 0);
}

console.log(findArray([1, [1, 2, 3], 1, [5, 9, 1], 6], 1, 0));

Upvotes: 1

T.J. Crowder
T.J. Crowder

Reputation: 1074445

This is a use case for recursion. (And also for Array.isArray, which was added in ES5.) findArray can call itself to find occurrences within arrays within the array:

function findArray(array, item) {
    var counter = 0;
    for (var i = 0; i < array.length; i++) {
        var entry = array[i];
        if (entry == item){
            counter++;
        } else if (Array.isArray(entry)) {
            // Add in the count of occurrences in the array, and any arrays in it
            counter += findArray(entry, item);
        }
    }
    return counter;
}

It's also a use case for Array#reduce:

function findArray(array, item) {
    return array.reduce(function(counter, entry) {
        if (entry == item) {
            ++counter;
        }
        if (Array.isArray(entry)) {
            counter += findArray(entry, item);
        }
        return counter;
    }, 0);
}

Array#reduce calls the callback once per entry in the array, passing in the accumulator on each call. The initial value of the accumulator is provided as a second argument (optional in some cases, but not here); the callback returns an updated version of the accumulator, which is the ultimate return value of reduce.

Upvotes: 9

Related Questions