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

Smallest Range II

Number: 946

Difficulty: Medium

Paid? No

Companies: Amazon, Adobe

Problem Description

Given an array of integers, nums, and an integer k, modify each element by either adding k or subtracting k. The goal is to minimize the difference (score) between the maximum and minimum values in the array after these modifications.

Key Insights

  • First, sort the array to easily compare adjacent numbers.
  • The initial answer is the difference between the maximum and minimum values.
  • By choosing a partition index, we can decide that all elements up to that index are increased by k and all elements after are decreased by k.
  • For each partition point, calculate the potential new minimum and maximum by considering the boundaries.
  • Iteratively update the answer with the minimum range encountered.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array.
Space Complexity: O(n) for storing the sorted array (O(1) extra space if sorting in place).

Solution

Sort the array to determine the natural order of the elements. The initial best answer is the difference between the largest and smallest values. Then, consider every possible partition, where indices up to i have k added and from i+1 have k subtracted. The new minimum is the lesser of the first element plus k and the (i+1)th element minus k. The new maximum is the greater of the last element minus k and the ith element plus k. Update the answer with the smallest difference found. This approach ensures that we're checking all potential configurations to minimize the overall range.

Code Solutions

def smallestRangeII(nums, k):
    # Sort the array to facilitate comparing adjacent elements.
    nums.sort()
    n = len(nums)
    # Initial answer is the difference between the largest and smallest.
    answer = nums[-1] - nums[0]
    
    # Try every partition where we switch from adding k to subtracting k.
    for i in range(n - 1):
        # After modification, the smallest value is the minimum of:
        # the first element increased by k or the (i+1)th element decreased by k.
        temp_low = min(nums[0] + k, nums[i + 1] - k)
        # Similarly, the largest value is the maximum of:
        # the (n-1)th element decreased by k or the ith element increased by k.
        temp_high = max(nums[-1] - k, nums[i] + k)
        answer = min(answer, temp_high - temp_low)
    
    return answer

# Example usage:
print(smallestRangeII([1, 3, 6], 3))  # Expected output: 3
← Back to All Questions