Minimize the maximum difference

Question

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 1

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