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?
Advertisement
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 returnmax - 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 subtractk
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, B
can 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 withA
or else withC
- Similarly if
B > D
then the range will end withB
or else withD
- 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
andC
. HereA
isarr[0] + k
andC
will benext element - k
i.e,.arr[ i + 1 ] - k
- End: Maximum of
B
andD
.B
iscurrent element + k
, i.e.,arr[i] + k
andD
will bearr[-1] - k
- Start: From the diagram minimum of