Queries for number of elements on right and left

Last Updated : 06 Feb, 2023

Given Q queries of three types where every query consists of a number.

Add element num on the left
Add element num on the right
Print the number of elements to the right an left of the given element num.

The task is to write a program that performs the above queries.
Note: Elements in queries 1 and 2 are distinct and 0 <= num <= 10⁵.
Examples:

Input:
Q = 5
Query of type 1: num = 3
Query of type 2: num = 5
Query of type 1: num = 2
Query of type 1: num = 4
Query of type 3: num = 3
Output: element on the right: 1 element on the left: 2
After query 1, the element positioning is 3
After query 2, the element positioning is 35
After query 3, the element positioning is 235
After query 4, the element positioning is 4235
So there is 1 element to the right and 2 elements on the left of 3 when
query 3 is called.

The following steps can be followed to solve the above problem.

Initialize a variable left and right as 0, and two hash arrays position[] and mark[]. position[] is used to store the index of num on left and right and mark[] is used to mark if the num is on left or right.
For query-1, increase the count of left, and mark position[num] as left and mark[num] as 1.
For query-2, increase the count of right, and mark position[num] as right and mark[num] as 2
For query-3, check if the given number is present on right or left using mark[].
If the number is present on right, then the number of elements to the left of num will be (left-position[num]), and the number of elements to the right of num will be (position[num] - 1 + right).
If the number is present on left, then the number of elements to the right of num will be (right-position[num]), and the number of elements to the left of num will be (position[num] - 1 + *left).

Below is the implementation of the above approach:

CPP

// C++ program to print the number of elements
// on right and left of a given element
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005

// function to perform query 1
void performQueryOne(int num, int* left, int* right,
                     int* position, int* mark)
{
    // count number of elements on left
    *left = *left + 1;

    // store the index number
    position[num] = *(left);

    // mark the element is on left
    mark[num] = 1;
}

// function to perform query 2
void performQueryTwo(int num, int* left, int* right,
                     int* position, int* mark)
{
    // count number of elements on right
    *right = *right + 1;

    // store the index number
    position[num] = *(right);

    // mark the element is on right
    mark[num] = 2;
}

// function to perform query 3
void performQueryThree(int num, int* left, int* right,
                       int* position, int* mark)
{
    int toright, toleft;

    // if the element is on right
    if (mark[num] == 2) {
        toright = *right - position[num];
        toleft = position[num] - 1 + *left;
    }

    // if the element is on left
    else if (mark[num] == 1) {
        toleft = *left - position[num];
        toright = position[num] - 1 + *right;
    }

    // not present
    else {
        cout << "The number is not there\n";
        return;
    }

    cout << "The number of elements to right of "
         << num << ": " << toright;

    cout << "\nThe number of elements to left of "
         << num << ": " << toleft;
}

// Driver Code
int main()
{

    int left = 0, right = 0;

    // hashing arrays
    int position[MAXN] = { 0 };
    int mark[MAXN] = { 0 };

    int num = 3;

    // query type-1
    performQueryOne(num, &left, &right, position, mark);

    // query type-2
    num = 5;
    performQueryTwo(num, &left, &right, position, mark);

    // query type-2
    num = 2;
    performQueryOne(num, &left, &right, position, mark);

    // query type-2
    num = 4;
    performQueryOne(num, &left, &right, position, mark);

    // query type-3
    num = 3;
    performQueryThree(num, &left, &right, position, mark);

    return 0;
}

Java

// Java code implementation for the above approach
import java.io.*;
import java.util.*;

class GFG {

  static final int MAXN = 100005;

  // function to perform query 1
  static void performQueryOne(int num, int[] left,
                              int[] right, int[] position,
                              int[] mark)
  {
    // count number of elements on left
    left[0] = left[0] + 1;

    // store the index number
    position[num] = left[0];

    // mark the element is on left
    mark[num] = 1;
  }

  // function to perform query 2
  static void performQueryTwo(int num, int[] left,
                              int[] right, int[] position,
                              int[] mark)
  {
    // count number of elements on right
    right[0] = right[0] + 1;

    // store the index number
    position[num] = right[0];

    // mark the element is on right
    mark[num] = 2;
  }

  // function to perform query 3
  static void performQueryThree(int num, int[] left,
                                int[] right,
                                int[] position,
                                int[] mark)
  {
    int toright, toleft;

    // if the element is on right
    if (mark[num] == 2) {
      toright = right[0] - position[num];
      toleft = position[num] - 1 + left[0];
    }

    // if the element is on left
    else if (mark[num] == 1) {
      toleft = left[0] - position[num];
      toright = position[num] - 1 + right[0];
    }

    // not present
    else {
      System.out.println("The number is not there");
      return;
    }

    System.out.println(
      "The number of elements to right of " + num
      + ": " + toright);
    System.out.println(
      "The number of elements to left of " + num
      + ": " + toleft);
  }

  public static void main(String[] args)
  {
    int[] left = { 0 }, right = { 0 };

    // hashing arrays
    int[] position = new int[MAXN];
    int[] mark = new int[MAXN];

    Arrays.fill(position, 0);
    Arrays.fill(mark, 0);

    int num = 3;

    // query type-1
    performQueryOne(num, left, right, position, mark);

    // query type-2
    num = 5;
    performQueryTwo(num, left, right, position, mark);

    // query type-2
    num = 2;
    performQueryOne(num, left, right, position, mark);

    // query type-2
    num = 4;
    performQueryOne(num, left, right, position, mark);

    // query type-3
    num = 3;
    performQueryThree(num, left, right, position, mark);
  }
}

// This code is contributed by lokesh.

Python3

