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 106 Discussions, By:

  • front_end_dev
     + 0 comments

    JS code template has naming issues, HackerRank have to check the description and the code

  • abhishek_pcs_201
     + 0 comments

    Get left limit and right limit of every number in the array. This will give temporary min-max for every window size. Calculate the index as per the formula index = right - left.

    Post this store the max of A[i] and res[index] into result[index]. Then, run a backward scan on result array to find min-max of left over window sizes.

    Important Note: Min-max of a window size N will always be less than or equal to the window size of N-1.

    static long[] riddle(long[] arr) {
    // complete this function
    int n= arr.Count();
    long[] res = new long[n];
    int[] left = new int[n];
    int[] right = new int[n];

    for(int i=0; i<n; i++){
        res[i] = 0;
    }

    Stack<int> st= new Stack<int>();

    for(int i=0; i<n; i++){
        while(st.Count>0 && arr[st.Peek()]>=arr[i])
            st.Pop();

        if(st.Count>0) left[i] = st.Peek()+1;
        else left[i]=0;

        st.Push(i);
    }

    Stack<int> st2= new Stack<int>();

    for(int i=n-1; i>=0; i--){
        while(st2.Count>0 && arr[st2.Peek()]>=arr[i])
            st2.Pop();

        if(st2.Count>0) right[i] = st2.Peek()-1;
        else right[i]=n-1;

        st2.Push(i);
    }

    for(int i=0; i<n; i++){
        int k = right[i]-left[i];
        res[k]=Math.Max(res[k], arr[i]);
    }

    for(int i=n-2; i>=0; i--){
        res[i]=Math.Max(res[i], res[i+1]);
    }

    return res;
}

  • gauravkumargk981
     + 0 comments
    void nextGreaterElement(vector<long> &arr, vector<long> &left, vector<long> &right) {
    stack<long> s;

    s.push(0);
    for(int i = 1; i < arr.size(); i++) {
        while(s.empty() == false && arr[s.top()] > arr[i] ) {
            right[s.top()] = i;
            s.pop();
        }
        
        s.push(i);
    }
    
    while(s.empty() == false) {
            right[s.top()] = arr.size();
            s.pop();
    }
    
    s.push(arr.size() - 1);
    for(int i = arr.size() - 2; i >= 0; i--) {
        while(s.empty() == false && arr[s.top()] > arr[i]) {
            left[s.top()] = i;
            s.pop();
        }
        
        s.push(i);
    }
    
    while(s.empty() == false) {
            left[s.top()] = -1;
            s.pop();
    }
}


// Complete the riddle function below.
vector<long> riddle(vector<long> arr) {
    // complete this function
    
    //implement next greater element algo
    vector<long> left(arr.size(), 0);
    vector<long> right(arr.size(), 0);
    vector<long> ans(arr.size(), 0);
    
    nextGreaterElement(arr, left, right);
    
    for(long i = 0; i < right.size(); i++) {
        long range = right[i] - left[i] - 1;
        ans[range - 1] = arr[i];
    }
    
    for(long i = ans.size() - 1; i >= 0 ;i--) {
        if(ans[i] == 0) {
            ans[i] = ans[i + 1];
        }
    } 

    return ans;
}

    can anyone help me with this code I can pass the 1st three cases but for the other cases getting wrong output.

  • alec_yenter
     + 0 comments
    def riddle(arr):
    # tracking index
    i = 0
    # stack for indices
    stack = []
    # results pre-filled with 0s
    result = [0]*len(arr)
    # iterate through arr (but don't stop until stack is empty)
    while i < len(arr) or stack:
        # if stack is empty
        # or current item (is in bounds of arr and) is greater than or equal to top of stack
        # then add current item to stack
        if not stack or (i < len(arr) and arr[stack[-1]] <= arr[i]):
            stack.append(i)
            i += 1
            continue
        
        # at this point, i is the right boundary for a localized minimum
        # so, we only need to find the left boundary
        
        # get localized minimum
        top = stack.pop()
        # calculate width between boundaries
        # this is i minus previous item in stack
        # (or the existing length so far if nothing left in stack)
        # (we subtract 1 for sake of 0-based indices)
        idx = (i-stack[-1]-1 if stack else i)-1
        # set the localized minimum to the calculated width
        # (but only if it is more than the existing minimum)
        result[idx] = max(result[idx], arr[top])
        
    # now that we have the results prefilled with max minimums
    # we just need to fill and adjust
    
    # iterate backwards through results (skipping last index)
    for i in range(len(result)-2,-1,-1):
        # if the window doesn't have a max
        # (this is b/c we have only filled those that a number is a minimum of)
        # or the max of the width is too small
        # (this can happen b/c we filled in every localized window found,
        #    but not necessarily the max)
        # then use the previous (i+1) max
        if result[i] == 0 or result[i+1] > result[i]:
            result[i] = result[i+1]
            
    return result

  • cschattisuresh
     + 1 comment

    if you are using go lang, then testcase2 may fail with runtime error as it can't able to read whole input

    you need to adjust the read buffer size in the main method like this

    reader := bufio.NewReaderSize(os.Stdin, MAX_INPUT_SIZE*64)

Load more conversations