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. Min Max Riddle
  2. Discussions

Min Max Riddle

Sort by

recency

|

112 Discussions

|

  • rajivaiyer
     + 0 comments

    My Java 8 code, passing all test-cases, for a Max Score of 60.

    (imports & main not provided. That should be available from the coding window)

    // All HackerRank test-cases pass, for Max Score of 60
//      Time-Complexity: O(n) | Space-Complexity: O(n)

// NOTE: "debugPrintArr" only given for Diagnostic / Debug purposes.
//       Uncommenting that results in slow-down, hence 1 TC fails with TLE.


public class Solution {

    // Only given for Diagnostic / Debug purposes
    // static void debugPrintArr(int[] arr, String arrName) {
    //     System.err.println("Arr '" + arrName + "' BGN -->");
    //     System.err.print(">");
    //     for (int i = 0 ; i < arr.length ; i++) {
    //         System.err.print(arr[i]);
    //         if (i != (arr.length - 1)) {
    //             System.err.print(" ");
    //         }
    //     }
    //     System.err.print("<"); System.err.println("");
    //     System.err.println("<-- Arr '" + arrName + "' END");
    //     System.err.println("");
    // }

    // Only given for Diagnostic / Debug purposes
    // static void debugPrintArr(long[] arr, String arrName) {
    //     System.err.println("Arr '" + arrName + "' BGN -->");
    //     System.err.print(">");
    //     for (int i = 0 ; i < arr.length ; i++) {
    //         System.err.print(arr[i]);
    //         if (i != (arr.length - 1)) {
    //             System.err.print(" ");
    //         }
    //     }
    //     System.err.print("<"); System.err.println("");
    //     System.err.println("<-- Arr '" + arrName + "' END");
    //     System.err.println("");
    // }

    // Complete the riddle function below.
    static long[] riddle(long[] arr) {

        // complete this function
        int n = arr.length;

        // The Stack stores Indices of "arr". As we iterate through the Array,
        // either forwards or backwards, we keep accumulating indices encountered.
        // But before this, if the Stack isn't empty, and arr[stack.peek()] >= arr[i])
        // Then we Pop from the Stack. This way, we maintain relevant indices in the Stack.
        // So that we can compute the Next Smaller Element in either Direction.
        Stack<Integer> stack = new Stack<>();

        int[] prevSmallerToLeft = new int[n];
        int[] nextSmallerToRight = new int[n];

        // Compute PREVIOUS smaller on LEFT, with help from Stack
        for (int i = 0 ; i < n ; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            prevSmallerToLeft[i] = ( stack.isEmpty() ? -1 : stack.peek() );
            stack.push(i);
        }
        //debugPrintArr(prevSmallerToLeft, "prevSmallerToLeft");

        // Clear Stack
        stack.clear();

        // Compute NEXT smaller on RIGHT, with help from Stack
        for (int i = (n - 1) ; i >= 0 ; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            nextSmallerToRight[i] = ( stack.isEmpty() ? n : stack.peek() );
            stack.push(i);
        }
        //debugPrintArr(nextSmallerToRight, "nextSmallerToRight");

        // ans[len]: max of minimums for window length = len
        long[] ans = new long[n + 1];
        Arrays.fill(ans, 0);

        // Iterating through Left/Right arrays, taking difference (len)
        // And finding the Max of Minimums, b/w "ans[len]" & "arr[i]"
        for (int i = 0 ; i < n ; i++) {
            int len = nextSmallerToRight[i] - prevSmallerToLeft[i] - 1;
            ans[len] = Math.max(ans[len], arr[i]);
        }
        //debugPrintArr(ans, "ans (initial)");

        // Fill remaining sizes
        for (int size = (n - 1) ; size >= 1 ; size--) {
            ans[size] = Math.max(ans[size], ans[size + 1]);
        }
        //debugPrintArr(ans, "ans (final)");

        // Prepare result for sizes 1 through n
        long[] result = new long[n];
        for (int k = 1; k <= n; k++) {
            result[k - 1] = ans[k];
        }
        //debugPrintArr(result, "result");

        return result;

    }
}

  • jose_lopezrs
     + 0 comments

    Solution in javascript, it passes all test cases but 1 and it fails because timeout so i'd say is almost okey, althought im not using stacks or queues:

    function riddle(arr) {
    // solve here
    let result = []
    let tempDict = new Map([[0, Number.MAX_SAFE_INTEGER]]);
    
    let minimum = 0;
    for(let i=0; i<arr.length; i++){
        let group= 1;
  
        for(let j=i; j<arr.length; j++){
              
            let min=Math.min(tempDict.get(group-1), arr[j]);
            tempDict.set(group, min )
            result[group-1] = result[group-1]!= undefined? Math.max(result[group-1], min) : min
            group++;
        }
   
    }
    
    
    return result;
}

  • alexsky1330
     + 0 comments

    Chemistry riddles enhance problem solving skills by challenging individuals to think critically, recall specific details, and connect abstract ideas, often requiring them to recognize patterns in chemical behavior.

  • dehaka
     + 1 comment

    O(n) using the previous and next smaller element algos and dynamic programming, pass all test.

    if u try to use sliding window and iterate over each length, it's O(n^2) and times out. u need to use dynamic programming concepts to achieve O(n).

    the max_element inside the last for loop may make the for loop look like O(n^2), but maximalWindow has a total of n element across all maximalWindow[size], so the for loop has O(n) operations in total

    void previousSmaller(const vector<int>& V, vector<int>& prev) {
    prev.resize(V.size(), -1);
    stack<int> S;
    S.push(0);
    for (int i = 1; i < V.size(); ++i) {
        while (!S.empty() and V[i] <= V[S.top()]) S.pop();
        if (!S.empty()) prev[i] = S.top();
        S.push(i);
    }
}

