Find the longest common subarray with the same element in range l to r for multiple queries

Question

Given an array, we need to find the longest contiguous subarray that has the same element in range l to r for multiple queries. For example, ar[] = {1,2,2,2,4,3,1,1,3}.

Query 1: l=1,r=5, element=2, output will be 3

Query 2: l=1,r=5, element=1, output will be 1

Query 3: l=6,r=9, element=3, output will be 1

Query 4: l=6,r=9, element=1, output will be 2

I can run a loop from l to r and calculate the longest contiguous occurance of the given element in the range, but I need a better approach. Constraints are 1<=l,r,no. of queries, size of array<=100000 Here is my brute force code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll i,j,k,m,n,l,r,x;
    n=9;
    ll ar[n]={1,2,2,2,4,3,1,1,3};
    ll query=4;//number of queries
    while(query--)
    {
        cin>>l>>r>>x;
        l--;r--;//changing to 0-based indexing
        ll ctr=0;
        ll ans=0;
        for(i=l;i<=r;i++)
        {
            if(ar[i]==x)
            {
                ctr++;
            }
            else ctr=0;
            ans=max(ctr,ans);
        }
        cout<<ans<<endl;
    }
}

Answer 1

This problem can be solved with a segment tree.

Here is my idea (not tested).

struct Node {
    // Length of this segment.
    int len;

    // Value and length of the longest prefix subarray.
    int prefix_val;
    int prefix_len;

    // Value and length of the longest suffix subarray.
    int suffix_val;
    int suffix_len;

    // Value and length of the longest subarray in this segment.
    int best_len;
    int best_val;
};

// Combines two nodes.
Node combine(Node lhs, Node rhs) {
    Node res;
    res.len = lhs.len + rhs.len;

    // Compute new best prefix subarray.
    res.prefix_val = lhs.prefix_val;
    res.prefix_len = lhs.prefix_len;
    if (lhs.prefix_len == lhs.len &&
        lhs.prefix_val == rhs.prefix_val) {
        res.prefix_len = lhs.len + rhs.prefix_len;
    }

    // Compute new best suffix subarray.
    res.suffix_val = rhs.suffix_val;
    res.suffix_len = rhs.suffix_len;
    if (rhs.suffix_len == rhs.len &&
        rhs.suffix_val == lhs.suffix_val) {
        res.suffix_len = rhs.len + lhs.suffix_len;
    }
    res.best_val = lhs.best_val;
    res.best_len = lhs.best_len;
    if (res.best_len < rhs.best_len) {
        res.best_val = rhs.best_val;
        res.best_len = rhs.best_len;
    }
    if (res.best_len < res.prefix_len) {
        res.best_val = res.prefix_val;
        res.best_len = res.prefix_len;
    }
    if (res.best_len < res.suffix_len) {
        res.best_val = res.suffix_val;
        res.best_len = res.suffix_len;
    }

    // Middle subarray.
    if (lhs.suffix_val == rhs.prefix_val) {
        int len = lhs.suffix_len + rhs.prefix_len;
        if (res.best_len < len) {
            res.best_val = val;
            res.best_len = len;
        }
    }
    return res;
}

Complexity is O(logN) per query.