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.

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

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
}

Python solution with a stack. You need to split solution in 2 parts:

1. Go through the array and add to stack till the next number is smaller than the last value added to stack. When it happens you pop from the stack checking if value is higher than value in max windows array.

2. You end up with array with maximum windows for some window lengths. You have to populate the missing values with values from the right using a logic that window length for bigger window is also at least maximum for a smaller window.

def riddle(arr):
    max_win = [0 for i in range(len(arr))]
    arr = arr.copy() + [-1]
    stack = []
    for i in range(len(arr)):
        prev_i = i    
        while len(stack) > 0 and stack[-1][1] >= arr[i]:
            prev_i, value = stack.pop()
            window = i - prev_i - 1
            max_win[window] = max(max_win[window], value)
        stack.append((prev_i, arr[i]))
    for n in range(len(max_win)-2,0,-1):
        max_win[n] = max(max_win[n], max_win[n+1])
    return max_win

`

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