Counting Valleys – HackerRank Challenge

Posted on

Problem

For this challenge on HackerRank:

A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.

Given Gary’s sequence of up and down steps during his last hike, find and print the number of valleys he walked through.

For example, if Gary’s path is s=[DDUUUUDD], he first enters a valley 2 units deep. Then he climbs out and up into a mountain 2 units high. Finally, he returns to sea level and ends the hike.

I reached a solution, but I’m sure it can be optimized:

function countingValleys(n, s) {
    let heightTracker = [];
    let height = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "D") {
            height--;
            heightTracker.push(height);
        }
        if (s[i] === "U") {
            height++;
            heightTracker.push(height);
        }
    }
    let planeTracker = [];
    for (let j = 0; j < heightTracker.length; j++) {
        if (heightTracker[j] < 0) {
            planeTracker.push("valley");
        }
        if (heightTracker[j] > 0) {
            planeTracker.push("mountain");
        }
        if (heightTracker[j] === 0) {
            planeTracker.push("flat");
        }
    }
    let newArray = [];
    for (let k = 0; k < planeTracker.length; k++) {
        if (planeTracker[k] === planeTracker[k - 1]) {
            continue;
        }
        if (planeTracker[k] !== planeTracker[k - 1]) {
            newArray.push(planeTracker[k]);
        }
    }
    let valleyCount = 0;
    for (let l = 0; l < newArray.length; l++) {
        if (newArray[l] === "valley") {
            valleyCount++;
        }
    }
    return valleyCount;
}

My logic was to keep track of all negative and positive values in s.

  • If heightTracker[j] is negative, push “valley” into planeTracker
  • If heightTracker[j] is positive, push “mountain” into planeTracker
  • Otherwise, push “flat” into planeTracker

So at that point, I’m left with:

[ 'valley', 'valley', 'valley', 'flat', 'valley', 'valley', 'valley', 'valley', 'valley', 'flat', 'mountain', 'flat' ]

And I’m wondering, is there a way to filter out any elements that are the same as the element before them? The goal was to generate the array:

[ 'valley', 'flat', 'valley', 'flat', 'mountain', 'flat'] and then count the number of times the word “valley” appears in that array. As you can see, I did this with a for-loop. But I’m wondering what other suggestions you’d have – maybe the .filter() method?

Solution

You’re vastly overcomplicating the solution by introducing three arrays heightTracker, planeTracker, and newArray. None of those is needed: just track the elevation (which is a better name than height), and go by the definition:

A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.

So, the number of valleys traversed is the number of times Gary’s elevation changes from -1 to 0.

function countingValleys(n, s) {
    let elevation = 0;
    let traversedValleys = 0;
    for (let i = 0; i < n; i++) {
        if (s[i] === "D") {
            --elevation;
        } else if (s[i] === "U") {
            if (++elevation === 0) traversedValleys++;
        }
    }
    return traversedValleys;
}

I found that instead of using the for-loop, I can use filter() like this:

planeTracker = planeTracker.filter((element, index, arr) => element !== arr[index + 1]);

To get rid of the elements that are the same as the previous element.

Leave a Reply

Your email address will not be published. Required fields are marked *