Largest interval in an Array that contains the given element X for Q queries

0 0 8 minutes read

Given an array arr[] of N elements and Q queries of the form [X]. For each query, the task is to find the largest interval [L, R] of the array such that the greatest element in the interval is arr[X], such that 1 ? L ? X ? R.
Note: The array has 1-based indexing.

Examples:

Input: N = 5, arr[] = {2, 1, 2, 3, 2}, Q = 3, query[] = {1, 2, 4}
Output:
[1, 3]
[2, 2]
[1, 5]
Explanation :
In 1st query, x = 1, so arr[x] = 2 and answer is L = 1 and R = 3. here, we can see that max(arr[1], arr[2], arr[3]) = arr[x], which is the maximum intervals.
In 2nd query, x = 2, so arr[x] = 1 and since it is the smallest element of the array, so the interval contains only one element, thus the range is [2, 2].
In 3rd query, x = 4, so arr[x] = 4, which is maximum element of the arr[], so the answer is whole array, L = 1 and R = N.

Input: N = 4, arr[] = { 1, 2, 2, 4}, Q = 2, query[] = {1, 2}
Output:
[1, 1]
[1, 3]
Explanation:
In 1st query, x = 1, so arr[x] = 1 and since it is the smallest element of the array, so the interval contains only one element, thus the range is [1, 1].
In 2nd query, x = 2, so arr[x] = 2 and answer is L = 1 and R = 3. here, we can see that max(arr[1], arr[2], arr[3]) = arr[x] = arr[2] = 2, which is the maximum intervals.

Approach: The idea is to precompute the largest interval for every value K in arr[] from 1 to N. Below are the steps:

For each element K in arr[], fix the index of the element K, then find how much we can extend the interval to it’s left and right.
Decrement left iterator till arr[left] ? K and similarly increment right iterator till arr[right] ? K.
The final value of left and right represents the starting and the ending index of the interval, which is stored in arrL[] and arrR[] respectively.
After we have precomputed interval range for each value. Then, for each query, we need to print the interval range for arr[x] i.e., arrL[arr[x]] and arrR[arr[x]].

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to precompute the interval
// for each query
void utilLargestInterval(int arr[],
                         int arrL[],
                         int arrR[],
                         int N)
{
 
    // For every values [1, N] find
    // the longest intervals
    for (int maxValue = 1;
         maxValue <= N; maxValue++) {
 
        int lastIndex = 0;
 
        // Iterate the array arr[]
        for (int i = 1; i <= N; i++) {
 
            if (lastIndex >= i
                || arr[i] != maxValue)
                continue;
            int left = i, right = i;
 
            // Shift the left pointers
            while (left > 0
                   && arr[left] <= maxValue)
                left--;
 
            // Shift the right pointers
            while (right <= N
                   && arr[right] <= maxValue)
                right++;
 
            left++, right--;
            lastIndex = right;
 
            // Store the range of interval
            // in arrL[] and arrR[].
            for (int j = left; j <= right; j++) {
 
                if (arr[j] == maxValue) {
                    arrL[j] = left;
                    arrR[j] = right;
                }
            }
        }
    }
}
 
// Function to find the largest interval
// for each query in Q[]
void largestInterval(
    int arr[], int query[], int N, int Q)
{
 
    // To store the L and R of X
    int arrL[N + 1], arrR[N + 1];
 
    // Function Call
    utilLargestInterval(arr, arrL,
                        arrR, N);
 
    // Iterate to find ranges for each query
    for (int i = 0; i < Q; i++) {
 
        cout << "[" << arrL[query[i]]
             << ", " << arrR[query[i]]
             << "]\n";
    }
}
 
