2210. Count Hills and Valleys in an Array

[mah-shamim]

Topics: Array, Weekly Contest 285

You are given a 0-indexed integer array nums. An index i is part of a hill in nums if the closest non-equal neighbors of i are smaller than nums[i]. Similarly, an index i is part of a valley in nums if the closest non-equal neighbors of i are larger than nums[i]. Adjacent indices i and j are part of the same hill or valley if nums[i] == nums[j].

Note that for an index to be part of a hill or valley, it must have a non-equal neighbor on both the left and right of the index.

Return the number of hills and valleys in nums.

Example 1:

• Input: nums = [2,4,1,1,6,5]
• Output: 3
• Explanation:
  At index 0: There is no non-equal neighbor of 2 on the left, so index 0 is neither a hill nor a valley.
  At index 1: The closest non-equal neighbors of 4 are 2 and 1. Since 4 > 2 and 4 > 1, index 1 is a hill.
  At index 2: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 2 is a valley.
  At index 3: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 3 is a valley, but note that it is part of the same valley as index 2.
  At index 4: The closest non-equal neighbors of 6 are 1 and 5. Since 6 > 1 and 6 > 5, index 4 is a hill.
  At index 5: There is no non-equal neighbor of 5 on the right, so index 5 is neither a hill nor a valley.
  There are 3 hills and valleys so we return 3.

Example 2:

• Input: nums = [6,6,5,5,4,1]
• Output: 0
• Explanation:
  At index 0: There is no non-equal neighbor of 6 on the left, so index 0 is neither a hill nor a valley.
  At index 1: There is no non-equal neighbor of 6 on the left, so index 1 is neither a hill nor a valley.
  At index 2: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 2 is neither a hill nor a valley.
  At index 3: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 3 is neither a hill nor a valley.
  At index 4: The closest non-equal neighbors of 4 are 5 and 1. Since 4 < 5 and 4 > 1, index 4 is neither a hill nor a valley.
  At index 5: There is no non-equal neighbor of 1 on the right, so index 5 is neither a hill nor a valley.
  There are 0 hills and valleys so we return 0.

Constraints:

• 3 <= nums.length <= 100
• 1 <= nums[i] <= 100

Hint:

1. For each index, could you find the closest non-equal neighbors?
2. Ensure that adjacent indices that are part of the same hill or valley are not double-counted.

[mah-shamim]

We need to count the number of hills and valleys in an array. A hill is an index where the closest non-equal neighbors on both sides are smaller than the current element. Similarly, a valley is an index where the closest non-equal neighbors on both sides are larger than the current element. Adjacent indices with the same value are considered part of the same hill or valley.

Approach

1. Preprocess the Array: Remove consecutive duplicates from the array. This step groups adjacent indices with the same value into a single segment, as they are considered part of the same hill or valley.
2. Check for Hills and Valleys: Traverse the processed array (excluding the first and last elements since they lack neighbors on one side). For each element, check if it is greater than both neighbors (hill) or smaller than both neighbors (valley).
3. Count Valid Hills and Valleys: Increment the count for each valid hill or valley encountered during the traversal.

Let's implement this solution in PHP: 2210. Count Hills and Valleys in an Array

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function countHillValley($nums) {
    $arr = [];
    $n = count($nums);
    $arr[] = $nums[0];
    for ($i = 1; $i < $n; $i++) {
        if ($nums[$i] != $nums[$i - 1]) {
            $arr[] = $nums[$i];
        }
    }

    $m = count($arr);
    if ($m < 3) {
        return 0;
    }

    $count = 0;
    for ($i = 1; $i < $m - 1; $i++) {
        if (($arr[$i] > $arr[$i - 1] && $arr[$i] > $arr[$i + 1]) ||
            ($arr[$i] < $arr[$i - 1] && $arr[$i] < $arr[$i + 1])) {
            $count++;
        }
    }
    return $count;
}

// Test cases
echo countHillValley([2,4,1,1,6,5]); // Output: 3
echo countHillValley([6,6,5,5,4,1]); // Output: 0
?>

Explanation:

1. Preprocessing: The array is processed to remove consecutive duplicates. For example, [2, 4, 1, 1, 6, 5] becomes [2, 4, 1, 6, 5]. This step ensures that adjacent indices with the same value are treated as a single segment.
2. Edge Handling: If the processed array has fewer than 3 elements, it's impossible to have both left and right neighbors, so the result is 0.
3. Traversal: The processed array is traversed from the second element to the second-to-last element. For each element, it checks if the element is either:
   • Hill: Greater than both adjacent elements.
   • Valley: Smaller than both adjacent elements.
4. Counting: Each valid hill or valley increments the count. The final count is returned as the result.

This approach efficiently counts hills and valleys by first simplifying the array to avoid redundant checks on consecutive duplicates, then systematically evaluating each relevant element's neighbors. The solution handles all edge cases and processes the array in linear time.

[kovatz]

Thanks for solving the problem of "Count Hills and Valleys in an Array"

[mah-shamim]

Thanks