Count Hills and Valleys in an Array

🏠 ⬅️ ➡️

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
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: nums(6)
    integer :: i, j
    integer :: nhills, nvalleys

    ! Example 1
    nums = [2,4,1,1,6,5]
    write(*,'(A,I0)') 'Example 1: ', solve(nums)

    ! Example 2
    nums = [6,6,5,5,4,1]
    write(*,'(A,I0)') 'Example 2: ', solve(nums)

contains

    function solve(nums) result(nhills_and_valleys)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: nhills, nvalleys
        integer :: i, j

        nhills = 0
        nvalleys = 0

        do i = 1, size(nums)-1
            ! Check if i is part of a hill
            if (nums(i+1) < nums(i)) then
                nhills = nhills + 1
            end if

            ! Check if i is part of a valley
            if (nums(i+1) > nums(i)) then
                nvalleys = nvalleys + 1
            end if
        end do

        nhills_and_valleys = nhills + nvalleys
    end function solve

end program main
✅ Compiled
✅ Executed
❌ Correct 
module hill_valley
    implicit none
    private
    public :: hill_valley_solution

contains

    function hill_valley_solution(nums) result(hills_valleys)
        integer, intent(in) :: nums(:)
        integer :: hills_valleys
        integer :: i, j, left_neighbor, right_neighbor

        hills_valleys = 0

        do i = 2, size(nums) - 1
            left_neighbor = nums(i - 1)
            right_neighbor = nums(i + 1)

            if (left_neighbor < nums(i) .and. right_neighbor < nums(i)) then
                hills_valleys = hills_valleys + 1
            else if (left_neighbor > nums(i) .and. right_neighbor > nums(i)) then
                hills_valleys = hills_valleys + 1
            end if
        end do

    end function hill_valley_solution

end module hill_valley

program test_hill_valley
    use hill_valley
    implicit none
    integer, parameter :: nums(6) = [2, 4, 1, 1, 6, 5]
    integer :: hills_valleys

    hills_valleys = hill_valley_solution(nums)

    write (*,*) "Hills and valleys: ", hills_valleys

end program test_hill_valley
🌐 Data from online sources 
def sorted_target_indices(nums, target):
    result = [i for i, num in enumerate(nums) if num == target]
    return sorted(result)

We iterate over the input array nums and check if the element at the current index is equal to the target. If it is, we add the current index to the result list. After iterating through the whole array, we sort the result list to ensure that the indices are in increasing order. Finally, we return the result list, which contains the target indices of the given element in the sorted array. If there are no target indices, the result list will be empty, and an empty list will be returned as specified.

🌐 Data from online sources 
#include <vector>
#include <algorithm>

std::vector<int> sortedTargetIndices(std::vector<int>& nums, int target) {
    std::vector<int> result;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == target) {
            result.push_back(i);
        }
    }
    std::sort(result.begin(), result.end());
    return result;
}

We iterate over the input array nums and check if the element at the current index is equal to the target. If it is, we add the current index to the result list. After iterating through the whole array, we sort the result list to ensure that the indices are in increasing order. Finally, we return the result list, which contains the target indices of the given element in the sorted array. If there are no target indices, the result list will be empty, and an empty list will be returned as specified.