void nextSmaller(const vector<int>& V, vector<int>& next) {
    next.resize(V.size(), V.size());
    stack<int> S;
    S.push(V.size() - 1);
    for (int i = V.size() - 2; i >= 0; --i) {
        while (!S.empty() and V[i] <= V[S.top()]) S.pop();
        if (!S.empty()) next[i] = S.top();
        S.push(i);
    }
}

vector<int> riddle(int n, const vector<int>& arr) {
    vector<int> prev, next, answers(n+1);
    vector<vector<int>> maximalWindow(n+1);
    previousSmaller(arr, prev);
    nextSmaller(arr, next);
    for (int i = 0; i < arr.size(); ++i) maximalWindow[next[i]-prev[i]-1].push_back(arr[i]);
    answers[n] = maximalWindow[n][0];
    for (int size = n - 1; size >= 1; --size) {
        int k = 0;
        if (!maximalWindow[size].empty()) k = *max_element(maximalWindow[size].begin(), maximalWindow[size].end());
        answers[size] = max(answers[size+1], k);
    }
    return answers;
}

  • uzma_abidi
     + 0 comments

    in swift

    func riddle(arr: [Int]) -> [Int] {
    let n = arr.count
    var maxWin = [Int](repeating: 0, count: n)
    var stack = [(index: Int, value: Int)]()
    var leftBoundaries = [Int](repeating: 0, count: n)
    var rightBoundaries = [Int](repeating: n, count: n)

     for i in 0..<n {
         while !stack.isEmpty && stack.last!.value >= arr[i] {
                stack.popLast()
            }
    leftBoundaries[i] = stack.isEmpty ? 0 : stack.last!.index + 1
    stack.append((index: i, value: arr[i]))
        }

stack.removeAll()

for i in stride(from: n - 1, through: 0, by: -1) {
        while !stack.isEmpty && stack.last!.value >= arr[i] {
            stack.popLast()
  }
  rightBoundaries[i] = stack.isEmpty ? n : stack.last!.index
  stack.append((index: i, value: arr[i]))
}

for i in 0..<n {
        let windowSize = rightBoundaries[i] - leftBoundaries[i]
  maxWin[windowSize - 1] = max(maxWin[windowSize - 1], arr[i])
}

for i in stride(from: n - 2, through: 0, by: -1) {
        maxWin[i] = max(maxWin[i], maxWin[i + 1])
}

        return maxWin
}