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

  • dehaka
     + 0 comments

    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;
}