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
Aof integers. - An integer
Krepresenting the maximum absolute value that can be added to any element inA.
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
Ahas only one element, the range is always 0. - If all elements in
Aare the same, the range remains 0 regardless ofK. - The value of
Kcan 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
-
Identify the Minimum and Maximum Values:
- Traverse the array to find the minimum (
min_val) and maximum (max_val) values.
- Traverse the array to find the minimum (
-
Calculate the Adjusted Range:
- Compute the adjusted range as
max(max_val - K, min_val + K).
- Compute the adjusted range as
-
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
Ahas only one element, the range is always 0. - All Elements Identical: If all elements in
Aare the same, the range remains 0 regardless ofK. - Zero K Value: If
Kis 0, no changes can be made to the array, and the range remains unchanged.