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,3,6], K = 3
Output: 3

Approach

Java

import java.util.Arrays;

public class SmallestRangeII {
    public static void main(String[] args) {
        int[] A = { 1, 3, 6 };
        int K = 3;
        System.out.println(smallestRangeII(A, K));
    }

    static public int smallestRangeII(int[] A, int K) {
        if (A.length <= 1)
            return 0;
        Arrays.sort(A);
        int ans = A[A.length - 1] - A[0];
        int r = A[A.length - 1] - K;
        int l = A[0] + K;
        for (int i = 0; i < A.length - 1; i++) {
            int max = r, min = l;

            if (A[i] + K > r)
                max = A[i] + K;

            if (A[i + 1] - K < l)
                min = A[i + 1] - K;

            if (ans > (max - min))
                ans = max - min;
        }
        return ans;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int smallestRangeII(vector<int> &A, int K)
{
    multiset<int> st;
    int n = A.size();
    sort(A.begin(), A.end());
    if (K == 0)
        return A[n - 1] - A[0];
    if (n == 1)
        return 0;
    int ans = A[n - 1] - A[0];
    int max1 = A[n - 1];
    for (int i = 0; i < n; i++)
        st.insert(A[i]);

    for (int i = 0; i < n; i++)
    {
        if (st.find(A[i]) != st.end())
            st.erase(st.find(A[i]));
        A[i] = A[i] + 2 * K;
        st.insert(A[i]);
        auto it = st.begin();
        max1 = max(max1, A[i]);
        int min1 = *it;
        ans = min(ans, max1 - min1);
    }
    return ans;
}

int main()
{
    vector<int> A = {1, 3, 6};
    int K = 3;
    cout << smallestRangeII(A, K);
    return 0;
}