'Number of SubArrays' Techniques

Md. Zarif Ul Alam

2020-06-08

Competitive Programming

Algo, DS, Software & What Not!

Problem Types

You are told to compute number of SubArrays with certain property .

Approach 1

Scan line from left to right .
For each right end (r) , calculate how many SubArrays starting with some l such that l<r . Add this count of l

Approach 2

Fix Border [l,r] with the given candidate property
For each border add border length to the SubArray

Example 1

Calculate the number of SubArrays such that Sum(l,r) = k

Solution Sketch

1
2
3

    Sum(l,r) = k
=>  Prefix(r) - Prefix(l-1) = k
=>  Prefix(l-1) + k = Prefix(r)

Code


int solve()
{
    int n,k;
    cin>>n>>k;

    vector<int>v(n+1),p(n+1,0);
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=n;i++) p[i] = p[i-1]+v[i];

    map<int,int>m;

    int ans = 0;

    for(int i=1;i<=n;i++)
    {
        int left = p[i-1] + k;
        m[left]++;

        int right = p[i];
        ans += m[right]; /// count how many subarrays (l,i) satisifes the condition
    }

    return ans;
}

Example 2

Calculate the number of SubArrays such that Sum(l,r) = SubArray's length

Solution Sketch
The solution is almost identical except there is something more to learn in here . As the paramter k consists of l and r , the idea is to put them in such a way that f(l) and f(r) are on diffrent sides.

1
2
3

    Sum(l,r) = r-l+1
=>  Prefix(r) - Prefix(l-1) = r-l+1
=>  Prefix(l-1) - l = Prefix(r) - r - 1

Code


int solve()
{
    int n,k;
    cin>>n>>k;

    vector<int>v(n+1),p(n+1,0);
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=n;i++) p[i] = p[i-1]+v[i];

    map<int,int>m;

    int ans = 0;

    for(int i=1;i<=n;i++)
    {
        int left = p[i-1] - i;
        m[left]++;

        int right = p[i] - i - 1;
        ans += m[right]; /// count how many subarrays (l,current right end) satisifes the condition
    }
    
    return ans;
}

More Practice Problems

Count the Subarrays (HackerEarth)

Code

/** Which of the favors of your Lord will you deny ? **/

#define int long long

void solveTC()
{
    int n,k;
    cin>>n>>k;

    vector<int>v(n+1),p(n+1);
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=n;i++) p[i] = p[i-1] + v[i];

    sort(ALL(p));
    DBG(p);

    /**
    p(r) > p(l-1) + k

    for every l-1  we count how many r's such that p(r) > p(l-1) + k
    **/

    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        int need = p[i-1] + k;
        int less = upper_bound(ALL(p),need) - p.begin() - 1;
        DBG(less);

        ans += n-less;
    }
    cout<<ans<<endl;
}

Number of Subarrays with Bounded Maximum (LeetCode)

Hint

2 Pointer . Find the candidate borders [l,r]

Code

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        
        int n = A.size();
        int left = -1 , right = -1 , ans = 0;
        for(int i=0;i<n;i++)
        {
            if(A[i]>=L) right = i;
            if(A[i]>R) left = i;
            
            ans += (right-left);
        }
        
        return ans;
    }
};

Increasing SubArrays (CodeChef)

Hint

2 Pointer . Find the candidate borders [l,r]

Code

#define int long long
void solveTC()
{
    int n;
    cin>>n;

    vector<int>v(n+1);
    for(int i=1;i<=n;i++) cin>>v[i];

    int left = 0, right = 0, ans = 0;
    for(int i=1; i<=n; i++)
    {
        if(v[i]>=v[i-1])
            right = i;
        else if(v[i]<v[i-1])
            left = i-1 , right = i;

        DBG(right-left);
        ans += (right-left); /// number of candidate subarrays in the [left+1,right] border
    }

    cout<<ans<<endl;
}

Three Occurreneces (Codeforces)

Hint 1

Can you think of a way to solve the number of distinct elements in ranges [i,fixed R] using Segment Tree ?

Hint 2

Can you think of a way to track the number of numbers that have frequency 3 in ranges [i,fixed R] using the same Segment Tree ?

Code

/** Which of the favors of your Lord will you deny ? **/

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

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define F first
#define S second

#define ALL(x)      (x).begin(), (x).end()
#define READ        freopen("alu.txt", "r", stdin)
#define WRITE       freopen("vorta.txt", "w", stdout)

#ifndef ONLINE_JUDGE
#define DBG(x)      cout << __LINE__ << " says: " << #x << " = " << (x) << endl
#else
#define DBG(x)
#define endl "\n"
#endif

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int INF = 1e9;

