Smallest Range II
Given an array A of integers, 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.
Return the smallest possible difference between the maximum value
of B and the minimum value of B.
Example 1:
Input: A = [1], K = 0 Output: 0 Explanation: B = [1]
Example 2:
Input: A = [0,10], K = 2 Output: 6 Explanation: B = [2,8]
Example 3:
Input: A = [1,3,6], K = 3 Output: 3 Explanation: B = [4,6,3]
Note:
-
1 <= A.length <= 10000 -
0 <= A[i] <= 10000 -
0 <= K <= 10000
Solution:
class Solution {
public int smallestRangeII(int[] A, int K) {
int i, min=0, max=0, min1, min2, max1, max2,
length = A.length, diff=0;
Arrays.sort(A);
diff = A[length-1]-A[0];
int result = Integer.MAX_VALUE;
min1 = A[0]+K;
max1 = A[length-1]-K;
for(i=1;i<length;i++){
min2 = A[i]-K;
max2 = A[i-1]+K;
min = Math.min(min1, min2);
max = Math.max(max1, max2);
result = Math.min(result,
max-min);
}
return Math.min(diff, result);
}
}
1) Initially sort the array, so that we can find one of the best
difference between min value and max value in the given
array.(i.e., diff variable in above code)
2) min1 is a variable which holds smallest value from a given
array and also along with the addition of K.
3) max1 is a variable which holds largest value from a given
array and also along with the subtraction of K.
4) min2 and max2 variables change accordingly based on
iteration. min2 checks min value for
current i'th position value. max2 checks max value for
previous i'th position value. So, for each value in a array we check
for both +K and -K value.
5) Find min value from min1 and min2
6) Find max value from max1 and max2.
7) Find min from result and max,min difference and store it in
result.
8) Finally, return min among result and diff.
Related Posts:
Like us? Please do share with your friends ..!!
Follow us to receive updates instantly.
If you have any feedback/suggestions, leave it in a comment section or contact us through our contact page which
will be helpful for us to improve.
Comments
Post a Comment