LeetCode Problem 3452

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 3452 - Sum of Good Numbers

Problem Understanding

This problem gives us an integer array nums and an integer k. For every position i, we need to determine whether nums[i] is a good number.

A number is considered good if it is strictly greater than the element located k positions to its left, nums[i - k], when that index exists, and also strictly greater than the element located k positions to its right, nums[i + k], when that index exists.

An important detail is that these comparisons are only required for indices that actually exist. If one of the two indices is outside the array bounds, that comparison is ignored. If both indices are outside the array bounds, the element is automatically considered good.

The goal is to examine every element, determine whether it satisfies the good-number condition, and return the sum of all such elements.

For example, if k = 2, then for index i = 3, we compare:

• nums[3] with nums[1]
• nums[3] with nums[5]

provided those indices exist.

The constraints are very small:

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

Since the array contains at most 100 elements, even relatively simple solutions are easily fast enough. There is no need for advanced data structures or optimization techniques.

Some important edge cases include:

• Elements near the beginning of the array, where i - k does not exist.
• Elements near the end of the array, where i + k does not exist.
• Elements where only one neighboring comparison is required.
• Equal values, since the condition requires strictly greater, not greater than or equal.
• Situations where an element has neither comparison index available, making it automatically good.

Approaches

Brute Force Approach

The most direct solution is to examine every element independently.

For each index i, we check whether the left comparison index i - k exists. If it does and nums[i] <= nums[i - k], then the element is not good.

Similarly, we check whether the right comparison index i + k exists. If it does and nums[i] <= nums[i + k], then the element is not good.

If neither comparison fails, the element is good and its value is added to the answer.

This approach is correct because the problem definition only requires examining up to two specific positions for each element.

Since each element requires at most two comparisons, the work per element is constant.

Key Insight

The key observation is that every element only depends on at most two other elements, namely those exactly k positions away.

There is no need to search larger ranges, maintain auxiliary data structures, or preprocess information. A single pass through the array is sufficient. During that pass, we directly verify the required conditions and accumulate the sum.

This gives an optimal linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Check both possible neighbors for every element
Optimal	O(n)	O(1)	Single pass, direct verification of good-number conditions

In this problem, the brute-force and optimal approaches are effectively the same because each element only requires constant work.

Algorithm Walkthrough

1. Initialize a variable total_sum to 0.
2. Iterate through every index i in the array.
3. Assume the current element is good by setting a boolean flag such as is_good = True.
4. Check whether the left comparison index exists:

• If i - k >= 0, compare nums[i] with nums[i - k].
• If nums[i] <= nums[i - k], mark the element as not good.

5. Check whether the right comparison index exists:

• If i + k < n, compare nums[i] with nums[i + k].
• If nums[i] <= nums[i + k], mark the element as not good.

6. After all required comparisons are performed, if is_good remains True, add nums[i] to total_sum.
7. Continue until every element has been processed.
8. Return total_sum.

Why it works

For every index, the algorithm checks exactly the conditions specified in the problem statement. If a comparison index exists, the algorithm verifies that the current element is strictly greater than the corresponding value. If a comparison index does not exist, the condition is ignored exactly as required. Therefore, an element is added to the sum if and only if it satisfies the definition of a good number, guaranteeing correctness.

Python Solution

from typing import List

class Solution:
    def sumOfGoodNumbers(self, nums: List[int], k: int) -> int:
        total_sum = 0
        n = len(nums)

        for i in range(n):
            is_good = True

            if i - k >= 0 and nums[i] <= nums[i - k]:
                is_good = False

            if i + k < n and nums[i] <= nums[i + k]:
                is_good = False

            if is_good:
                total_sum += nums[i]

        return total_sum

The implementation begins by storing the array length and initializing the answer accumulator.

The main loop processes each index exactly once. The variable is_good tracks whether the current element still satisfies all required conditions.

The first conditional handles the left-side comparison. It only executes when the left index exists. If the current value is not strictly greater, the element is marked as not good.

The second conditional performs the same logic for the right-side comparison.

After both checks, a good element contributes its value to the running total.

Finally, the accumulated sum is returned.

Go Solution

func sumOfGoodNumbers(nums []int, k int) int {
    totalSum := 0
    n := len(nums)

    for i := 0; i < n; i++ {
        isGood := true

        if i-k >= 0 && nums[i] <= nums[i-k] {
            isGood = false
        }

        if i+k < n && nums[i] <= nums[i+k] {
            isGood = false
        }

        if isGood {
            totalSum += nums[i]
        }
    }

    return totalSum
}

