# Sum of Good Numbers
**Difficulty:** EASY
[External](https://leetcode.com/problems/sum-of-good-numbers)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-good-numbers
**Data structures:** Array
---
## Problem
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)`

# Approaches
## Brute Force with Array Copying
This approach is a deliberately inefficient, brute-force method designed to highlight the importance of direct index access. Instead of directly calculating and accessing `nums[i-k]` and `nums[i+k]`, it simulates this by creating copies of the subarrays to the left and right of the current element. This is a highly inefficient way to access elements that are at a known offset and is used here to demonstrate a non-optimal solution.
**Time:** O(N^2), where N is the number of elements in `nums`. The main loop runs N times. Inside the loop, creating a copy of a part of the array can take up to O(N) time. This results in a nested, quadratic time complexity. · **Space:** O(N), where N is the number of elements in `nums`. In each iteration of the loop, a new array of size up to N-1 can be created, leading to linear space complexity.
**Pros:** It correctly solves the problem.; The logic is broken down into distinct steps for checking each neighbor, which might be simple to conceptualize for a beginner.
**Cons:** Very poor time complexity of O(N^2), making it unsuitable for large inputs.; High space complexity of O(N) due to the creation of temporary arrays in each iteration.; Overly complicated and inefficient for a problem that can be solved with simple index access.
### Explanation
The algorithm iterates through each element `nums[i]` of the array.

To check the left neighbor `nums[i-k]`, it first verifies if the index `i-k` is valid. If so, it creates a new array containing all elements to the left of `i` using a method like `Arrays.copyOfRange(nums, 0, i)`. Then it accesses the element at index `i-k` from this new array to perform the comparison.

Similarly, to check the right neighbor `nums[i+k]`, it creates a copy of the subarray to the right of `i` and accesses the required element at the adjusted index `k-1`.

This process of creating array copies inside a loop is computationally expensive. Copying an array of size M takes O(M) time. Since this is done for each of the N elements in the input array, the overall time complexity becomes quadratic.

```java
import java.util.Arrays;

class Solution {
    public int sumOfGoodNumbers(int[] nums, int k) {
        int n = nums.length;
        long sum = 0;

        for (int i = 0; i < n; i++) {
            boolean isGood = true;

            // Inefficiently check left neighbor via array copy
            if (i - k >= 0) {
                // This copy operation is expensive
                if (nums[i] <= nums[i - k]) {
                    isGood = false;
                }
            }

            // Inefficiently check right neighbor via array copy
            if (isGood && i + k < n) {
                // Index in the right part is k-1
                if (nums[i] <= nums[i + k]) {
                    isGood = false;
                }
            }

            if (isGood) {
                sum += nums[i];
            }
        }
        return (int) sum;
    }
}
```
### Algorithm
- 1. Initialize a variable `sum` to 0.
- 2. Loop through the array `nums` from `i = 0` to `nums.length - 1`.
- 3. For each element `nums[i]`, assume it is a good number by setting a flag, e.g., `boolean isGood = true;`.
- 4. **Check the left neighbor**: If the index `i - k` is valid (`>= 0`), create a temporary array `leftPart` by copying elements from `nums[0]` to `nums[i-1]`. Then, compare `nums[i]` with `leftPart[i-k]`. If `nums[i]` is not strictly greater, set `isGood` to `false`.
- 5. **Check the right neighbor**: If `isGood` is still true and the index `i + k` is valid (`< nums.length`), create another temporary array `rightPart` by copying elements from `nums[i+1]` to the end of the array. Compare `nums[i]` with `rightPart[k-1]`. If `nums[i]` is not strictly greater, set `isGood` to `false`.
- 6. If the `isGood` flag remains `true` after both checks, add `nums[i]` to the `sum`.
- 7. After the loop finishes, return the total `sum`.

## Optimal Single-Pass Approach
This is the most efficient and straightforward approach. It involves a single pass through the array. For each element, it directly accesses its neighbors at `i-k` and `i+k` (if they exist) using their calculated indices and performs the required comparisons. This avoids any redundant computations or inefficient data access patterns.
**Time:** O(N), where N is the length of `nums`. We iterate through the array once, and all operations inside the loop (index calculations, comparisons) take constant time, O(1). · **Space:** O(1). We only use a constant amount of extra space for variables like `sum`, `n`, and the loop counter, regardless of the input size.
**Pros:** Optimal time complexity, as we must examine each element at least once.; Minimal space usage, making it very memory-efficient.; The logic is simple, direct, and easy to understand and implement.
**Cons:** There are no significant cons to this approach as it is optimal in terms of time and space complexity.
### Explanation
The algorithm initializes a sum to zero and iterates through the input array `nums` from the first element to the last. In each iteration, for the current element `nums[i]`, it checks two conditions to determine if it's a "good" number.

- **Left Condition**: It first checks if the index `i - k` is within the array bounds (i.e., `i - k >= 0`). If it is, it compares `nums[i]` with `nums[i - k]`. If `nums[i]` is not strictly greater, the element is not good. If the index `i - k` is out of bounds, this condition is automatically met.

- **Right Condition**: Similarly, it checks if the index `i + k` is within bounds (i.e., `i + k < nums.length`). If it is, it compares `nums[i]` with `nums[i + k]`. If `nums[i]` is not strictly greater, the element is not good. If the index `i + k` is out of bounds, this condition is also automatically met.

An element `nums[i]` is considered "good" only if it satisfies both the left and right conditions. If an element is determined to be good, its value is added to a running total. After iterating through all the elements, the final sum is returned.

```java
class Solution {
    public int sumOfGoodNumbers(int[] nums, int k) {
        int n = nums.length;
        long sum = 0;

        for (int i = 0; i < n; i++) {
            boolean isGood = true;
            
            // Check left neighbor
            if (i - k >= 0) {
                if (nums[i] <= nums[i - k]) {
                    isGood = false;
                }
            }
            
            // Check right neighbor only if left condition is still met
            if (isGood && i + k < n) {
                if (nums[i] <= nums[i + k]) {
                    isGood = false;
                }
            }
            
            if (isGood) {
                sum += nums[i];
            }
        }
        
        return (int) sum;
    }
}
```
### Algorithm
- 1. Initialize a variable `sum` to 0.
- 2. Get the length of the array, `n = nums.length`.
- 3. Loop through the array `nums` from index `i = 0` to `n - 1`.
- 4. For each `nums[i]`, assume it's a good number by initializing a boolean flag, `isGood = true`.
- 5. **Check left condition**: If the index `i - k` is valid (i.e., `i - k >= 0`), check if `nums[i] <= nums[i - k]`. If it is, the number is not good, so set `isGood = false`.
- 6. **Check right condition**: If `isGood` is still true and the index `i + k` is valid (i.e., `i + k < n`), check if `nums[i] <= nums[i + k]`. If it is, set `isGood = false`.
- 7. If the `isGood` flag is still `true` after these checks, it means `nums[i]` is a good number. Add `nums[i]` to `sum`.
- 8. After the loop completes, return the final `sum`.

# Solutions
### Java

```java
class Solution {
public
  int sumOfGoodNumbers(int[] nums, int k) {
    int ans = 0;
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      if (i >= k && nums[i] <= nums[i - k]) {
        continue;
      }
      if (i + k < n && nums[i] <= nums[i + k]) {
        continue;
      }
      ans += nums[i];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int sumOfGoodNumbers(vector<int> &nums, int k) {
    int ans = 0;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      if (i >= k && nums[i] <= nums[i - k]) {
        continue;
      }
      if (i + k < n && nums[i] <= nums[i + k]) {
        continue;
      }
      ans += nums[i];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def sumOfGoodNumbers(self, nums: List[int], k: int) -> int: ans = 0 for i, x in enumerate(nums): if i >= k and x <= nums[i - k]: continue if i + k < len(nums) and x <= nums[i + k]: continue ans += x return ans

```