How To Solve The Counting Valleys Challenge

How To Solve HackerRank’s Counting Valleys Code Challenge With JavaScript

Image for post
Image for post
How To Solve The Counting Valleys Code Challenge

Problem

The Counting Valleys challenge is counting the number of valleys Gary the hiker goes though:

  • Gary = Hiker
  • Sea level is 0 — Also the starting level
  • S = Descriptive string that is the path of steps Gary the hiker takes
  • U and D are “Up” and “Down” respectively and the direction of Gary’s step
  • N = number of steps between 2 and 10⁶ (1,000,000)
  • AR is a single string of spaced numbers with values ranging between 1 and 100 — ex 10 11 20 31
  • N is the number of values in steps in the path between 2 and 1,000,000 (which could be useless if we’re just calculating the array length)
  • A valley is defined as going lower than sea level and then back to sea level

Example 1:

N = 8
S = UDDDUDUU
_/\ _
\ /
\/\/
Result: 1 Valley

Example 2:

N = 10
S = UDDDUDUUDU
_/\ _ _
\ / \/
\/\/
Result: 2 Valleys

Goal

Write a function or functions that returns the total number of valleys found by traversing the string path (S) of steps

Covering Our Bases

Covering our bases, we need to make sure that:

  • Number of item (values) of S is in between 2 and 10⁶
  • N is an integer, between 2 and 10⁶
  • N = the total number of values of S

In order to get a better sense of how many values are in S we need to convert the string to an array and count it.

function countingValleys(n, s) {
// setting the constraints
const min = 2;
const max = 1000000;

// if it's a string convert it to an array
// ex "UDU" = ["U", "D", "U"]
s = (typeof ar === "string") ? s.split('') : s;
// check if s meets the requirements
if (s.length >= min && s.length <= max) {
// continue
}
}

Next we need to make sure that N is an integer and matches the same number of values of the path (S).

function countingValleys(n, s) {
// setting the constraints
const min = 2;
const max = 1000000;

// if it's a string convert it to an array
// ex "UDU" = ["U", "D", "U"]
s = (typeof s === "string") ? s.split('') : s;

// check if s meets the requirements
if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {
// continue
}
}

Understanding The Problem

In order to get a better idea of directions, another way we could look at things is going Up (U) would +1 and going Down (D) would be -1. If the definition of a valley is to go below sea level and then back to sea level, our goal is come up with a way to only start counting when we meet this condition.

Converting the array to integers is the first step to getting the directions.

// Example
// n = 8
// s = "
UDDDUDUU"
function countingValleys(n, s) {
// setting the constraints
const min = 2;
const max = 1000000;

// if it's a string convert it to an array
// ex "UDU" = ["U", "D", "U"]
s = (typeof s === "string") ? s.split('') : s;
// ["U", "D", "D", "D", "U", "D", "U", "U"]

// check if s meets the requirements
if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {

// converting the array steps to integers
s = s.map(steps => ((steps === "U") ? 1 : -1));
// [1, -1, -1, -1, 1, -1, 1, 1]

}
}

Next we’ll create a for loop and continuously sum the steps to traverse the full path.

// Example
// n = 8
// s = "UDDDUDUU"
function countingValleys(n, s) {
// setting the constraints
const min = 2;
const max = 1000000;

// if it's a string convert it to an array
// ex "UDU" = ["U", "D", "U"]
s = (typeof s === "string") ? s.split('') : s;
// ["U", "D", "D", "D", "U", "D", "U", "U"]

// check if s meets the requirements
if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {

// converting the array steps to integers
s = s.map(steps => ((steps === "U") ? 1 : -1));
// [1, -1, -1, -1, 1, -1, 1, 1]

let path = 0;
for(let i in s) {
path += s[i];
}
// 0 + 1 = 1
// 1 + -1 = 0
// 0 + -1 = -1
// -1 + -1 = -2
// -2 + 1 = -1
// -1 + -1 = -2
// -2 + 1 = -1
// -1 + 1 = 0
// initial = 0
// end = 0

}
}

Next we need to make handle the condition of meeting the valley requirements.

  • Below sea level (<0)
  • Back to sea level (=0)
// Example
// n = 8
// s = "UDDDUDUU"
function countingValleys(n, s) {
// setting the constraints
const min = 2;
const max = 1000000;
let valleys = 0;

// if it's a string convert it to an array
// ex "UDU" = ["U", "D", "U"]
s = (typeof s === "string") ? s.split('') : s;
// ["U", "D", "D", "D", "U", "D", "U", "U"]

// check if s meets the requirements
if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {

// converting the array steps to integers
s = s.map(steps => ((steps === "U") ? 1 : -1));
// [1, -1, -1, -1, 1, -1, 1, 1]

let path = 0;
for(let i in s) {
path += s[i];
if (path < 0) {
// start of a valley
}
if (path == 0) {
// end of valley, increase count
}

}
// 0 + 1 = 1 (Moved up = valley not started)
// 1 + -1 = 0 (Back to sea level = valley not started)
// 0 + -1 = -1 (Below sea level = valley started)
// -1 + -1 = -2 (Moved lower = still in valley
// -2 + 1 = -1 (Moved up = still in valley)
// -1 + -1 = -2 (Moved lower = still in valley)
// -2 + 1 = -1 (Moved up = still in valley)
// -1 + 1 = 0 (Back to sea level = 1 valley)
// initial = 0
// end = 0
}
}

Now that we defined the beginning and ending of a valley, we also need to factor for not counting valleys while we’re still in a valley.

