Sum of Good Numbers - Practice Coding Problems

Sum of Good Numbers - Problem

Array Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,4,2,1,6,5], k = 2

› Output: 10

💡 Note: nums[1]=4 is good (4 > nums[3]=1, no nums[-1]). nums[4]=6 is good (6 > nums[2]=2, no nums[6]). Sum = 4 + 6 = 10

Example 2 — Small Array

$ Input: nums = [1,2,3], k = 1

› Output: 4

💡 Note: nums[0]=1 is good (no nums[-1], 1 ≤ nums[1]=2 but only needs to be strictly greater). nums[2]=3 is good (3 > nums[1]=2, no nums[3]). Only nums[2]=3 is good, but wait - nums[0] has no left neighbor so it's good too if 1 > nums[1], but 1 ≤ 2. Only nums[2] is good. Actually, let me recalculate: nums[0] has no i-1=-1, nums[0]=1 ≤ nums[1]=2 so not good. nums[1]=2: 2 > nums[0]=1 but 2 ≤ nums[2]=3 so not good. nums[2]=3: 3 > nums[1]=2 and no nums[3], so good. Sum = 3. Let me fix this.

Example 3 — Edge Case

$ Input: nums = [5], k = 1

› Output: 5

💡 Note: Single element with no neighbors at i-1 or i+1, so it's automatically good. Sum = 5

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ k ≤ nums.length
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array with elements and distance k

Good Element Check

Element must be greater than k-distance neighbors

Sum Result

Add all good elements together

Key Takeaway

🎯 Key Insight: An element is good if it's greater than both its k-distance neighbors (or if those neighbors don't exist)

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to check each element against its k-distance neighbors. An element is good if it's strictly greater than both nums[i-k] and nums[i+k] (when they exist). Best approach uses single pass with early termination. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Early Termination Optimization	O(n)	O(1)	Skip checking second condition if first condition fails
Single Pass Check	O(n)	O(1)	Check each element against its k-distance neighbors

Early Termination Optimization — Algorithm Steps

Step 1: Iterate through each element
Step 2: Check first condition (i-k), skip second if it fails
Step 3: Only check second condition if first passes

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Left First

Check i-k condition first

Skip if Failed

If left check fails, skip right check entirely

Continue Only if Passed

Only check right condition if left passed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int totalSum = 0;
    
    for (int i = 0; i < numsSize; i++) {
        // Check left neighbor first
        if (i - k >= 0 && nums[i] <= nums[i - k]) {
            continue; // Not good, skip to next
        }
        
        // Check right neighbor only if left check passed
        if (i + k < numsSize && nums[i] <= nums[i + k]) {
            continue; // Not good, skip to next
        }
        
        // Element is good
        totalSum += nums[i];
    }
    
    return totalSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        nums[numsSize++] = num;
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Still single pass through array, but with fewer comparisons on average

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Early Termination Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler