Sum of Good Numbers — Solution in Python, Java & C++
Sum of Good Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon.
Sum of Good Numbers is an easy coding problem on arrays, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array nums and an integer k, the element nums[i] is good when it is strictly greater than nums[i - k] and than nums[i + k] — each comparison applies only if that index exists. An element with neither index in range is good automatically.
Return the sum of all good elements.
Example 1
Input: nums = [1,3,2,1,5,4], k = 2
Output: 12
Explanation: 3 (index 1) beats nums[3] = 1; 5 (index 4) beats nums[2] = 2; 4 (index 5) beats nums[3] = 1. 3 + 5 + 4 = 12.
Example 2
Input: nums = [2,1], k = 1
Output: 2
Explanation: 2 beats its only partner 1; 1 does not beat 2.
Example 3
Input: nums = [4,4,4], k = 1
Output: 0
Explanation: Equal values are not strictly greater.
Constraints
2 <= nums.length <= 1001 <= nums[i] <= 10001 <= k <= floor(nums.length / 2)
Hints for Sum of Good Numbers
Hint 1
Each element is compared with at most two others,
kpositions away on each side.Hint 2
Treat a missing partner (index out of range) as a comparison that passes.
How to solve Sum of Good Numbers
Check the definition directly: for every index, compare with i - k and i + k when those exist, and add the element if it wins every comparison that applies.
Approach
- Set
sum = 0. - For each
i, letok = true; ifi - k >= 0andnums[i] <= nums[i - k], setok = false; likewise fori + k < n. - If
ok, addnums[i]tosum. Returnsum.
Why it works
The loop applies the definition of a good element literally to every index, so exactly the good elements are summed.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- "Strictly greater": ties make an element not good.
- A missing partner does not disqualify an element — only an existing larger-or-equal one does.
Reference solution
Python
from typing import List
def sumOfGoodNumbers(nums: List[int], k: int) -> int:
n = len(nums)
total = 0
for i, v in enumerate(nums):
if i - k >= 0 and v <= nums[i - k]:
continue
if i + k < n and v <= nums[i + k]:
continue
total += v
return totalJava
public static int sumOfGoodNumbers(int[] nums, int k) {
int n = nums.length, total = 0;
for (int i = 0; i < n; i++) {
if (i - k >= 0 && nums[i] <= nums[i - k]) continue;
if (i + k < n && nums[i] <= nums[i + k]) continue;
total += nums[i];
}
return total;
}C++
int sumOfGoodNumbers(vector<int>& nums, int k) {
int n = nums.size(), total = 0;
for (int i = 0; i < n; i++) {
if (i - k >= 0 && nums[i] <= nums[i - k]) continue;
if (i + k < n && nums[i] <= nums[i + k]) continue;
total += nums[i];
}
return total;
}JavaScript
var sumOfGoodNumbers = function(nums, k) {
var n = nums.length, total = 0;
for (var i = 0; i < n; i++) {
if (i - k >= 0 && nums[i] <= nums[i - k]) continue;
if (i + k < n && nums[i] <= nums[i + k]) continue;
total += nums[i];
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays