Sherlock and MiniMax Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Sherlock and MiniMax
  5. Discussions

Sherlock and MiniMax

Sort by

recency

|

154 Discussions

|

  • shreyavishwalin1
     + 0 comments
    def sherlockAndMinimax(arr, p, q):
    arr.sort()
    n = len(arr)

    # Evaluate the endpoints p and q
    candidates = [p, q]

    # Evaluate midpoints between adjacent array elements
    for i in range(n - 1):
        mid = (arr[i] + arr[i + 1]) // 2
        if p <= mid <= q:
            candidates.append(mid)
        if p <= mid + 1 <= q:
            candidates.append(mid + 1)
    
    # Function to find the minimum distance to any array element
    def min_distance(M):
        return min(abs(M - x) for x in arr)
    
    # Evaluate each candidate and keep track of the best one
    best_M = None
    best_min_distance = -1

    for M in candidates:
        current_min_distance = min_distance(M)
        if (current_min_distance > best_min_distance) or (current_min_distance == best_min_distance and (best_M is None or M < best_M)):
            best_M = M
            best_min_distance = current_min_distance

    return best_M

  • kheengz
     + 0 comments
    function sherlockAndMinimax(arr, p, q) {
    // Write your code here
    let maxInd = p;
    let minimum = Number.MAX_SAFE_INTEGER;
    arr.sort((a, b) => a - b);
    
    for (const element of arr) {
        const absP = Math.abs(element - p);
        if (absP < minimum) {
            minimum = absP;
        }
    }
    let maximum = minimum;
    minimum = Number.MAX_SAFE_INTEGER;
    
    for (let i = 1; i <= arr.length; i++) {
        const mid = parseInt((arr[i] + arr[i - 1]) / 2, 10);
        if (p < mid && mid < q) {
            minimum = Math.min(mid - arr[i - 1], arr[i] - mid);
            if (minimum > maximum) {
                maximum = minimum;
                maxInd = mid;
            }
        }
    }
    
    minimum = Number.MAX_SAFE_INTEGER;
    for (const element of arr) {
        const absQ = Math.abs(element - q);
        if (absQ < minimum) {
            minimum = absQ;
        }
    }
    
    if (minimum > maximum) {
        maximum = minimum;
        maxInd = q;
    }

    return maxInd;
}

  • aadiupadhyay
     + 0 comments

    Python O(n) solution where n is size of array. 

    def sherlockAndMinimax(arr, p, q):
    arr.sort()
    diff = -float('inf')
    ans = 0 
    if p < arr[0]:
        diff = arr[0] - p 
        ans = p 
    n = len(arr)
    for i in range(1,n):
        x = min(q, (arr[i] + arr[i-1])//2 )
        x = max(p, x)
        dif1 = arr[i] - x 
        dif2 = x - arr[i-1]
        y = min(dif1, dif2)
        if y > diff :
            if dif2 == y :
                diff = dif2
                ans = x
            else :
                diff = dif1
                ans = x
    if arr[-1] < q : 
        x = q - arr[-1]
        if x > diff :
            ans = q
    return ans

  • john_v_little
     + 0 comments

    Hi, in Java, I always get: "Time limit exceeded Your code did not execute within the time limits. Please optimize your code."

    for test case 8, 9 and 10. If I run the test locally with the test data from 8, 9 and 10, it runs perfectly. I have done some optimisation (e.g. convert list to array), but cant see how to optimise further. Here is my code: public static int sherlockAndMinimax(List arr, int p, int q) { int M; int maxMin = Integer.MIN_VALUE; int maxMinPos = 0;

        int[] optArr = arr.parallelStream().mapToInt(Integer::intValue).toArray();

    int size = arr.size();

    for (M = p; M <= q; M++) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < size; i++) {
            int diff = Math.abs(optArr[i] - M);
            if (diff < min) {
                min = diff;
            }
        }
        if (min > maxMin) {
            maxMin = min;
            maxMinPos = M;
        }
    }
    return maxMinPos;
}

  • dehaka
     + 0 comments

    easy tedious question, O(n) where n is size of arr

    int sherlockAndMinimax(vector<int> arr, int p, int q) {
    pair<int, int> M = {p, 0};
    sort(arr.begin(), arr.end());
    int first = -1, caseB = -1;
    bool flag = false;
    for (int i=0; i < arr.size(); i++) {
        if (arr[i] >= p and arr[i] <= q) {
            first = i;
            flag = true;
            break;
        }
        if (i < arr.size()-1 and arr[i] < p and arr[i+1] > q){
            caseB = i;
            break;
        }
    }
    if(!flag) {
        if (q < arr[0]) return p;
        else if (p > arr.back()) return q;
        else {
            if (q <= (arr[caseB] + arr[caseB+1])/2) return q;
            else if (p >= ceil(arr[caseB] + arr[caseB+1]/2.0)) return p;
            else return (arr[caseB+1] + arr[caseB])/2;
        }
    }
    int last = first;
    int result = 0;
    while (last < arr.size()-1 and arr[last+1] <= q) last++;
    if (first == 0) M.second = arr[first] - p;
    else {
        if (p >= ceil(arr[first] + arr[first-1])/2.0) M.second = arr[first] - p;
        else M = {(arr[first] + arr[first-1])/2, (arr[first] - arr[first-1])/2};
    }
    for (int i=first; i < last; i++) {
        if (M.second < (arr[i+1] - arr[i])/2) M = {(arr[i+1] + arr[i])/2, (arr[i+1] - arr[i])/2};
    }
    if (last == arr.size()-1) {
        if (M.second < q - arr[last]) M = {q, q - arr[last]};
    }
    else {
        pair<int, int> temp;
        if (q <= (arr[last+1] + arr[last])/2) temp = {q, q - arr[last]};
        else temp = {(arr[last+1] + arr[last])/2, (arr[last+1] - arr[last])/2};
        if (M.second < temp.second) M = temp;
    }
    return M.first;
}