algoadvance

Leetcode 2210. Count Hills and Valleys in an Array

Problem Statement

You are given a 0-indexed integer array nums. An index i in the array is considered a hill if the following conditions are met:

Similarly, an index i is considered a valley if the following conditions are met:

Return the number of hills and valleys in nums.

Clarifying Questions

  1. Q: Can nums have equal and consecutive elements? A: Yes, nums can have consecutive equal elements, but these should not count as hills or valleys.

  2. Q: What is the range of values in the array nums? A: The problem will specify that the values fit within a specified range which typically does not affect the logic of counting hills and valleys.

  3. Q: What should be the output if the array nums has less than three elements? A: If the array has less than three elements, it is impossible to form a hill or a valley, so the result should be 0.

Strategy

To solve this problem, we’ll iterate through the nums list starting from the second element and ending at the second last element (i.e., between indices 1 and nums.length - 2). For each element, we’ll check the following:

We’ll maintain a counter to keep track of the number of hills and valleys.

Steps:

  1. Initialize a counter count to 0.
  2. Loop through the array starting from index 1 to nums.length - 2.
  3. For each element, check if it satisfies the hill or valley condition.
  4. If it does, increment the counter.

Code

Here is the implementation based on the described strategy:

public class Solution {
    public int countHillValley(int[] nums) {
        if (nums.length < 3) return 0;

        int count = 0;

        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            
            int left = i - 1;
            // Move `left` to the leftmost non-equal value in the contiguous range
            while (left >= 0 && nums[left] == nums[i - 1]) {
                left--;
            }
            
            int right = i + 1;
            // Move `right` to the rightmost non-equal value in the contiguous range
            while (right < nums.length && nums[right] == nums[i + 1]) {
                right++;
            }
            
            if (left >= 0 && right < nums.length) {
                if (nums[i] > nums[left] && nums[i] > nums[right]) {
                    count++;
                } else if (nums[i] < nums[left] && nums[i] < nums[right]) {
                    count++;
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 4, 1, 1, 6, 5};
        System.out.println(solution.countHillValley(nums));  // Output should be 3
    }
}

Time Complexity

The time complexity of the implemented solution is O(n), where n is the number of elements in the array. This is because we make a single pass through the array while sometimes looking ahead or behind by at most a few steps.

The space complexity is O(1) because we are using a constant amount of extra space.

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