Sum of Good Numbers

Easy
1848.

Sum of Good Numbers

Sum of Good Numbers is an easy coding problem on arrays, asked in Amazon interviews.

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 <= 100
  • 1 <= nums[i] <= 1000
  • 1 <= k <= floor(nums.length / 2)
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var sumOfGoodNumbers = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 1 <= nums[i] <= 1000
  • 1 <= k <= floor(nums.length / 2)

Hints for Sum of Good Numbers

  1. Hint 1

    Each element is compared with at most two others, k positions away on each side.

  2. 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

  1. Set sum = 0.
  2. For each i, let ok = true; if i - k >= 0 and nums[i] <= nums[i - k], set ok = false; likewise for i + k < n.
  3. If ok, add nums[i] to sum. Return sum.

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 total

Java

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