algoadvance

Given an array A of integers, consider the difference between the largest and smallest value of A. We define the transformation A[i] = A[i] + K or A[i] = A[i] - K for all elements in the array. Return the smallest possible difference between the largest and smallest value of A after applying this transformation.

Example 1:

Input: A = [1], K = 0
Output: 0

Example 2:

Input: A = [0,10], K = 2
Output: 6

Example 3:

Input: A = [1,3,6], K = 3
Output: 3

Note:

  1. 1 <= A.length <= 10000
  2. 0 <= A[i] <= 10000
  3. 0 <= K <= 10000

Clarifying Questions

  1. Should the transformation be applied exactly once to each element of the array?
    • Yes, each element should be either increased or decreased by K exactly once.
  2. What is the expected type of input and output?
    • The input is an array of integers A and an integer K, and the output is an integer representing the smallest possible difference.
  3. Do we need to maintain the original sequence of A?
    • No, the sequence does not matter; we only need to find the smallest possible range.

Strategy

  1. First, sort the array A. This helps in minimizing the difference range calculation.
  2. Transform the smallest element with +K and the largest element with -K. This considers the extreme transformations.
  3. Note that the overall range difference might include intermediate values, so we compute difference ranges between the current smallest (min(A[i] - K, A[0] + K)) and largest (max(A[i - 1] + K, A[-1] - K)).
  4. Iterate through possible division points in the sorted array to calculate the minimal range.

Code

def smallestRangeII(A, K):
    A.sort()
    n = len(A)
    result = A[-1] - A[0]

    for i in range(n - 1):
        high = max(A[-1] - K, A[i] + K)
        low = min(A[0] + K, A[i + 1] - K)
        result = min(result, high - low)
        
    return result

# Example usage
A1 = [1]
K1 = 0
print(smallestRangeII(A1, K1))  # Output: 0

A2 = [0, 10]
K2 = 2
print(smallestRangeII(A2, K2))  # Output: 6

A3 = [1, 3, 6]
K3 = 3
print(smallestRangeII(A3, K3))  # Output: 3

Time Complexity

Therefore, the overall time complexity is (O(n \log n)).

The space complexity is (O(1)) as we only use a fixed amount of extra space.

Try our interview co-pilot at AlgoAdvance.com