Counting Valleys HackerRank Solution in Python & Java | Step-by-Step Guide

Problem Overview

The Counting Valleys problem on HackerRank asks you to determine how many valleys a hiker walks through during a hike. The hiker's path is represented as a string of steps where each step is either 'U' (uphill) or 'D' (downhill).

You are given:

• An integer steps representing the total number of steps taken during the hike.
• A string path of length steps describing the sequence of uphill and downhill movements.

The goal is to count the number of valleys traversed. A valley is defined as a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up back to sea level.

This problem helps practice logical thinking, iteration, and conditional checks. Understanding how to track elevation changes relative to sea level is key, as a naive approach of simply counting ups and downs without context could lead to incorrect results.

Problem Difficulty & Tags

The Counting Valleys problem on HackerRank is generally considered Easy to Medium difficulty. While it doesn’t require complex algorithms, it does test your understanding of loops, conditionals, and careful tracking of state.

Key concepts and tags associated with this problem include:

• Implementation: Directly translating problem logic into code.
• Loops: Iterating over the path string step by step.
• Conditional Statements: Checking if the hiker is starting or ending a valley.
• Counting / State Tracking: Maintaining the current elevation relative to sea level.
• Python & Java: Popular languages for solving this problem.

Understanding the Problem

Let’s break down what the Counting Valleys problem is really asking in simple terms. Imagine a hiker starting at sea level. Each step they take can either move them uphill ('U') or downhill ('D').

A valley occurs when the hiker goes below sea level and comes back up. More formally:

• The hiker starts at sea level.
• A valley begins with a step down from sea level ('D' when at 0 elevation).
• The valley ends when the hiker returns to sea level (0 elevation).
• Steps above sea level are part of a mountain, which we do not count in this problem.

For example, consider the path DDUUUUDD:

• Steps 1-2: Down into a valley.
• Steps 3-4: Up toward sea level, completing the first valley.
• Steps 5-6: Up above sea level (mountain).
• Steps 7-8: Down, but if returning to sea level, counts as a valley.

The key challenge is tracking elevation changes relative to sea level and recognizing when a valley starts and ends. Simple step counting is not enough; you need to maintain the current altitude at each step to determine valleys accurately.

Approach / Logic Explanation

To solve the Counting Valleys problem, we need to track the hiker's elevation relative to sea level at each step and count valleys accurately. Let’s break down the logic step by step:

1. Initialize variables:
   • currentLevel = 0: Represents the hiker's current elevation. Sea level is 0.
   • valleys = 0: Counter for the number of valleys traversed.
   • inValley = false: A flag to track if the hiker is currently in a valley.
2. Iterate through each step:

   Loop over the path string, character by character:

   • If the step is 'U', increment currentLevel by 1.
   • If the step is 'D', decrement currentLevel by 1.
3. Check for valley entry and exit:
   • A valley starts when the hiker goes below sea level: currentLevel < 0 and inValley == false. Set inValley = true.
   • A valley ends when the hiker returns to sea level: currentLevel == 0 and inValley == true. Increment valleys by 1 and reset inValley = false.
4. Return the valley count: After processing all steps, the valleys variable holds the total number of valleys traversed.

Edge Cases to Consider:

• The path consists entirely of 'U' or 'D' steps. Valleys may not exist.
• Multiple valleys separated by mountains or flat sequences.
• Immediate transitions from one valley to another without returning above sea level fully.

Common Mistakes to Avoid:

• Counting a valley when the hiker hasn’t actually gone below sea level.
• Not resetting the inValley flag after returning to sea level.
• Misinterpreting uphill steps as valley exits when the hiker is still below sea level.

By carefully maintaining elevation and tracking the valley state, you can accurately count valleys in a single pass through the path.

Code Implementation

Here’s the solution for Counting Valleys using your original Python and Java code.

Python Solution

steps = int(input())
path = input()
u = False
d = False
tot = 0
vally = 0

for i in path:
    if i == 'U':
        if tot == 0:
            u = True
        tot += 1
    else:
        if tot == 0:
            d = True
        tot -= 1
    if tot == 0:
        if d == True:
            vally += 1
        u = False
        d = False

print(vally)
  

Java Solution

import java.util.*;
import java.io.*;

