LeetCode — Smallest Range II

Problem Link: https://leetcode.com/problems/smallest-range-ii/

Problem Description: 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.

Sorting

Constraints:

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

Approach Used: Sorting, Arrays

Explanation: Since we have to find the minimum difference between the minimum and maximum element, we need to maximize the minimum element (or add k) and minimize the maximum element(or subtract k). The maximum and minimum can check after adding k or -k to them so we cannot simply take the largest and smallest element from the array and calculate the answer (although that’ll be the base case). We will have to compare all the adjacent pairs.

Code: (Java)

public int smallestRangeII(int[] A, int K) {
 //sort the array
 Arrays.sort(A);
 //maximum element of array
 int max = A[A.length-1];
 //minimum element of array
 int min = A[0];
 
 //intial value of result (always bigger than other answers)
 int result = A[A.length-1]-A[0];
 
 //base case will be max-min-2k (right-left)
 int right = max-K;
 int left = min+K;
 
 for(int i=0; i<A.length-1; i++){
 //find maximum element after adding k till ith index
 max = Math.max(right, A[i]+K);
 //find minimum element after substracting k till ith index
 min = Math.min(left, A[i+1]-K);
 //result till ith index will be minimum of existing result and new difference calculated
 result = Math.min(result, max-min);
 }
 return result;
 }

Complexity:

Space Complexity: O(1). Constant space used for the variable result.

Time Complexity: O(n*logn). “nlogn ” time required to sort the array in the most efficient way. Linear time to traverse the array and find the pair.