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?

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`

- if

- From the diagram, we can calculate the range as below
- 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`

- Start: From the diagram minimum of

## Recent Comments