Problem

Given an array of integers nums and an integer k, an element nums[i] is considered good if it is strictly greater than the elements at indices i - k and i + k (if those indices exist). If neither of these indices exists , nums[i] is still considered good.

Return the sum of all the good elements in the array.

Examples

Example 1

1
2
3
4
5
Input: nums = [1,3,2,1,5,4], k = 2
Output: 12
Explanation:
The good numbers are `nums[1] = 3`, `nums[4] = 5`, and `nums[5] = 4` because
they are strictly greater than the numbers at indices `i - k` and `i + k`.

Example 2

1
2
3
4
5
Input: nums = [2,1], k = 1
Output: 2
Explanation:
The only good number is `nums[0] = 2` because it is strictly greater than
`nums[1]`.

Constraints

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 1000
  • 1 <= k <= floor(nums.length / 2)

Solution

Method 1 – Direct Index Comparison

Intuition

The problem asks us to find elements that are strictly greater than their neighbors at a fixed distance k, if those neighbors exist. If either neighbor does not exist, the element is automatically considered good. By iterating through the array and checking these conditions for each element, we can efficiently identify and sum all good numbers.

Approach

For each index i, check if nums[i] is strictly greater than nums[i-k] and nums[i+k] (if those indices exist). If so, add nums[i] to the sum. If neither index exists, nums[i] is always good.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <vector>
using namespace std;
class Solution {
public:
    int sumOfGoodNumbers(vector<int>& nums, int k) {
        int n = nums.size(), sum = 0;
        for (int i = 0; i < n; ++i) {
            bool good = true;
            if (i - k >= 0 && nums[i] <= nums[i - k]) good = false;
            if (i + k < n && nums[i] <= nums[i + k]) good = false;
            if (good) sum += nums[i];
        }
        return sum;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int sumOfGoodNumbers(int[] nums, int k) {
        int n = nums.length, sum = 0;
        for (int i = 0; i < n; ++i) {
            boolean good = true;
            if (i - k >= 0 && nums[i] <= nums[i - k]) good = false;
            if (i + k < n && nums[i] <= nums[i + k]) good = false;
            if (good) sum += nums[i];
        }
        return sum;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    fun sumOfGoodNumbers(nums: IntArray, k: Int): Int {
        val n = nums.size
        var sum = 0
        for (i in 0 until n) {
            var good = true
            if (i - k >= 0 && nums[i] <= nums[i - k]) good = false
            if (i + k < n && nums[i] <= nums[i + k]) good = false
            if (good) sum += nums[i]
        }
        return sum
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def sumOfGoodNumbers(self, nums: list[int], k: int) -> int:
        n = len(nums)
        total = 0
        for i in range(n):
            good = True
            if i - k >= 0 and nums[i] <= nums[i - k]:
                good = False
            if i + k < n and nums[i] <= nums[i + k]:
                good = False
            if good:
                total += nums[i]
        return total
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn sum_of_good_numbers(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let mut sum = 0;
        for i in 0..n {
            let mut good = true;
            if i as i32 - k >= 0 && nums[i] <= nums[(i as i32 - k) as usize] { good = false; }
            if i as i32 + k < n as i32 && nums[i] <= nums[(i as i32 + k) as usize] { good = false; }
            if good { sum += nums[i]; }
        }
        sum
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function sumOfGoodNumbers(nums: number[], k: number): number {
    const n = nums.length;
    let sum = 0;
    for (let i = 0; i < n; ++i) {
        let good = true;
        if (i - k >= 0 && nums[i] <= nums[i - k]) good = false;
        if (i + k < n && nums[i] <= nums[i + k]) good = false;
        if (good) sum += nums[i];
    }
    return sum;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)