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 I

Number: 944

Difficulty: Easy

Paid? No

Companies: Bloomberg, Adobe

Problem Description

Given an array of integers and an integer k, you are allowed to add or subtract any value from -k to k to each element (at most once per element). The goal is to minimize the score of the modified array, where the score is defined as the difference between the maximum and minimum elements.

Key Insights

  • Every element can be either increased by k or decreased by k.
  • The best strategy to minimize the range is to increase the smaller elements and decrease the larger elements.
  • This effectively means the new minimum becomes (min(nums) + k) and the new maximum becomes (max(nums) - k).
  • The final score is max(0, (max(nums) - k) - (min(nums) + k)) which simplifies to max(0, max(nums) - min(nums) - 2*k).

Space and Time Complexity

Time Complexity: O(n) - where n is the number of elements in the input array (to find min and max). Space Complexity: O(1) - constant extra space is used.

Solution

The solution uses a straightforward mathematical insight. First, we compute the minimum and maximum values in the array. Then, by considering the effect of adding and subtracting k, we calculate the new range as max(nums) - min(nums) - 2*k. Since the range cannot be negative, we return the maximum of 0 and this computed value. This approach uses simple arithmetic operations and scanning of the array without any additional data structures.

Code Solutions

# Python solution with detailed comments

def smallestRangeI(nums, k):
    # Find the minimum and maximum numbers in the list
    min_num = min(nums)
    max_num = max(nums)
    # Calculate the difference after decreasing max and increasing min
    modified_range = max_num - min_num - 2 * k
    # The score cannot be negative, so return the maximum of 0 and modified_range
    return max(modified_range, 0)

# Example usage
if __name__ == "__main__":
    print(smallestRangeI([1,3,6], 3))  # Expected output: 0
← Back to All Questions