// Driver Code
int main()
{
    int N = 5, Q = 3;
 
    // Given array arr[]
    int arr[N + 1] = { 0, 2, 1, 2, 3, 2 };
 
    // Given Queries
    int query[Q] = { 1, 2, 4 };
 
    // Function Call
    largestInterval(arr, query, N, Q);
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Function to precompute the interval
// for each query
static void utilLargestInterval(int arr[],
                                int arrL[],
                                int arrR[],
                                int N)
{
 
    // For every values [1, N] find
    // the longest intervals
    for(int maxValue = 1;
            maxValue <= N; maxValue++)
    {
       int lastIndex = 0;
        
       // Iterate the array arr[]
       for(int i = 1; i <= N; i++) 
       {
          if (lastIndex >= i || 
                 arr[i] != maxValue)
              continue;
          int left = i, right = i;
           
          // Shift the left pointers
          while (left > 0 && 
                 arr[left] <= maxValue)
              left--;
           
          // Shift the right pointers
          while (right <= N && 
                 arr[right] <= maxValue)
              right++;
           
          left++; 
          right--;
          lastIndex = right;
           
          // Store the range of interval
          // in arrL[] and arrR[].
          for(int j = left; j <= right; j++)
          {
             if (arr[j] == maxValue)
             {
                 arrL[j] = left;
                 arrR[j] = right;
             }
          }
       }
    }
}
 
// Function to find the largest interval
// for each query in Q[]
static void largestInterval(int arr[],
                            int query[], 
                            int N, int Q)
{
     
    // To store the L and R of X
    int []arrL = new int[N + 1];
    int []arrR = new int[N + 1];
 
    // Function Call
    utilLargestInterval(arr, arrL,
                        arrR, N);
 
    // Iterate to find ranges for 
    // each query
    for(int i = 0; i < Q; i++) 
    {
       System.out.print("[" + arrL[query[i]] + 
                       ", " + arrR[query[i]] + "]\n");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5, Q = 3;
 
    // Given array arr[]
    int arr[] = { 0, 2, 1, 2, 3, 2 };
 
    // Given queries
    int query[] = { 1, 2, 4 };
 
    // Function call
    largestInterval(arr, query, N, Q);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
 
# Function to precompute the interval
# for each query
def utilLargestInterval(arr, arrL, arrR, N):
  
    # For every values [1, N] find
    # the longest intervals
    for maxValue in range(1, N + 1):
        lastIndex = 0
  
        # Iterate the array arr[]
        for i in range(N + 1):
            if (lastIndex >= i or
                   arr[i] != maxValue):
                continue
             
            left = i
            right = i
  
            # Shift the left pointers
            while (left > 0 and
               arr[left] <= maxValue):
                left -= 1
  
            # Shift the right pointers
            while (right <= N and
               arr[right] <= maxValue):
                right += 1
  
            left += 1
            right -= 1
            lastIndex = right
  
            # Store the range of interval
            # in arrL[] and arrR[].
            for j in range(left, right + 1):
                if (arr[j] == maxValue):
                    arrL[j] = left
                    arrR[j] = right
             
# Function to find the largest interval
# for each query in Q[]
def largestInterval(arr, query, N, Q):
  
    # To store the L and R of X
    arrL = [0 for i in range(N + 1)]
    arrR = [0 for i in range(N + 1)]
  
    # Function call
    utilLargestInterval(arr, arrL, arrR, N);
  
    # Iterate to find ranges for each query
    for i in range(Q):
        print('[' + str(arrL[query[i]]) +
             ', ' + str(arrR[query[i]]) + ']')
  
# Driver code 
if __name__=="__main__":
     
    N = 5
    Q = 3
  
    # Given array arr[]
    arr = [ 0, 2, 1, 2, 3, 2 ]
  
    # Given Queries
    query = [ 1, 2, 4 ]
  
    # Function call
    largestInterval(arr, query, N, Q)
 
# This code is contributed by rutvik_56

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to precompute the interval
// for each query
static void utilLargestInterval(int []arr,
                                int []arrL,
                                int []arrR,
                                int N)
{
 
    // For every values [1, N] find
    // the longest intervals
    for(int maxValue = 1;
            maxValue <= N; maxValue++)
    {
       int lastIndex = 0;
        
       // Iterate the array []arr
       for(int i = 1; i <= N; i++)
       {
          if (lastIndex >= i || 
                 arr[i] != maxValue)
              continue;
               
          int left = i, right = i;
           
          // Shift the left pointers
          while (left > 0 && 
                 arr[left] <= maxValue)
              left--;
               
          // Shift the right pointers
          while (right <= N && 
                 arr[right] <= maxValue)
              right++;
           
          left++; 
          right--;
          lastIndex = right;
           
          // Store the range of interval
          // in arrL[] and arrR[].
          for(int j = left; j <= right; j++)
          {
             if (arr[j] == maxValue)
             {
                 arrL[j] = left;
                 arrR[j] = right;
             }
          }
       }
    }
}
 
// Function to find the largest interval
// for each query in Q[]
static void largestInterval(int []arr,
                            int []query, 
                            int N, int Q)
{
     
    // To store the L and R of X
    int []arrL = new int[N + 1];
    int []arrR = new int[N + 1];
 
    // Function Call
    utilLargestInterval(arr, arrL,
                        arrR, N);
 
    // Iterate to find ranges for 
    // each query
    for(int i = 0; i < Q; i++) 
    {
       Console.Write("[" + arrL[query[i]] + 
                    ", " + arrR[query[i]] + "]\n");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 5, Q = 3;
 
    // Given array []arr
    int []arr = { 0, 2, 1, 2, 3, 2 };
 
    // Given queries
    int []query = { 1, 2, 4 };
 
    // Function call
    largestInterval(arr, query, N, Q);
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to precompute the interval
// for each query
function utilLargestInterval(arr, arrL, arrR, N)
{
 
    // For every values [1, N] find
    // the longest intervals
    for (var maxValue = 1;
         maxValue <= N; maxValue++) {
 
        var lastIndex = 0;
 
        // Iterate the array arr[]
        for (var i = 1; i <= N; i++) {
 
            if (lastIndex >= i
                || arr[i] != maxValue)
                continue;
            var left = i, right = i;
 
            // Shift the left pointers
            while (left > 0
                   && arr[left] <= maxValue)
                left--;
 
            // Shift the right pointers
            while (right <= N
                   && arr[right] <= maxValue)
                right++;
 
            left++, right--;
            lastIndex = right;
 
            // Store the range of interval
            // in arrL[] and arrR[].
            for (var j = left; j <= right; j++) {
 
                if (arr[j] == maxValue) {
                    arrL[j] = left;
                    arrR[j] = right;
                }
            }
        }
    }
}
 
// Function to find the largest interval
// for each query in Q[]
function largestInterval( arr, query, N, Q)
{
 
    // To store the L and R of X
    var arrL = Array(N+1).fill(0),arrR = Array(N+1).fill(0);
 
    // Function Call
    utilLargestInterval(arr, arrL,
                        arrR, N);
 
    // Iterate to find ranges for each query
    for (var i = 0; i < Q; i++) {
 
        document.write( "[" + arrL[query[i]]
             + ", " + arrR[query[i]]
             + "]<br>");
    }
}
 
// Driver Code
var N = 5, Q = 3;
 
// Given array arr[]
var arr = [0, 2, 1, 2, 3, 2];
 
// Given Queries
var query = [1, 2, 4];
 
// Function Call
largestInterval(arr, query, N, Q);
 
// This code is contributed by itsok.
</script>

Output:

[1, 3]
[2, 2]
[1, 5]

Time Complexity: O(Q + N²)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!