Skip to main content
Talentd

Sum of Good Numbers - Solution & Explanation

EasyArray7 min readAsked at: Google, Bcg
Practice this problem

Problem Statement

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

Approach Overview

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.

Solution

We can traverse the array nums and check each element nums[i] to see if it meets the conditions:

  • If i \ge k and nums[i] \le nums[i - k], then nums[i] is not a good number.
  • If i + k < len(nums) and nums[i] \le nums[i + k], then nums[i] is not a good number.
  • Otherwise, nums[i] is a good number, and we add it to the answer.

After traversing, we return the answer.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Neighbor Check (Brute Traversal)O(n)O(1)Best for clarity when first implementing the problem
Single-Pass Optimized TraversalO(n)O(1)Preferred interview solution with minimal checks and clean logic

Video Solution

Leetcode | 3452. Sum of Good Numbers | Easy | Java Solution • Developer Docs • 1,204 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Sum of Good Numbers easy or hard?
Sum of Good Numbers is classified as an easy problem. The main challenge is handling boundary cases correctly when i-k or i+k falls outside the array. Once the index checks are handled, the logic becomes a straightforward linear scan.
Sum of Good Numbers Python/Java solution
Both Python and Java implementations follow the same logic: iterate through the array, check nums[i-k] and nums[i+k] when the indices are valid, and accumulate values that satisfy the conditions. The implementation stays O(n) time and O(1) space in both languages.
How to solve Sum of Good Numbers in O(n)?
Iterate through the array from index 0 to n-1. For each position, check whether the element k positions to the left and right exists and ensure the current value is strictly greater than those neighbors. If the conditions hold, add the number to the running sum. Because each element is processed once, the solution runs in linear time.
What is the best approach for Sum of Good Numbers?
The best approach is a single-pass array traversal. For each index i, compare nums[i] with nums[i-k] and nums[i+k] if those indices exist. If the value is strictly greater than both neighbors, add it to the sum. This method runs in O(n) time and uses O(1) extra space.
Is Sum of Good Numbers asked at Google/Amazon/Meta?
The problem represents a typical easy-level array traversal question often used in coding screens to test indexing, boundary checks, and conditional logic. Similar array comparison problems frequently appear in interviews at companies like Amazon, Google, and Meta, especially for entry-level or early interview rounds.
What data structure is used in Sum of Good Numbers?
The solution primarily uses a simple array traversal. No additional data structures such as hash maps or stacks are required because the decision depends only on elements located k positions away in the same array.
What is the time complexity of Sum of Good Numbers?
The time complexity is O(n) because the algorithm scans the array once and performs constant-time comparisons at each index. Only two potential neighbor checks are required per element. The space complexity remains O(1) since no additional data structures are used.

Ready to solve this problem?

Practice Sum of Good Numbers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays