Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Segment Tree Competitive Coding

Consecutive Permutation

Harsh

Last Updated on May 23, 2022 by Ria Pathak

Concepts Used

Segment Trees

Difficulty Level

Hard

Problem Statement :

Given an array of N unique elements and Q queries. In each query, we are given two values l,r. We want to know if there is a permutation of all the integers in this range such that in that permutation all the elements are consecutive. Print Yes if such a permutation exists else No.

See original problem statement here

Solution Approach :

Introduction :

We have to find where the array elements in the given range is
consecutive or not. We can solve this problem using brute force approach or using segment tree. Basic idea is to keep track of the lowest and highest values of the array within the given range now the difference between these values is equal to the difference between the ranges then we can say the array elements are consecutive, else not.

Method 1 (Brute force):

We can calculate the minimum and maximum values within the given range in linear time for each query by sorting the array in increasing order. Then check whether the difference between these values and the given range is same or not.

Method 2 (Segment Tree):

As the number of queries and array size is too large for linear search in every query, we will use segment tree to solve this problem.
A Segment Tree is a data structure which allows answering range queries very effectively over a large input. Each query takes logarithmic time. Range queries includes sum over a range, or finding a minimum value over a given range etc. Query be of any type we can use segment trees and modify it accordingly.
Leaf nodes of the tree stores the actual array values and intermediate nodes stores the information of subarrays with is require to solve the problem. Lets say if we have to find a sum between different ranges, so now the intermediate nodes will store the sum of the current subarray. We fill the nodes by recursively calling left and right subtree (dividing into segements), untill there is a single element left, which can be directly assigned the value of the array. Array representation of the tree is used to represent segment tree, where (i*2)+1 represents the left node and (i*2)+2 represents right node, parent will be represented by (i-1)/2 for every index i.
We will construct two segment trees, one for storing minimum values and other to store maximum values of the subarrays.
We begin with the original array and dividing it into two halves (left and right), untill there is a single element left (leaf) which can directly be filled with a[i] for any index i. Now for every range say l to r, we will store the minimum and maximum values of the current range in the node in first and second tree respectively.
Now that our tree is constructed, we will answer queries (minimum/maximum of the given range). The queries can be of 3 types:

  1. The range of the tree exactly matches with the query, in this case we will return the value stored in this node.
  2. The range either belongs to the left or right node, in this case we will make two recursive calls for left and right subtrees respectively.
  3. The range overlaps with two of more ranges, in this case we are forced to go to the lower levels of both the subtrees and find the gcd of the range which fits the current range and finally return the minimum/maximum of the values returned by both subtrees.
    Now after retrieving the minimum and maximum values within the range from both segment trees we will check whether the difference max - min +1 is equal to the range gap r-l+1. Since we are assuming array has distinct values this difference must be equal if the array elements are consecutive.

Algorithms :

