An interesting Coding Problem : Smallest Range II

Hi there!

Firstly the link to the problem I want to discuss is :

Smallest Range II - LeetCode

I suggest you to give it a try and comeback.

problem statement :

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.

Approach:

• Firstly if A[i]<A[j] then there is no point in considering A[i]-K and A[j]+K since that would obviously increase the difference between them but we want the minimum difference.
• So Lets sort the array first
• Now,for each i , consider A as two segments {A[0]+k,…..,A[i]+K} and {A[i+1]-K,…..,A[n-1]-K}
• In the first segment, minimum value is A[0]+K and maximum value is A[i]+K. Similarly in the second segment, minimum value is A[i+1]-K and maximum value is A[n-1]-K
• So, for a particular i , maximum value possible is max(A[i]+K,A[n-1]-K) and minimum value possible is min(A[0]+K,A[i+1]-K)
• The final answer is minimum of all possible answers.

Sample Code in Java:

class Solution {
    public int smallestRangeII(int[] A, int K) {
        int n=A.length;
        Arrays.sort(A);
        int ans=A[n-1]-A[0];
        for(int i=0;i<n-1;i++){
            int small=Math.min(A[0]+K,A[i+1]-K);
            int big=Math.max(A[n-1]-K,A[i]+K);
            ans=Math.min(ans,big-small);
        }
        return ans;
    }
}

Time Complexity : O(nlogn) because of sorting