algoadvance

Leetcode 2210. Count Hills and Valleys in an Array Sure, let’s break this down step by step.

Problem Statement

You are given a 0-indexed integer array nums. An index i is part of a hill or a valley if the surroundings fulfill the following conditions:

Count the number of hills and valleys in the given array nums.

Example:

Input: nums = [2, 4, 1, 1, 6, 5]
Output: 3
Explanation: We have 3 hills or valleys, they are 4, 1, and 6.

Clarifying Questions

  1. Q: What is the minimum and maximum length of nums? A: The minimum length of nums is 3, and there is no explicit limit but generally follows the typical constraints of competitive programming problems (e.g., up to (10^5)).

  2. Q: Can there be consecutive equal numbers? A: Yes, consecutive equal numbers are allowed, but they cannot form hills or valleys directly.

Strategy

To solve this problem, we’ll iterate over the array nums and check each element (except the first and last element) to see if it forms a hill or a valley. We’ll handle consecutive equal numbers carefully to avoid false counts.

  1. We’ll iterate through the array from the second element to the second-last element.
  2. For each element nums[i], we check its neighbors nums[i-1] and nums[i+1].
  3. We’ll skip checking when neighboring elements are equal to ensure no false positives.
  4. Count the number of elements satisfying the hill or valley conditions.

Code

Here’s the implementation in C++:

#include <vector>

class Solution {
public:
    int countHillValley(std::vector<int>& nums) {
        int count = 0;
        
        for (int i = 1; i < nums.size() - 1; ++i) {
            if ((nums[i-1] < nums[i] && nums[i] > nums[i+1]) || (nums[i-1] > nums[i] && nums[i] < nums[i+1])) {
                ++count;
            }
            // Skip the same elements to avoid double-counting
            while (i < nums.size() - 1 && nums[i] == nums[i+1]) {
                ++i;
            }
        }
        
        return count;
    }
};

Time Complexity

This approach ensures that we efficiently count the number of hills and valleys in the array with a single traversal, adhering to the constraints and handling edge cases like consecutive equal elements appropriately.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI