Sum of Good Numbers

EASY

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.

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

Checkout 2 different approaches to solve Sum of Good Numbers. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

1. Initialize a variable sum to 0.
1. Loop through the array nums from i = 0 to nums.length - 1.
1. For each element nums[i], assume it is a good number by setting a flag, e.g., boolean isGood = true;.
1. 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.
1. 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.
1. If the isGood flag remains true after both checks, add nums[i] to the sum.
1. After the loop finishes, return the total sum.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Sum of Good Numbers. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Sum of Good Numbers

Data Structures:

Array