Smallest Range II

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
Snapdeal Ltd.

Problem statement

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]
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
1 0
1
2 2
0 10
Sample Output 1 :
0
6
Explanation Of Sample Input 1 :
For the first test case, the given value of  N = 1, while K = 0, therefore the list (array) B formed so as to result in the smallest difference between the minimum and maximum element is  B = [1]. Which would give us output as 0.

While, For the next test case, the given value of  N = 2 with K = 2, which would give us B = [2,8] having the smallest difference between the minimum element i.e. 2 and the maximum element i.e. 8 would give us 6.
Sample Input 2 :
2
3 3
1 3 6
4 2
6 7 1 3
Sample Output 2 :
3
2
Hint

Try and see if you could for smaller A[i], choose to increase their value ("go up"), and for bigger A[i], decrease their value ("go down").

Approaches (1)
Using Sorting

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.
  • 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’.
Time Complexity

O(N * log(N)), where ‘N’ is the length of the ‘A’.
 

Since we are iterating over all the elements given in the list (array) ‘A’ which is an O(N) operation but before that also we are performing a sorting on the list (array), therefore, the complexity here grows by O(N * log(N)).

Space Complexity

O(N) or O(log(N)), where ‘N’ is the length of the ‘A’.

 

Here, The space complexity of the sorting algorithm depends on the implementation of each programming language.

For instance, the list.sort() function in Python is implemented with the Timsort algorithm whose space complexity is O(N).

In Java, the Arrays.sort() is implemented as a variant of quicksort algorithm whose space complexity is O(logN).

Code Solution
(100% EXP penalty)
Smallest Range II
Full screen
Console