construct_min():

  • if the current node is a leaf (subarray contains single elemnt), assign the value directly, (tree[curr]= arr[l]).
  • break the tree into two halves by recursively calling for left and right subtree, construct(l,mid) and construct(mid+1,r)
  • fill the current node with the minimum of left & right node. (tree[curr] = min(LeftSubtree , RightSubtree).

construct_max():

  • if the current node is a leaf (subarray contains single elemnt), assign the value directly, (tree[curr]= arr[l]).
  • break the tree into two halves by recursively calling for left and right subtree, construct(l,mid) and construct(mid+1,r)
  • fill the current node with the maximum of left & right node. (tree[curr] = max(LeftSubtree , RightSubtree).

RMQ_min():

  • if range is within the current range, return the value stored in node.
  • if current range is outside the boundaries, return -1.
  • else return the min of left & right subtrees.

RMQ_max():

  • if range is within the current range, return the value stored in node.
  • if current range is outside the boundaries, return -1.
  • else return the max of left & right subtrees.

Complexity Analysis :

In the brute force approach the time complexity for sorting is O(nlogn) and total time complexity will be O(Q*nlogn).
In segment tree, preprocessing time is O(n) for each tree and worst time to for range minimum/maximum query is equivalent to the height of the tree.
The space complexity is O(n) to store the segment tree.

Solutions:

#include

int tree_min[1000001], 
    tree_max[1000001]; 

int min(int a, int b) 
{ 
    return a < b ? a : b; 
} 

int max(int a, int b) 
{ 
    return a > b ? a : b; 
} 

// Segment tree for minimum element 
void build_min(int array[], int node, 
            int left, int right) 
{ 
    // If left is equal to right 
    if (left == right) 
        tree_min[node] = array[left]; 

    else { 
        // Divide the segment into equal halves 
        build_min(array, 2 * node, left, 
                (left + right) / 2); 

        build_min(array, 2 * node + 1, 
                (left + right) / 2 + 1, right); 


        tree_min[node] = min(tree_min[2 * node], 
                            tree_min[2 * node + 1]); 
    } 
} 

int query_min(int node, int c_l, 
            int c_r, int l, int r) 
{ 
    // Out of range 
    if (c_l > r || c_r < l) 
        return 1e9; 

    if (c_l >= l && c_r <= r) 
        return tree_min[node]; 
    else

        return min(query_min(2 * node, c_l, 
                            (c_l + c_r) / 2, l, r), 
                query_min(2 * node + 1, 
                            (c_l + c_r) / 2 + 1, 
                            c_r, l, r)); 
} 

void build_max(int array[], int node, 
            int left, int right) 
{ 
    // If left is equal to right 
    if (left == right) 
        tree_max[node] = array[left]; 

    else { 

        build_max(array, 2 * node, left, 
                (left + right) / 2); 

        build_max(array, 2 * node + 1, 
                (left + right) / 2 + 1, right); 


        tree_max[node] = max(tree_max[2 * node], 
                            tree_max[2 * node + 1]); 
    } 
} 


int query_max(int node, int c_l, 
            int c_r, int l, int r) 
{ 
    // Out of range 
    if (c_l > r || c_r < l) 
        return -1; 

    // Within the range completely 
    if (c_l >= l && c_r <= r) 
        return tree_max[node]; 
    else

        return max(query_max(2 * node, c_l, 
                            (c_l + c_r) / 2, l, r), 
                query_max(2 * node + 1, 
                            (c_l + c_r) / 2 + 1, 
                            c_r, l, r)); 
} 

void init(int array[], int n) 
{ 
    build_min(array, 1, 0, n - 1); 
    build_max(array, 1, 0, n - 1); 
} 

int isConsecutive(int x, int y, int n) 
{ 
    return ((query_max(1, 0, n - 1, x, y) - query_min(1,0, n - 1, x, y))== (y - x));
} 


int main() 
{ 
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n;
    scanf("%d",&n);
      int arr[n];
      for(int i=0;i

						 
#include  
using namespace std; 

// Segment tree 
int tree_min[1000001], 
    tree_max[1000001]; 


int min(int a, int b) 
{ 
    return a < b ? a : b; 
} 

int max(int a, int b) 
{ 
    return a > b ? a : b; 
} 


void build_min(int array[], int node, 
            int left, int right) 
{ 

    if (left == right) 
        tree_min[node] = array[left]; 

    else { 
        build_min(array, 2 * node, left, 
                (left + right) / 2); 

        build_min(array, 2 * node + 1, 
                (left + right) / 2 + 1, right); 

        tree_min[node] = min(tree_min[2 * node], 
                            tree_min[2 * node + 1]); 
    } 
} 

int query_min(int node, int c_l, 
            int c_r, int l, int r) 
{ 
    // Out of range 
    if (c_l > r || c_r < l) 
        return 1e9; 

    if (c_l >= l && c_r <= r) 
        return tree_min[node]; 
    else

        return min(query_min(2 * node, c_l, 
                            (c_l + c_r) / 2, l, r), 
                query_min(2 * node + 1, 
                            (c_l + c_r) / 2 + 1, 
                            c_r, l, r)); 
} 

// Segment tree for maximum element 
void build_max(int array[], int node, 
            int left, int right) 
{ 
    // If left is equal to right 
    if (left == right) 
        tree_max[node] = array[left]; 

    else { 
        // Divide the segment into equal halves 
        build_max(array, 2 * node, left, 
                (left + right) / 2); 

        build_max(array, 2 * node + 1, 
                (left + right) / 2 + 1, right); 

        tree_max[node] = max(tree_max[2 * node], 
                            tree_max[2 * node + 1]); 
    } 
} 

int query_max(int node, int c_l, 
            int c_r, int l, int r) 
{ 
    // Out of range 
    if (c_l > r || c_r < l) 
        return -1; 

    // Within the range completely 
    if (c_l >= l && c_r <= r) 
        return tree_max[node]; 
    else

        return max(query_max(2 * node, c_l, 
                            (c_l + c_r) / 2, l, r), 
                query_max(2 * node + 1, 
                            (c_l + c_r) / 2 + 1, 
                            c_r, l, r)); 
} 

// Build the tree 
void init(int array[], int n) 
{ 
    build_min(array, 1, 0, n - 1); 
    build_max(array, 1, 0, n - 1); 
} 


bool isConsecutive(int x, int y, int n) 
{ 
    return ((query_max(1, 0, n - 1, x, y) 
            - query_min(1, 0, n - 1, x, y)) 
            == (y - x)); 
} 


int main() 
{ 
  int t;
  cin>>t;
  while(t--)
  {
    int n;
    cin>>n;
      int arr[n];
      for(int i=0;i>arr[i];
      init(arr, n); 

    int q;
    cin>>q;
      for (int i = 0; i < q; i++) { 
          int l, r; 
          cin>>l>>r;
          cout << (isConsecutive(l - 1, r - 1, n) ?"Yes" : "No") << "\n"; 
    }
 } 

    return 0; 
} 

import java.util.*;

class Main
{ 

    static int[] tree_min = new int[1000001]; 
    static int[] tree_max = new int[1000001]; 

    static int min(int a, int b) 
    { 
        return a < b ? a : b; 
    } 

    static int max(int a, int b) 
    { 
        return a > b ? a : b; 
    } 

    static void build_min(int array[], int node, int left, int right) 
    { 
        // If left is equal to right 
        if (left == right) 
            tree_min[node] = array[left]; 

        else
        { 
            // Divide the segment into equal halves 
            build_min(array, 2 * node, left, (left + right) / 2); 

            build_min(array, 2 * node + 1, 
                    (left + right) / 2 + 1, right); 

            tree_min[node] = Math.min(tree_min[2 * node], 
                    tree_min[2 * node + 1]); 
        } 
    } 


    static int query_min(int node, int c_l, int c_r, int l, int r) 
    { 
        // Out of range 
        if (c_l > r || c_r < l) 
            return (int) 1e9; 

        // Within the range completely 
        if (c_l >= l && c_r <= r) 
            return tree_min[node]; 
        else

            return min(query_min(2 * node, c_l, (c_l + c_r) / 2, l, r), 
                    query_min(2 * node + 1, (c_l + c_r) / 2 + 1, c_r, l, r)); 
    } 

    // Segment tree for maximum element 
    static void build_max(int array[], int node, int left, int right) 
    { 
        // If left is equal to right 
        if (left == right) 
            tree_max[node] = array[left]; 

        else
        { 
            // Divide the segment into equal halves 
            build_max(array, 2 * node, left, (left + right) / 2); 

            build_max(array, 2 * node + 1, (left + right) / 2 + 1, right); 

            tree_max[node] = Math.max(tree_max[2 * node], 
                    tree_max[2 * node + 1]); 
        } 
    } 


    static int query_max(int node, int c_l, int c_r, int l, int r) 
    { 
        // Out of range 
        if (c_l > r || c_r < l) 
            return -1; 

        // Within the range completely 
        if (c_l >= l && c_r <= r) 
            return tree_max[node]; 
        else

            return Math.max(query_max(2 * node, c_l, (c_l + c_r) / 2, l, r), 
                    query_max(2 * node + 1, (c_l + c_r) / 2 + 1, c_r, l, r)); 
    } 

    // Build the tree 
    static void init(int array[], int n) 
    { 
        build_min(array, 1, 0, n - 1); 
        build_max(array, 1, 0, n - 1); 
    } 

    // Check if the given range is Consecutive 
    static boolean isConsecutive(int x, int y, int n) 
    { 
        return ((query_max(1, 0, n - 1, x, y) - 
                query_min(1, 0, n - 1, x, y)) == (y - x)); 
    } 

    public static void main(String[] args) 
    { 
      Scanner sc = new Scanner(System.in);
      int t = sc.nextInt();
      while(t-->0)
      {
        int n= sc.nextInt();
          int []arr = new int [n];
          for(int i=0;i

[forminator_quiz id="2287"]

So, in this blog, we have tried to explain the concept of segment trees in most optimal way. If you want to practice more for interview, visit Interview Coding Practice which is curated by our expert mentors at PrepBytes.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post