How To Solve The Counting Valleys Challenge

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

How To Solve The Counting Valleys Code Challenge

Problem

N = 8
S = UDDDUDUU
_/\ _
\ /
\/\/
Result: 1 Valley
N = 10
S = UDDDUDUUDU
_/\ _ _
\ / \/
\/\/
Result: 2 Valleys

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

Covering Our Bases

Counting The 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 ar === "string") ? s.split('') : s;
// check if s meets the requirements
if (s.length >= min && s.length <= max) {
// continue
}
}

Validating N

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

Converting Steps To Integers

// 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]

}
}

Looping Over Steps

// 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

}
}

Defining Initial Conditions For Paths

// 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
}
}

Accounting For Still Being In The 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;
}
// 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
// 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

Refactoring For Performance

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;
}
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

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?

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