# python program to print the number of elements
# on right and left of a given element
MAXN = 100005

# function to perform query 1
def performQueryOne(num, position, mark):
    
    global left
    # count number of elements on left
    left = left + 1

    # store the index number
    position[num] = left

    # mark the element is on left
    mark[num] = 1

# function to perform query 2
def performQueryTwo(num, position, mark):
    
    global right
    # count number of elements on right
    right = right + 1

    # store the index number
    position[num] = right

    # mark the element is on right
    mark[num] = 2

# function to perform query 3
def performQueryThree(num, position, mark):
    toright = 0
    toleft = 0
    global left
    global right

    # if the element is on right
    if mark[num] == 2:
        toright = right - position[num]
        toleft = position[num] - 1 + left
    
    # if the element is on left
    elif mark[num] == 1:
        toleft = left - position[num]
        toright = position[num] - 1 + right

    # not present
    else:
        print("The number is not there \n")
        return

    print("The number of elements to right of ", num, " : " , toright)

    print("\nThe number of elements to left of ", num, " : ", toleft)

    
# Driver Code
left = 0
right = 0

# hashing arrays
position = [0]*MAXN
mark = [0]*MAXN

num = 3

# query type-1
performQueryOne(num, position, mark)

# query type-2
num = 5
performQueryTwo(num, position, mark)

# query type-2
num = 2
performQueryOne(num, position, mark)

# query type-2
num = 4
performQueryOne(num, position, mark)

# query type-3
num = 3
performQueryThree(num, position, mark)

# The code is contributed by Gautam goel.

using System;
class GFG {

  // function to perform query 1
  static void performQueryOne(int num, int[] left, 
                              int[] right, int[] position, 
                              int[] mark)
  {

    // count number of elements on left
    left[0] = left[0] + 1;

    // store the index number
    position[num] = left[0];

    // mark the element is on left
    mark[num] = 1;
  }


  // function to perform query 2
  static void performQueryTwo(int num, int[] left, 
                              int[] right, int[] position, 
                              int[] mark)
  {
    // count number of elements on right
    right[0] = right[0] + 1;

    // store the index number
    position[num] = right[0];

    // mark the element is on right
    mark[num] = 2;
  }


  // function to perform query 3
  static void performQueryThree(int num, int[] left, int[] right,
                                int[] position, int[] mark)
  {
    int toright, toleft;

    // if the element is on right
    if (mark[num] == 2) {
      toright = right[0] - position[num];
      toleft = position[num] - 1 + left[0];
    }

    // if the element is on left
    else if (mark[num] == 1) {
      toleft = left[0] - position[num];
      toright = position[num] - 1 + right[0];
    }

    // not present
    else {
      Console.WriteLine("The number is not there\n");
      return;
    }

    Console.WriteLine( "The number of elements to right of " + num + ": " + toright);


    Console.WriteLine("\nThe number of elements to left of " + num + ": " + toleft);
  }


  static void Main() {

    int MAXN = 100005;
    int[] left = {0};
    int[] right = {0};

    // hashing arrays
    int[] position = new int[MAXN];
    int[] mark = new int[MAXN];
    for(int i = 0; i < MAXN; i++){
      position[i] = 0;
      mark[i] = 0;
    }

    int num = 3;

    // query type-1
    performQueryOne(num, left, right, position, mark);

    // query type-2
    num = 5;
    performQueryTwo(num, left, right, position, mark);

    // query type-2
    num = 2;
    performQueryOne(num, left, right, position, mark);

    // query type-2
    num = 4;
    performQueryOne(num, left, right, position, mark);

    // query type-3
    num = 3;
    performQueryThree(num, left, right, position, mark);
  }
}

// the code is contributed by Nidhi goel.

JavaScript

<script>
    // JavaScript program to print the number of elements
    // on right and left of a given element
    const MAXN = 100005;

    let left = 0, right = 0;

    // hashing arrays
    let position = new Array(MAXN).fill(0);
    let mark = new Array(MAXN).fill(0);

    // function to perform query 1
    const performQueryOne = (num) => {
    
        // count number of elements on left
        left = left + 1;

        // store the index number
        position[num] = left;

        // mark the element is on left
        mark[num] = 1;
    }

    // function to perform query 2
    const performQueryTwo = (num) => {
    
        // count number of elements on right
        right = right + 1;

        // store the index number
        position[num] = right;

        // mark the element is on right
        mark[num] = 2;
    }

    // function to perform query 3
    const performQueryThree = (num) => {
        let toright, toleft;

        // if the element is on right
        if (mark[num] == 2) {
            toright = right - position[num];
            toleft = position[num] - 1 + left;
        }

        // if the element is on left
        else if (mark[num] == 1) {
            toleft = left - position[num];
            toright = position[num] - 1 + right;
        }

        // not present
        else {
            document.write("The number is not there<br/>");
            return;
        }

        document.write(`The number of elements to right of ${num}: ${toright}`);

        document.write(`<br/>The number of elements to left of ${num}: ${toleft}`);
    }

    // Driver Code
    let num = 3;

    // query type-1
    performQueryOne(num);

    // query type-2
    num = 5;
    performQueryTwo(num);

    // query type-2
    num = 2;
    performQueryOne(num);

    // query type-2
    num = 4;
    performQueryOne(num);

    // query type-3
    num = 3;
    performQueryThree(num);

// This code is contributed by rakeshsahni

</script>

The number of elements to right of 3: 1
The number of elements to left of 3: 2

Time Complexity: O(1) for every query.

Auxiliary Space: O(MAXN), where MAXN is 10⁵.

Striver

Improve

Article Tags :

Queries for number of elements on right and left

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem

Thank You!

What kind of Experience do you want to share?