Last Updated: 10 Apr, 2021
Smallest Range II
Easy
Asked in company
You are given an array A of integers and an integer K, where, for each integer A[i] we need to choose either x = -K or x = K, and add x to A[i] only once. After this process, we have some array B. Your task is to find the smallest possible difference between the maximum value of B and the minimum value of B.
For Example :
Input: A = [1,3,6], K = 3
Output: 3
Explanation: B = [4,6,3]
Input Format :
The first line of input contains a single integer ‘T’ denoting the number of test cases given.
The first line of each test case input contains two space-separated integers ‘N’ and ‘K’. Where ‘N’ denotes the number of elements in the array while ‘K’ is the value to be added or subtracted from each A[i] so that the so formed list (array) ‘B’ has the smallest possible difference between its maximum and minimum element.
The next line of input for each test case contains ‘N’ space-separated integers (elements of the list/array).
Output Format :
For every test case, print the smallest possible difference between the maximum value of B and the minimum value of B.
Print the output of each test case in a separate line.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 100
1 <= A.length <= 5000
0 <= A[i] <= 10000
0 <= K <= 10000
Time Limit: 1 sec
Approaches
Using the intutuin that if A[i] < A[j], we don't need to consider when A[i] goes down while A[j] goes up. Since, the interval (A[i] + K, A[j] - K) would already always be a subset of (A[i] - K, A[j] + K) (here, (a, b) for a > b denotes (b, a) instead.)
That means that it is never worse to choose (up, down) instead of (down, up).
Now, for a sorted list (array) A, assume that element A[i] is the largest i that goes up. Then, A[0] + K, A[i] + K, A[i+1] - K, A[A.length - 1] - K are the only relevant values for calculating the answer: every other value is between one of these extremal values.
Algorithm
- Start with sorting the given list (array) ‘A’ of elements in ascending order which would now place the minimum value at the beginning while the maximum value would be at the end of the list (array).
- After that now, initialize the min and max values from the list (array) in separate variables.
- Also, initialize the required result in ‘ans’ by finding the difference between the present min ‘mn’ and max ‘mx’.
- Keep traversing the elements in the list (array) ‘A’ and compute the following for i'th element from 0 ... A.length - 1.
- Initialize the ‘a’ and ‘b’ with A[i] and A[i+1].
- Now keep calculating whether:
- ( max(mx - K, a + K) - min(mn + K, b - K) < ‘ans’
- if yes, update ‘ans’ with the computed value.
- Now keep calculating whether:
- Initialize the ‘a’ and ‘b’ with A[i] and A[i+1].
- Once we have iterated for all the elements present in the list (array) we would have the required smallest difference in ‘ans’
- We finally return ‘ans’.