We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Good Numbers

Number: 3723

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an integer array nums and an integer k, an element nums[i] is defined as good if it is strictly greater than the element at index i - k (if it exists) and strictly greater than the element at index i + k (if it exists). Even if one or both of these indices are out of bounds, the element can still be considered good. The task is to return the sum of all good numbers in the array.

Key Insights

  • For each element at index i, check its neighbors at indices i-k and i+k if they exist.
  • An element is good if it is strictly greater than any available neighbor.
  • Iterate through the array only once, making the solution efficient.
  • Be cautious with boundary conditions when one or both of the neighboring indices fall outside the array.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array because we iterate through it once. Space Complexity: O(1) constant extra space.

Solution

The solution involves a simple linear scan of the array. For each element, we perform the following checks:

  1. If the index i-k exists, ensure that nums[i] is strictly greater than nums[i-k].
  2. If the index i+k exists, ensure that nums[i] is strictly greater than nums[i+k].
  3. If one of the checks does not apply because an index is out of bounds, that check is ignored. If an element passes the above condition(s), it is added to a running total sum. Using this approach ensures all edge cases (boundary indices) are handled cleanly.

We use a for loop to iterate through the elements. The algorithm uses simple conditional checks for neighboring indices, keeping our space usage constant and time linear.

Code Solutions

# Function to compute the sum of good numbers
def sum_of_good_numbers(nums, k):
    total_sum = 0  # Initialize the total sum of good numbers
    n = len(nums)  # Get the length of the array
    
    # Loop through each element in nums
    for i in range(n):
        is_good = True  # Assume nums[i] is good initially
        
        # Check left neighbor at index i-k if it exists
        if i - k >= 0 and nums[i] <= nums[i - k]:
            is_good = False  # Not strictly greater than left neighbor
        
        # Check right neighbor at index i+k if it exists
        if i + k < n and nums[i] <= nums[i + k]:
            is_good = False  # Not strictly greater than right neighbor
        
        # If the element is good, add it to total_sum
        if is_good:
            total_sum += nums[i]
    
    return total_sum

# Example usage:
print(sum_of_good_numbers([1,3,2,1,5,4], 2))  # Expected output: 12
← Back to All Questions