3452. Sum of Good Numbers

Problem Description

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.

Intuition

To determine whether an element in the array is "good", we need to check its neighboring elements that are k positions away to the left and right. Specifically:

For each element at index i, check if it is greater than the element at index i - k, but only if this index exists (i.e., i >= k).
Similarly, check if it is greater than the element at index i + k, if this index exists within the bounds of the array (i.e., i + k < len(nums)).
If the element is greater than both of these, or if one/both comparisons are not possible due to index bounds, then this element is considered "good".

The straightforward way to approach this is by iterating through the array and applying these checks for each element. If an element satisfies these conditions, add it to the cumulative sum of good elements.

Solution Approach

The solution employs a straightforward traversal strategy over the array nums:

Initialize a variable ans to zero. This will store the sum of all the "good" numbers in the array.
Iterate through each index i and corresponding element x in the array nums.
For each position i, we check two conditions:
- If i >= k: This condition checks if there is a valid index i-k. If nums[i] is less than or equal to nums[i-k], continue to the next iteration as nums[i] is not a good number.
- If i + k < len(nums): This verifies the existence of the index i+k within the array boundaries. If nums[i] is less than or equal to nums[i+k], continue as nums[i] is not good.
If neither of the above conditions holds, nums[i] is a good number. Add x (i.e., nums[i]) to ans.
After checking all elements, ans will contain the sum of all good numbers. Return this sum.

The key pattern used here is iteration with boundary checks to ensure we do not attempt accessing out-of-bound indices. This results in an efficient O(n) solution, where n is the length of the array, since each element is examined a constant number of times.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider the array nums = [5, 10, 6, 3, 9] and k = 2.

Initialize ans = 0 to keep track of the sum of good numbers.
Iterate through each element in the array:
- Index 0 (Element: 5):
  - i - k = -2 (invalid index) and i + k = 2, compare 5 with 6. No element at i - k, so we only need to check the right neighbor if it exists.
  - 5 is not greater than 6, skip this as 5 is not good.
- Index 1 (Element: 10):
  - i - k = -1 (invalid index) and i + k = 3, compare 10 with 3. No left neighbor, so consider the right neighbor only if it exists.
  - 10 is greater than 3.
  - Add 10 to ans. Now, ans = 10.
- Index 2 (Element: 6):
  - i - k = 0, compare 6 with 5, and i + k = 4, compare 6 with 9.
  - 6 is greater than 5, but not greater than 9. Thus, not considered good.
- Index 3 (Element: 3):
  - i - k = 1, compare 3 with 10, and i + k = 5 (invalid index). Only consider the left if it exists.
  - 3 is not greater than 10, not good.
- Index 4 (Element: 9):
  - i - k = 2, compare 9 with 6, i + k = 6 (invalid index). Only compare with left.
  - 9 is greater than 6.
  - Add 9 to ans. Now, ans = 19.
After iterating through the array, the sum of all good elements is 19.
The final output is 19, representing the sum of the good elements.

Solution Implementation

1from typing import List
2
3class Solution:
4    def sumOfGoodNumbers(self, nums: List[int], k: int) -> int:
5        # Initialize the sum to 0
6        total_sum = 0  
7      
8        # Iterate over the list with index and value
9        for index, value in enumerate(nums):
10            # Check the left side condition: skip number if it's not greater than nums[index - k]
11            if index >= k and value <= nums[index - k]:
12                continue  
13          
14            # Check the right side condition: skip number if it's not greater than nums[index + k]
15            if index + k < len(nums) and value <= nums[index + k]:
16                continue  
17          
18            # If both conditions above are false, add the value to the sum
19            total_sum += value  
20      
21        # Return the final calculated sum
22        return total_sum
23

1class Solution {
2  
3    // Method to calculate the sum of "good" numbers according to the specified conditions.
4    public int sumOfGoodNumbers(int[] nums, int k) {
5        int ans = 0; // Initialize answer to zero for accumulating the sum of good numbers.
6        int n = nums.length; // Get the length of the array for boundary checks.
7      
8        // Iterate through every element in the array.
9        for (int i = 0; i < n; ++i) {
10            // Check if the current element has a left neighbor k places away that is greater,
11            // if so, skip this element.
12            if (i >= k && nums[i] <= nums[i - k]) {
13                continue;
14            }
15          
16            // Check if the current element has a right neighbor k places away that is greater,
17            // if so, skip this element.
18            if (i + k < n && nums[i] <= nums[i + k]) {
19                continue;
20            }
21          
22            // If the current element passed both checks, add it to the sum.
23            ans += nums[i];
24        }
25      
26        // Return the sum of "good" numbers.
27        return ans;
28    }
29}
30

1class Solution {
2public:
3    int sumOfGoodNumbers(vector<int>& nums, int k) {
4        int sum = 0;              // Initialize sum to store the total of "good" numbers.
5        int size = nums.size();   // Get the size of the numbers array.
6
7        for (int i = 0; i < size; ++i) {  // Loop through each element in the array.
8            // Check condition for element not being "good" by looking backward.
9            if (i >= k && nums[i] <= nums[i - k]) {
10                continue;          // If condition met, skip and go to next element.
11            }
12            // Check condition for element not being "good" by looking forward.
13            if (i + k < size && nums[i] <= nums[i + k]) {
14                continue;          // If condition met, skip and go to next element.
15            }
16            sum += nums[i];        // Add the current "good" number to sum.
17        }
18      
19        return sum;               // Return the total sum of "good" numbers.
20    }
21};
22

1function sumOfGoodNumbers(nums: number[], k: number): number {
2    const n = nums.length;
3    let ans = 0;
4
5    // Iterate through each number in the array
6    for (let i = 0; i < n; ++i) {
7        // If the current number has a predecessor k steps back 
8        // and is not greater than that predecessor, skip it
9        if (i >= k && nums[i] <= nums[i - k]) {
10            continue;
11        }
12
13        // If the current number has a successor k steps forward 
14        // and is not greater than that successor, skip it
15        if (i + k < n && nums[i] <= nums[i + k]) {
16            continue;
17        }
18
19        // Add the current number to the sum as it qualifies as a 'good number'
20        ans += nums[i];
21    }
22
23    return ans;
24}
25

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the list nums. This is because the code iterates over each element in nums exactly once, performing constant-time operations for each element.

The space complexity of the code is O(1). This is due to the fact that the space used by the program does not increase with the size of the input list nums. The variables ans, i, and x are all used to store a constant amount of data regardless of the input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: