2
\$\begingroup\$

Pick peaks

Wrote my "hello world" on Thursday, so definitely a beginner. I know some Python, so not a novice to programming in general.

Question

For example, the array arr = [0, 1, 2, 5, 1, 0] has a peak at position 3 with a value of 5 (since arr[3] equals 5).

The output will be returned as an object with two properties: pos and peaks. Both of these properties should be arrays. If there is no peak in the given array, then the output should be {pos: [], peaks: []}.

Example: pickPeaks([3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3]) should return {pos: [3, 7], peaks: [6, 3]} (or equivalent in other languages)

All input arrays will be valid integer arrays (although it could still be empty), so you won't need to validate the input.

The first and last elements of the array will not be considered as peaks (in the context of a mathematical function, we don't know what is after and before and therefore, we don't know if it is a peak or not).

Also, beware of plateaus !!! [1, 2, 2, 2, 1] has a peak while [1, 2, 2, 2, 3] does not. In case of a plateau-peak, please only return the position and value of the beginning of the plateau. For example: pickPeaks([1, 2, 2, 2, 1]) returns {pos: [1], peaks: [2]} (or equivalent in other languages)

Have fun!


Solution

function pickPeaks(arr)
{
   const obj = {
      pos: [],
      peaks: []
   };
   let i = 1;
   while(i < arr.length-1)
   {
      let run = false;
      let peak = false
      if(new Set(arr.slice(i, i+2)).size === 1)  // There is a run of numbers.
      {
         previous = arr[i-1] < arr[i];
         var j = i;
         while(arr[j] === arr[i]) j++;  // Consume the run.
         next = arr[j] < arr[i]
         if(previous && next) peak = true;  // Was the run a plateau?
      }
      else if(arr[i] > arr[i-1] && arr[i] > arr[i+1]) peak = true;
      if(peak)
      {
         obj.pos.push(i);
         obj.peaks.push(arr[i]);
      }
      i = run ? j : i+1;
   }
   return obj
}
\$\endgroup\$
2
\$\begingroup\$

Unfinished ?

You have the variable run set to false and then use it in a ternary to set i. run is never set to true. I assume you intended to set it true after scanning a plateau.

JavaScript Style

  • In JavaScript we put the opening { on the same line and else on the same line as the closing }

  • Spaces between operators. eg arr[i+1]; becomes arr[i + 1];

  • Always declare variables. The variables next and previous are undeclared and are thus automatically declared in global scope. Global scoped variables are significantly slower, and highly likely to conflict with other globals if you are unaware. Use the directive "use strict" (strict mode) which will throw an error when you use undeclared variables.

  • Use ; consistently. JavaScript requires them and will insert them automatically if you do not add them where required. The insertion rules are complex and unless you are familiar with them it is best to always use them.

  • Use meaningful names. obj could be result. Better yet you can declare the arrays pos and peaks as variables and build the object on the return. eg return {pos, peaks} this saves you having to indirectly reference the arrays when you use them. (see rewrite)

  • Learn the difference between function scope var and block scope let, const and use appropriately.

  • Always declare vars at the top of the function. You declared j as a var in the middle of the function.

  • Always delimit code blocks with {} eg while (foo) j++; should be while (foo) { j++; } with the exception of empty blocks. eg while (arr[i++] !== 0); I know that C like languages let you skip the {} but after years of coding I can tell you it is a very hard bug to spot when you change code and forget to delimit the block.

  • Avoid single use variables unless doing so will make a line too long. Eg next = arr[j] < arr[i]; if (previous && next) { becomes just if (previous && arr[j] < arr[i]) {

  • Use the simplest logic. the line if (new Set(arr.slice(i, i + 2)).size === 1) { creates a new Array, a new Set, populates the Set by generating a hash for each array item. That is a lot of overhead (you generate a Hash twice for each inner array item) that can replaces with if (arr[i] === arr[i+1]) { with only the i + 1 being overhead

  • Always try to reduce indexing into arrays by assigning array items into variables. Generally do this if you use the item 2 or more times. For engines like V8 (Chrome and Node) this can provide some worthwhile performance improvements. Firefox this makes no difference however it does make the code less noisy and thus easier to read..

Rewrite

I think your solution is a little over complicated, especially indexing into the array so many times. Nor is there a need to make a special case of plateaus.

The rewrite is a simpler solution that uses the variables climbing to track positions where the current item is greater than the previous. If the item is less than the previous then record the peak to be the climbing position. The plateau is thus automatically handled, and the number of lines and variables is greatly reduced.

The rewrite runs on average 15 times faster on the same data.

However to be fair the slow point is the use of the Set in the statement if(new Set(arr.slice(i, i+2)).size === 1) If you change that line to if (arr[i] === arr[i + 1]) { and add run = true in the plateau statement block, your function is then only about 30% slower than the rewrite (see second rewrite)

"use strict";   // not needed if this was a module
function pickPeaks(arr) {
    const pos = [], peaks = [];
    var i = 1, climbing, prevVal = arr[0];
    while (i < arr.length) {
        const val = arr[i++];
        if (val < prevVal && climbing) {
            pos.push(--climbing);
            peaks.push(arr[climbing]);
            climbing = 0;
        } else if (val > prevVal) { climbing = i }
        prevVal = val;
    }
    return {pos, peaks};
}

And rewriting you algorithm using the points in this answer we get...

function pickPeaks(arr){
    const pos = [], peaks = [];
    var j, i = 1;
    while (i < arr.length) {
        const val = arr[i], nextVal = arr[i + 1];
        let run = false, peak = false;
        if (val === nextVal) {
            j = i;
            while (arr[j] === val) { j++ }
            if (arr[i - 1] < val && arr[j] < val) { peak = true }
            run = true;
        } else if (val > arr[i - 1] && val > nextVal) { peak = true }
        if (peak) {
            pos.push(i);
            peaks.push(val);
        }
        i = run ? j : i + 1;
   }
   return {pos, peaks};
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.