Domain 1EasyCORE

Smallest Range I

The problem asks us to find the smallest possible difference between the maximum value and the minimum value of an array `B`, where `B` is derived from array `A` by adding any integer `x` within the range `-K <= x <= K` to each element of `A`. The goal is to minimize the range `[max(B) - min(B)]`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

908. Smallest Range I

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 66.4%


Problem Breakdown

The problem asks us to find the smallest possible difference between the maximum value and the minimum value of an array B, where B is derived from array A by adding any integer x within the range -K <= x <= K to each element of A. The goal is to minimize the range [max(B) - min(B)].

Inputs:

  • An array A of integers.
  • An integer K representing the maximum absolute value that can be added to any element in A.

Outputs:

  • An integer representing the smallest possible difference between the maximum and minimum values of the transformed array B.

Implicit Constraints or Edge Cases:

  • If A has only one element, the range is always 0.
  • If all elements in A are the same, the range remains 0 regardless of K.
  • The value of K can be 0, which means no changes can be made to the array.

Intuition

The brute-force approach would involve generating all possible arrays B by adding every possible value of x within the range -K <= x <= K to each element in A, and then calculating the range for each. This approach is computationally expensive, with a time complexity of O(n * (2K + 1)), where n is the length of the array.

A better approach involves recognizing that the smallest possible difference between the maximum and minimum values of B can be achieved by considering the original range of A. If we add K to the minimum value and subtract K from the maximum value, we get a new range. The key insight is that if this adjusted range is non-negative, it represents the smallest possible difference; otherwise, the smallest possible difference is 0.

Approach

  1. Identify the Minimum and Maximum Values:

    • Traverse the array to find the minimum (min_val) and maximum (max_val) values.
  2. Calculate the Adjusted Range:

    • Compute the adjusted range as max(max_val - K, min_val + K).
  3. Determine the Result:

    • If the adjusted range is greater than or equal to 0, return it as the result.
    • Otherwise, return 0, indicating that the entire array can be made uniform by adding/subtracting K.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. This is because we only need a single pass to find the minimum and maximum values.
  • Space Complexity: O(1), as we are using a constant amount of extra space.

Solution

def smallestRangeI(A, K):
    min_val = min(A)
    max_val = max(A)
    
    # Calculate the adjusted range
    adjusted_range = max(max_val - K, min_val + K) - (min_val + K)
    
    # Return the result based on the adjusted range
    return max(0, adjusted_range)

# Example usage:
print(smallestRangeI([1], 0))        # Output: 0
print(smallestRangeI([0, 10], 2))   # Output: 6
print(smallestRangeI([1, 3, 6], 3))  # Output: 0

Edge Cases Handled

  • Single Element Array: If A has only one element, the range is always 0.
  • All Elements Identical: If all elements in A are the same, the range remains 0 regardless of K.
  • Zero K Value: If K is 0, no changes can be made to the array, and the range remains unchanged.