Scale Engineer

Sum of Good Numbers

Easy
#3068Time: 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.
Data structures
Array

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem