Watch 2 video solutions for Sum of Good Numbers, a easy level problem involving Array. This walkthrough by Developer Docs has 1,113 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
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:
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 <= 1001 <= nums[i] <= 10001 <= k <= floor(nums.length / 2)Problem Overview: You are given an integer array nums and an integer k. A number is considered good if it is strictly greater than the elements located k positions to its left and right (when those indices exist). The task is to scan the array and return the sum of all such good numbers.
Approach 1: Direct Neighbor Check (Brute Force Traversal) (Time: O(n), Space: O(1))
The straightforward way is to iterate through every index i and explicitly check the two positions that determine whether the number is good: i - k and i + k. For each element, first verify whether these indices are within array bounds. If the left index exists, ensure nums[i] > nums[i-k]. If the right index exists, ensure nums[i] > nums[i+k]. When both conditions hold (or the neighbor does not exist), add the value to a running sum. Since each element requires only constant-time comparisons, the entire array is processed in linear time. This approach relies purely on sequential scanning and works well for any input distribution.
Approach 2: Single-Pass Optimized Traversal (Time: O(n), Space: O(1))
The optimal implementation is still a single traversal but focuses on minimizing redundant checks and keeping the logic tight. As you iterate from left to right, evaluate the two possible constraints using simple boundary checks. Instead of branching into multiple nested conditions, compute boolean flags such as whether the left or right comparison is required. If both comparisons pass, accumulate the current value into the result. Because the algorithm performs only two comparisons per index and does not allocate extra structures, it maintains constant auxiliary space and optimal linear runtime.
This technique falls under standard array traversal patterns and is similar to many problems where you compare elements at fixed offsets. Practicing problems that involve sequential checks and condition-based aggregation strengthens your intuition for array scanning and simple traversal strategies.
Recommended for interviews: Interviewers expect the linear traversal solution. The brute-force reasoning—checking the required neighbors for each index—shows that you understand the definition of a good number. Implementing it cleanly in a single pass with proper boundary checks demonstrates strong control over array indexing and edge cases, which is typically what interviewers evaluate for easy array problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Neighbor Check (Brute Traversal) | O(n) | O(1) | Best for clarity when first implementing the problem |
| Single-Pass Optimized Traversal | O(n) | O(1) | Preferred interview solution with minimal checks and clean logic |