class Result {
    public void countVally(int n, String ar) {
        boolean u, d = false;
        int vally = 0, total = 0;
        for (int i = 0; i < n; i++) {
            if (ar.charAt(i) == 'U') {
                if (total == 0) {
                    u = true;
                }
                total += 1;
            } else if (ar.charAt(i) == 'D') {
                if (total == 0) {
                    d = true;
                }
                total -= 1;
            }
            if (total == 0) {
                if (d == true) {
                    vally += 1;
                }
                d = false;
                u = false;
            }
        }
        System.out.println(vally);
    }
}

public class Solution {
    public static void main(String[] args) {
        InputStreamReader r = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(r);
        try {
            int n = Integer.parseInt(br.readLine().trim());
            String path = br.readLine();
            Result res = new Result();
            res.countVally(n, path);
        } catch (Exception ex) {
            // Handle exceptions if needed
        }
    }
}
  

Step-by-Step Walkthrough

Let’s go through the Counting Valleys problem step by step, using your original code and logic to understand how it works.

Step 1: Initialize Variables

In your Python code, the variables are initialized as follows:

• tot = 0 – Keeps track of the current elevation relative to sea level.
• u = False – Flag to indicate if the hiker started an uphill from sea level.
• d = False – Flag to indicate if the hiker started a downhill from sea level.
• vally = 0 – Counter for the number of valleys traversed.

Step 2: Iterate Over Each Step

The code loops over each character in the path string. For each step:

• If the step is 'U' (uphill):
  • If the current elevation tot is 0, it means we are starting an uphill from sea level. So, u = True.
  • Increment the elevation: tot += 1.
• If the step is 'D' (downhill):
  • If the current elevation tot is 0, it means we are starting a downhill from sea level. So, d = True.
  • Decrement the elevation: tot -= 1.

Step 3: Check if a Valley Ends

After updating the elevation, the code checks if tot == 0, which indicates that the hiker has returned to sea level. At this point:

• If d == True, it means the hiker came up from a valley, so we increment the valley counter: vally += 1.
• Reset both flags: u = False and d = False to prepare for detecting the next valley or mountain.

Step 4: Output the Result

Finally, after processing all steps, the code prints the total number of valleys traversed:

print(vally)
  

Key Observations

• The u flag isn’t strictly necessary for valley counting; it’s used for symmetry in tracking uphill starts.
• The d flag is essential because a valley only counts if the hiker started below sea level.
• Maintaining tot as the current elevation is crucial for detecting sea level transitions.

This step-by-step approach ensures that each valley is counted correctly in a single pass through the path string.

Sample Input & Output

Here are some examples to illustrate the input and expected output:

Time & Space Complexity Analysis

Understanding the efficiency of your solution is important, especially for large inputs. Let's analyze the complexity of the given Python and Java solutions.

Time Complexity

• The code iterates through each step in the path string exactly once.
• For each step, it performs constant-time operations (comparison, addition/subtraction, and flag updates).
• Therefore, the overall time complexity is O(n), where n is the number of steps.

Space Complexity

• The solution uses a fixed number of variables: tot/currentLevel, vally/valleys, and u/d/inValley.
• No additional data structures are used that scale with input size.
• Therefore, the overall space complexity is O(1) (constant space).

Summary: The solution is highly efficient, running in linear time relative to the number of steps and using minimal memory.

Mistakes to Avoid & Tips

Related Problems

If you enjoyed solving Counting Valleys, here are some similar problems to practice:

• Jumping on the Clouds – HackerRank
• Mountain and Valley Counting – HackerRank
• Sock Merchant – HackerRank

Conclusion

The Counting Valleys problem is a great exercise to strengthen your understanding of loops, conditionals, and state tracking. By carefully monitoring elevation relative to sea level and using simple flags to track valleys, you can solve this problem efficiently in a single pass.

Remember, the key is to keep your logic clear: focus on when the hiker enters and exits a valley, and always test edge cases such as consecutive valleys or paths that never go below sea level. Once you master this approach, you’ll be better prepared for similar problems involving sequences and counting patterns.

Keep practicing, and don’t hesitate to revisit your code to refine readability and efficiency. With every problem you solve, your problem-solving skills will grow stronger!