struct node
    {
        PLL mx;
        LL lazy;

        node()
        {
            mx = {-INF,0};
            lazy = 0;
        }

        node(PLL mx)
        {
            this-> mx = mx;
            lazy = 0;
        }

        void create_leaf(LL val)
        {
            mx = {val,1};
            lazy = 0;
        }
    };

struct LazySegmentTree
{
    vector<node>Tree;
    vector<int>ara;
    int n;

    LazySegmentTree(int n)
    {
        this->n = n;
        int len = n+1;
        ara = vector<int>(len);
        Tree = vector<node>(len<<2);
    }

    void build()
    {
        __build(1,1,n);
    }

    void update(int L,int R,LL add)
    {
        __update(1,1,n,L,R,add);
    }

    node query(int L,int R)
    {
        return __query(1,1,n,L,R);
    }

    /**-------------------------------------**/

    node merge_nodes(node &A,node &B)
    {
        if(A.mx.F>B.mx.F)
            return A;
        else if(A.mx.F<B.mx.F)
            return B;
        else
            return node({A.mx.F,A.mx.S+B.mx.S});
    }

    void node_update(int v,LL add)
    {
        Tree[v].mx.F += add;
        Tree[v].lazy += add;
    }

    void push(int v,int st,int en)
    {
        int lc = v<<1, rc = lc|1;

        if(st != en)
        {
            node_update(lc,Tree[v].lazy);
            node_update(rc,Tree[v].lazy);
        }

        Tree[v].lazy = 0;
    }

    void __build(int cur,int start,int end) /** build the segment tree **/
    {
        if(start==end)
        {
            Tree[cur].create_leaf(0);
            return;
        }

        int mid = (start+end)>>1;
        int lc = cur<<1, rc = lc|1;

        __build(lc,start,mid);
        __build(rc,mid+1,end);

        Tree[cur] = merge_nodes(Tree[lc],Tree[rc]);
    }

    void __update(int cur, int start, int end, int l,int r, LL add)
    {
        push(cur,start,end); /** Pushdown to children node **/

        if(r<start || end<l) return;
        else if (l<=start && r>=end)
        {
            node_update(cur,add);
            push(cur,start,end); /** Pushdown to children node **/
        }
        else
        {
            int mid = (start + end)>>1;
            int lc = cur<<1, rc = lc|1;

            __update(lc, start, mid,l,min(r,mid), add);
            __update(rc, mid+1, end,max(l,mid+1),r, add);

            Tree[cur] = merge_nodes(Tree[lc],Tree[rc]);
        }
    }

    node __query(int cur,int start,int end,int l,int r) /** RANGE query **/
    {
        push(cur,start,end); /** Pushdown to children node **/

        if(l>r) return node({-INF,0});

        if(start>=l && end<=r)
        {
            return Tree[cur];
        }

        int mid = (start+end)>>1;
        int lc = cur<<1, rc = lc|1;

        node p1 = __query(lc,start,mid,l,min(r,mid));
        node p2 = __query(rc,mid+1,end,max(l,mid+1),r);

        return merge_nodes(p1,p2);

    }

};

void UNDO(int x, LazySegmentTree &lst, vector<vector<int>> &pos)
{
    int sz = pos[x].size();
    if(sz<4)
        return;

    int L = pos[x][sz-4]+1;
    int R = pos[x][sz-3];

    lst.update(L,R,-1);
}

void DO(int x, LazySegmentTree &lst, vector<vector<int>> &pos)
{
    int sz = pos[x].size();
    if(sz<4)
        return;

    int L = pos[x][sz-4]+1;
    int R = pos[x][sz-3];

    lst.update(L,R,+1);
}

int32_t main()
{
    optimizeIO();

    int n;
    cin>>n;

    LazySegmentTree LST(n);
    LST.build();

    vector<int>v(n+1);
    for(int i=1; i<=n; i++)
        cin>>v[i];

    int max_num = n+1;
    vector<int>last(max_num,0);

    vector<vector<int>>pos(max_num);

    node q = LST.query(1,n);
    DBG(q.mx);

    LL ans = 0;

    for(int i=1; i<=n; i++)
    {
        int el = v[i];

        if(pos[el].empty())
            pos[el].push_back(0);

        UNDO(el,LST,pos);
        pos[el].push_back(i);
        DO(el,LST,pos);

        int L = last[el]+1;
        int R = i;

        last[el] = i;

        LST.update(L,R,-1);

        node q = LST.query(1,i);
        DBG(q.mx);

        if(q.mx.F==0) ans += q.mx.S;
    }

    cout<<ans<<endl;

    return 0;
}

/**

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}