gardusig / problem-solving

Solutions for programming problems

problem-solving

Solutions for programming problems

problem-solving's Issues

Implement solution for leetcode problem

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/description/

Implement my own solution to interview problem

Problem: https://github.com/gardusig/road2senior/tree/main/solutions/real-questions/count_stock_intervals

Reference:

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> R2;
vector<long long> memo;
long long dp(int i){
    if(i == n)
        return 0;
    long long& ans = memo[i];
    if(ans != -1)
        return ans;
    return ans = dp(R2[i]) + 1;
}

long long solve(vector<int> arr){
    // Para cada i, encontrar o primeiro j > i tal que a[j] > a[i]
    n = arr.size();
    stack<int> st;
    vector<int> R(n);
    for(int i = n - 1; i >= 0; i--){
        while(!st.empty() && arr[st.top()] <= arr[i])
            st.pop();
        if(st.empty())
            R[i] = n;
        else
            R[i] = st.top();
        st.push(i);
    }
    
    long long ans = 0;
    for(int i = 0; i < n; i++)
        ans += R[i] - i;

    // segundo caso
    R2 = vector<int>(n);
    while(!st.empty())
        st.pop();

    for(int i = n - 1; i >= 0; i--){
        while(!st.empty() && arr[st.top()] < arr[i])
            st.pop();
        if(st.empty())
            R2[i] = n;
        else
            R2[i] = st.top();
        st.push(i);
    }

    memo = vector<long long>(n, -1);
    for(int i = 0; i < n; i++)
        ans += dp(R[i]);

    return ans;
}

long long solve_brute(vector<int> arr){
    long long ans = 0;
    int n = arr.size();
    for(int i = 0; i < n; i++)
        for(int j = i; j < n; j++){
            int greater = arr[i];
            for(int k = i + 1; k <= j; k++)
                greater = max(greater, arr[k]);
            if(greater == arr[i] || greater == arr[j])
                ans++;
        }
    
    return ans;
}

int main(){
    vector<int> arr{1, 2, 1, 2};
    assert(solve(arr) == solve_brute(arr));

    arr = vector<int>{1, 3, 2};
    assert(solve(arr) == solve_brute(arr));

    arr = vector<int>{1, 2, 3, 4, (int)1e9, 42, 69, 0, -4, 23, 0, 22, (int)-1e8};
    assert(solve(arr) == solve_brute(arr));

    return 0;
}