Codewars - Pick peaks

Salutations.

GIF

I'm posting Codewars challenges and my thought process in this series. I'm using JS and Node 18 whenever possible. Just for the sake of clarity, I'm making fair use of them.

I took a break, and now I'm back. Did some challenges without posting the solution here though. Let's approach an easy challenge.

Pick peaks is a fun one. You need to find local maxima according to its mathematical definition. From GFG:

Mathematically, f (a) ≥ f (a -h) and f (a) ≥ f (a + h) where h > 0, then a is called the Local maximum point.

In essence, we need to see which values are bigger than its closest neighbors. If a neighbor is missing we can't verify if it's a local maximum or not. So we won't check the borders of the array.

The following solution is not optimized. It should be one pass. Besides, I was taught to avoid using break and continue. But it does the job.

First we set the rules:

• If the array is empty, return empty arrays. [] => {pos:[], peaks:[]}
• If a value is less than or equal to the previous one, it's automatically discarded (plateaux will be treated in another rule). (array[i] <= array[i-1]) ? discard
• If a value is NOT discarded by the previous rule, AND it's bigger than the next value, it's a maximum. (array[i] > array[i+1]) ? maximum
• If a value is NOT discarded by the aforementioned rule, AND it's EQUAL TO the next value, it requires special treatment. We'll solve this later.

Second, it needs an specific return value: {pos:[], peaks:[]}
This challenge asks for position and value of the maxima.

Third, we need to set a loop for the array:
for (let i = 1 ; i < arr.length -1 ; i++)
We skip the first and last value because they'll never be maxima according to the definition.

Fourth, we implement the rules:

  for (let i = 1 ; i < arr.length -1 ; i++){
    if (arr[i] <= arr[i-1]){
      continue;
    }
    if (arr[i] > arr[i+1]){
      cache.pos.push(i);
      cache.peaks.push(arr[i]);
    }
    if (arr[i] == arr[i+1]){
      // TO DO
    }
  }

We'll need to refine that last part. That's the special treatment mentioned above while setting the rules. It is merely another loop that acts as a sub process:

    if (arr[i] == arr[i+1]){
      for (let j=i +1 ; j< arr.length - 1; j++){
        if (arr[j] == arr[j+1]){
          continue;
        }
        if (arr[j] < arr[j+1]){
          break;
        }
        if (arr[j] > arr[j+1]){
          cache.pos.push(i);
          cache.peaks.push(arr[i]);
        }
      }
    }

The sum of it all is this:

function pickPeaks(arr){
  let cache = {pos:[], peaks:[]};
  if (arr == false) {
    return cache;
  }

  for (let i = 1 ; i < arr.length -1 ; i++){
    if (arr[i] <= arr[i-1]){
      continue;
    }
    if (arr[i] > arr[i+1]){
      cache.pos.push(i);
      cache.peaks.push(arr[i]);
    }
    if (arr[i] == arr[i+1]){
      for (let j=i +1 ; j< arr.length - 1; j++){
        if (arr[j] == arr[j+1]){
          continue;
        }
        if (arr[j] < arr[j+1]){
          break;
        }
        if (arr[j] > arr[j+1]){
          cache.pos.push(i);
          cache.peaks.push(arr[i]);
        }
      }
    }
  }

  return cache;
}

And now let's test it... Yay! It passed! Let's submit and...

Oh no. What???

GIF

This particular test: pickPeaks([1,2,5,4,3,2,3,6,4,1,2,3,3,4,5,3,2,1,2,3,5,5,4,3])
This should return: {pos:[2,7,14,20], peaks:[5,6,5,5]}
It returns: {pos:[2,7,14,20,20], peaks:[5,6,5,5,5]}

But why? The logic is sound. And every loop is correctly... Uhmmm... Wait... It gets duplicated. Position 20, value 5. It's there twice. There's got be something wrong here:

    if (arr[i] == arr[i+1]){
      for (let j=i +1 ; j< arr.length - 1; j++){
        if (arr[j] == arr[j+1]){
          continue;
        }
        if (arr[j] < arr[j+1]){
          break;
        }
        if (arr[j] > arr[j+1]){
          cache.pos.push(i);
          cache.peaks.push(arr[i]);
        }
      }
    }

After some debugging with Dev Tools, I found it. Here's the problem:

        if (arr[j] > arr[j+1]){
          cache.pos.push(i);
          cache.peaks.push(arr[i]);
        }

It's missing a break statement. [...3,5,5,4,3] duplicates the second value because it only breaks out of the inner loop when it finds a sequence where this exit condition occurs:

        if (arr[j] < arr[j+1]){
          break;
        }

Otherwise it keeps going. Turns out it should exit when it finds a maximum too:

        if (arr[j] > arr[j+1]){
          cache.pos.push(i);
          cache.peaks.push(arr[i]);
          break; // <------------ EXTREMELY IMPORTANT
        }

FIXED:

function pickPeaks(arr){
  let cache = {pos:[], peaks:[]};
  if (arr == false) {
    return cache;
  }

  for (let i = 1 ; i < arr.length -1 ; i++){
    if (arr[i] <= arr[i-1]){
      continue;
    }
    if (arr[i] > arr[i+1]){
      cache.pos.push(i);
      cache.peaks.push(arr[i]);
    }
    if (arr[i] == arr[i+1]){
      for (let j=i +1 ; j< arr.length - 1; j++){
        if (arr[j] == arr[j+1]){
          continue;
        }
        if (arr[j] < arr[j+1]){
          break;
        }
        if (arr[j] > arr[j+1]){
          cache.pos.push(i);
          cache.peaks.push(arr[i]);
          break;  // if you don't break, situations like this: 3,5,5,4,3
                  // can duplicate a value..
        }
      }
    }
  }

  return cache;
}

Inefficient, but effective.

Take care. Drink water 💧💧💧.

Previous