// Example
// n = 8
// s = "UDDDUDUU"
function countingValleys(n, s) {
// setting the constraints
const min = 2;
const max = 1000000;
let valleys = 0;
let isInValley = false;


// if it's a string convert it to an array
// ex "UDU" = ["U", "D", "U"]
s = (typeof s === "string") ? s.split('') : s;
// ["U", "D", "D", "D", "U", "D", "U", "U"]

// check if s meets the requirements
if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {

// converting the array steps to integers
s = s.map(steps => ((steps === "U") ? 1 : -1));
// [1, -1, -1, -1, 1, -1, 1, 1]

let path = 0;
for(let i in s) {
path += s[i];
if (path < 0 && !isInValley) {
// to check that we're not already in a valley
// start of a valley
isInValley = true;
}
if (path == 0 && isInValley) {
// to check if we're just coming out of a valley
// end of valley, increase count
valleys++; // increase count
isInValley = false; // reset isInValley
}

}
// 0 + 1 = 1 (Moved up = valley not started)
// 1 + -1 = 0 (Back to sea level = valley not started)
// 0 + -1 = -1 (Below sea level = valley started)
// -1 + -1 = -2 (Moved lower = still in valley
// -2 + 1 = -1 (Moved up = still in valley)
// -1 + -1 = -2 (Moved lower = still in valley)
// -2 + 1 = -1 (Moved up = still in valley)
// -1 + 1 = 0 (Back to sea level = 1 valley)
// initial = 0
// end = 0
}

// to make sure we return even when the req. are not met
return valleys;
}

Let’s run the same values again from above:

// Example 1
// n = 8
// s = "UDDDUDUU"
countingValleys(8, "UDDDUDUU");// path = 1
// isInValley = false
// valleys = 0
// path = 0
// isInValley = false
// valleys = 0
// path = -1
// isInValley = true
// valleys = 0
// path = -2
// isInValley = true
// valleys = 0
// path = -1
// isInValley = true
// valleys = 0
// path = -2
// isInValley = true
// valleys = 0
// path = -1
// isInValley = true
// valleys = 0
// path = 0
// isInValley = false
// valleys = 1
// Solution = 1

Here is Example 2 (nearly the same):

// Example 2
// n = 10
// s = UDDDUDUUDU
// ...// path = 0
// isInValley = false
// valleys = 1
// path = -1
// isInValley = true
// valleys = 1
// path = 0
// isInValley = false
// valleys = 2
// Solution = 2

Now that we have the solution, let’s refactor the for loop, with some more performing method, such as map and reduce.

Before

function countingValleys(n, s) {
const min = 2;
const max = 1000000;
let valleys = 0;
let isInValley = false;

s = (typeof s === "string") ? s.split('') : s;

if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {

s = s.map(steps => ((steps === "U") ? 1 : -1));

let path = 0;
for(let i in s) {
path += s[i];
if (path < 0 && !isInValley) {
isInValley = true;
}
if (path == 0 && isInValley) {
valleys++;
isInValley = false;
}
}
}

return valleys;
}

After

function countingValleys(n, s) {
const min = 2;
const max = 1000000;
let valleys = 0;
let isInValley = false;
s = (typeof s === "string") ? s.split('') : s;

if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {

// remove s = s.map because we're already iterating
s.map(steps => ((steps === "U") ? 1 : -1))
.reduce((prev, next) => {
if (prev < 0 && !isInValley) {
isInValley = true;
}
if ((prev + next) === 0 && isInValley) {
valleys++;
isInValley = false;
}
// continue incrementing by adding
return prev + next;
});

}

return valleys;
}

Solution

And here is the full solution:

function countingValleys(n, s) {
const min = 2;
const max = 1000000;
let isInValley = false;
let valleys = 0;
s = (typeof s === "string") ? s.split('') : s;

if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {

s.map(steps => ((steps === "U") ? 1 : -1))
.reduce((prev, next) => {
if (prev < 0 && !isInValley) {
isInValley = true;
}
if ((prev + next) === 0 && isInValley) {
valleys++;
isInValley = false;
}

return prev + next;
});
}

return valleys;
}

Test Cases

// N = 8, S = "UDDDUDUU", Expected 1
// N = 12, S = "DDUUDDUDUUUD", Expected 2
// N = 1, S = "DU", Expected 0
// N = 2, S = "DU", Expected 1
// N = 3, S = "DDU", Expected 0
// N = 1000001, S = "DDU", Expected 0
// N = 20, S = "DDUUDDUUDDUUDDUUDDUU", Expected 5
// N = 10, S = "UUUUUDUUUU", Expected 0
countingValleys(8, "UDDDUDUU"); // 1 ✅
countingValleys(12, "DDUUDDUDUUUD"); // 2 ✅
countingValleys(1, "DU"); // 0 ✅
countingValleys(2, " DU"); // 1 ✅
countingValleys(3, "DDU"); // 0 ✅
countingValleys(100001, "DDU"); // 0 ✅
countingValleys(20, "DDUUDDUUDDUUDDUUDDUU"); // 5 ✅
countingValleys(10, "UUUUUDUUUU"); // 0 ✅

Feedback?

If you have some tips or recommendations on how this can be optimized, or even a better solution, I would definitely be open to talk about it and welcome any feedback.

If you got value from this, share it on twitter 🐦 or other social media platforms. Thanks again for reading. 🙏

Please also follow me on twitter: @codingwithmanny and instagram at @codingwithmanny.

Image for post
Image for post

Web Application / Full Stack JavaScript Developer & Aspiring DevOps

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store