The Go implementation follows the same logic as the Python version.

Since the constraints are very small and values are at most 1000, standard Go int arithmetic is more than sufficient. No special handling for overflow is necessary. The solution operates directly on the input slice and uses only a few local variables, maintaining constant extra space.

Worked Examples

Example 1

Input

nums = [1, 3, 2, 1, 5, 4]
k = 2

i	nums[i]	Left Check	Right Check	Good?	Running Sum
0	1	N/A	1 > 2? No	No	0
1	3	N/A	3 > 1? Yes	Yes	3
2	2	2 > 1? Yes	2 > 5? No	No	3
3	1	1 > 3? No	1 > 4? No	No	3
4	5	5 > 2? Yes	N/A	Yes	8
5	4	4 > 1? Yes	N/A	Yes	12

Final answer:

12

Example 2

Input

nums = [2, 1]
k = 1

i	nums[i]	Left Check	Right Check	Good?	Running Sum
0	2	N/A	2 > 1? Yes	Yes	2
1	1	1 > 2? No	N/A	No	2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed once with at most two comparisons
Space	O(1)	Only a few variables are used regardless of input size

The algorithm performs a single pass through the array. For each element, only constant-time work is required because there are at most two relevant neighboring positions. No auxiliary data structures proportional to the input size are allocated, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def sumOfGoodNumbers(self, nums: List[int], k: int) -> int:
        total_sum = 0
        n = len(nums)

        for i in range(n):
            is_good = True

            if i - k >= 0 and nums[i] <= nums[i - k]:
                is_good = False

            if i + k < n and nums[i] <= nums[i + k]:
                is_good = False

            if is_good:
                total_sum += nums[i]

        return total_sum

sol = Solution()

assert sol.sumOfGoodNumbers([1, 3, 2, 1, 5, 4], 2) == 12  # Example 1
assert sol.sumOfGoodNumbers([2, 1], 1) == 2  # Example 2

assert sol.sumOfGoodNumbers([5, 1], 1) == 5  # First element only
assert sol.sumOfGoodNumbers([1, 5], 1) == 5  # Last element only

assert sol.sumOfGoodNumbers([3, 3, 3, 3], 1) == 0  # Strict inequality check

assert sol.sumOfGoodNumbers([10, 1, 10], 1) == 20  # Both ends good

assert sol.sumOfGoodNumbers([1, 2, 3, 4, 5], 2) == 9  # Mixed comparisons

assert sol.sumOfGoodNumbers([1000, 1, 1000, 1, 1000], 2) == 3000  # Large values

assert sol.sumOfGoodNumbers([7, 7, 7, 1], 2) == 0  # Equality prevents goodness

assert sol.sumOfGoodNumbers([9, 1, 2, 3], 2) == 12  # Missing comparison on one side

Test	Why
[1,3,2,1,5,4], k=2	Official example
[2,1], k=1	Official example
[5,1], k=1	Smallest valid array, first element good
[1,5], k=1	Smallest valid array, last element good
[3,3,3,3], k=1	Verifies strict inequality requirement
[10,1,10], k=1	Multiple good elements
[1,2,3,4,5], k=2	Increasing sequence with mixed outcomes
[1000,1,1000,1,1000], k=2	Large values and repeated good elements
[7,7,7,1], k=2	Equality should fail the condition
[9,1,2,3], k=2	Elements with only one valid comparison

Edge Cases

Elements Near the Beginning of the Array

For indices smaller than k, the position i - k does not exist. A common mistake is to attempt the comparison anyway, which can cause out-of-bounds access. The implementation explicitly checks i - k >= 0 before performing the comparison, ensuring only valid indices are used.

Elements Near the End of the Array

Similarly, for indices where i + k >= n, the right comparison position does not exist. The problem states that such comparisons should simply be ignored. The implementation handles this by checking i + k < n before accessing the right-side element.

Equal Values

The condition requires an element to be strictly greater than the relevant neighboring values. Using < instead of <= in the comparison logic would incorrectly classify equal values as good. The implementation correctly rejects equality through the checks:

nums[i] <= nums[i - k]

and

nums[i] <= nums[i + k]

Only One Neighbor Exists

Many elements near the boundaries have only one valid comparison index. The algorithm treats the missing side as automatically satisfied and only verifies the existing side. This exactly matches the problem specification and avoids incorrectly rejecting valid good numbers.

No Valid Comparison Indices

Although the given constraints prevent extremely large values of k, the problem definition states that if neither comparison index exists, the element is still good. The implementation naturally supports this behavior because neither comparison condition executes, leaving is_good equal to True.