Minimize the maximum difference

I’m trying to solve this Problem from GFG with following approach:

class Solution:
    def getMinDiff(self, arr, n, k):
        # code here
        arr.sort()
        min_diff = arr[-1] - arr[0]
        if min_diff <= k:
            return min_diff
        
        min_ele = arr[0] + k
        max_ele = arr[-1] - k
        if min_ele > max_ele:
            min_ele, max_ele = max_ele, min_ele
            
        for i in range(1, n-1):
            curr_min = arr[i] - k
            curr_max = arr[i] + k
            
            if curr_min >= min_ele or curr_max <= max_ele:
                continue
            
            if max_ele - curr_min <= curr_max - min_ele:
                min_ele = curr_min
            else:
                max_ele = curr_max
                
        return min(min_diff, max_ele - min_ele)


if __name__ == '__main__':
    tc = int(input())
    while tc > 0:
        k = int(input())
        n = int(input())
        arr = list(map(int, input().strip().split()))
        ob = Solution()
        ans = ob.getMinDiff(arr, n, k)
        print(ans)
        tc -= 1

But i’m unable to pass the testcases:

Input:
4
10
6 1 9 1 1 7 9 5 2 10

Its Correct output is:
5

And my Code's output is:
6

I’m unable to figure out fault in my logic or code. Could some suggest corrections or better approach?

Answer

I’m unable to figure out fault in my logic or code.

As per your current logic, you decide to add or subtract k just based on the current element. But it might not yield the min diff overall. For example, for 5 you decided to add k and it resulted in the range (5,11) for the whole set. Rather if you have subtracted it would have yielded (1,6).

---

Could some suggest corrections or better approach?

Approach:

• Sort the array
• Lets handle the trivial case, if k > (max - min) then directly return max - min. Since adding k to min and subtracting k from max will yield a larger difference. (To be precise, 2 * k + (max - min))
• In all other cases, we will add k to min element and subtract k from max element. There should exist an index in the array, where we switch from adding k to subtracting k. The below diagram shows the switch index:

(Note: In the diagram, Bcan be less than D and also A can be greater than C)

• Now we iterate over the array and at each index, if it was the switch index we determine the range.
  • From the diagram, we can calculate the range as below
    • if A < C then the range will start with A or else with C
    • Similarly if B > D then the range will end with B or else with D
• The min range across all index gives the result

---

Updated Code:

def getMinDiff(self, arr, n, k):
    # code here
    arr.sort()
    min_diff = arr[-1] - arr[0]
    if min_diff <= k:
        return min_diff
    
    for i in range(0, n-1):
        if arr[i + 1] < k :
            continue
        start = min(arr[0] + k, arr[i + 1] - k)
        end = max(arr[-1] - k, arr[i] + k)
        min_diff = min(min_diff, end - start)
            
    return min_diff

Explanation:

• In the for loop, we determine the switch index range for each element as follows
  • Start: From the diagram minimum of A and C. Here A is arr[0] + k and C will be next element - k i.e,. arr[ i + 1 ] - k
  • End: Maximum of B and D. B is current element + k, i.e., arr[i] + k and D will be arr[-1] - k