Algorithm


Problem Name: Data Structures - Array and simple queries

Problem Link: https://www.hackerrank.com/challenges/array-and-simple-queries/problem?isFullScreen=true

In this HackerRank in Data Structures - Array and simple queries solutions

Given two numbers N and M . N indicates the number of elements in the array A[](1 - indexed) and M indicates number of queries. You need to perform two types of queries on the array A[].

You are given M queries. Queries can be of two types, type 1 and type 2.

  • Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front.
  • Type 2 queries are represented as 2 i j : Modify the given array by removing elements from i to j and adding them to the back.

Your task is to simply print |A[1] - A[N]| of the resulting array after the execution of M queries followed by the resulting array.

Note While adding at back or front the order of elements is preserved.

Input Format

First line consists of two space-separated integers, N and M.

Second line contains N integers, which represent the elements of the array. M queries follow. Each line contains a query of either type 1 or type 2 in the form type i j

Constraints

  • 1 <= M, N <= 10**5
  • 1 <= A[i] <= 10**9
  • 1 <= i <= j <= N

Output Format

Print the absolute value i.e. abs(A[1] - A[N])

in the first line.
Print elements of the resulting array in the second line. Each element should be seperated by a single space.

Sample Input

8 4
1 2 3 4 5 6 7 8
1 2 4
2 3 5
1 4 7
2 1 4

Sample Output

1
2 3 6 5 7 8 4 1

 

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>
typedef struct _ct_node{
  int size;
  int priority;
  int value;
  struct _ct_node *left,*right;
} ct_node;
void tar(ct_node *root);
int get_size(ct_node *root);
ct_node* merge(ct_node *L,ct_node *R);
int sizeOf(ct_node *root);
void recalc(ct_node *root);
void split(int x,ct_node **L,ct_node **R,ct_node *root);
void computeTree();
int P[100000],T[100000],st[100000],N;
ct_node pool[100000];

int main(){
  int M,x,y,z,i;
  ct_node *root,*l,*m,*r,*t;
  scanf("%d%d",&N,&M);
  for(i = 0; i  <  N; i++){
    scanf("%d",&pool[i].value);
    P[i] = pool[i].priority = rand();
    pool[i].left = pool[i].right = NULL;
  }
  computeTree();
  for(i = 0; i  <  N; i++)
    if(T[i] == -1)
      root = & pool[i];
    else
      if(i<T[i])
        pool[T[i]].left = & pool[i];
      else
        pool[T[i]].right = & pool[i];
  get_size(root);
  for( i = 0; i  <  M; i++){
    scanf("%d%d%d",&x,&y,&z);
    switch(x){
      case 1:
        split(y - 2,&l,&t,root);
        split(z - y,&m,&r,t);
        root = merge(merge(m,l),r);
        break;
      default:
        split(y - 2,&l,&t,root);
        split(z - y,&m,&r,t);
        root = merge(merge(l,r),m);
    }
  }
  N = 0;
  tar(root>;
  printf("%d\n",(T[0]>T[N-1])?T[0]-T[N-1]:T[N-1]-T[0]);
  for(i = 0; i  <  N; i++)
    printf("%d ",T[i]);
  return 0;
}
void tar(ct_node *root){
  if(!root)
    return;
  tar(root -> left);
  T[N++] = root -> value;
  tar(root -> right);
  return;
}
int get_size(ct_node *root){
  if(!root)
    return 0;
  root->size=get_size(root->left)+get_size(root->right)+1;
  return root->size;
}
ct_node* merge(ct_node *L,ct_node *R){
  if(!L)
    return R;
  if(!R)
    return L;
  if(L -> priority > R -> priority){
    L -> right = merge(L -> right,R);
    recalc(L);
    return L;
  }
  R -> left = merge(L,R -> left);
  recalc(R);
  return R;
}
int sizeOf(ct_node *root){
  return (root) ? root -> size:0;
}
void recalc(ct_node *root){
  root -> size = sizeOf(root -> left) + sizeOf(root -> right) + 1;
  return;
}
void split(int x,ct_node **L,ct_node **R,ct_node *root){
  if(!root){
    *L =*R= NULL;
    return;
  }
  int curIndex = sizeOf(root -> left);
  ct_node *t;
  if(curIndex <= x>{
    split(x - curIndex - 1,&t,R,root -> right);
    root -> right = t;
    recalc(root);
    *L = root;
  }
  else{
    split(x,L,&t,root -> left);
    root -> left = t;
    recalc(root);
    *R = root;
  }
  return;
}
void computeTree(){
  int i,k,top=-1;
  for(i = 0; i  <  N; i++){
    k=top;
    while(k >= 0 && P[st[k]]  <  P[i])
      k--;
    if(k != -1)
      T[i] = st[k];
    if(k < top>
      T[st[k + 1]] = i;
    st[++k] = i;
    top = k;
  }
  T[st[0]] = -1;
  return;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int Random() { return rand() << 15 | rand(); }

struct item {
    int prior, value, cnt;
    item *left, *right;
    item(int val = 0): value(val), prior(Random()), cnt(0), left(nullptr), right(nullptr) {}
};

int n, m;
item *tr;

int Count(item * p) { return p? p->cnt: 0; }

void Update(item * p) { if (p) p->cnt = Count(p->left) + Count(p->right) + 1; }

void Merge(item* &p, item *l, item *r)
{
    if (!l || !r) p = l? l: r;
    else if (l->prior > r->prior) Merge(l->right, l->right, r), p = l;
    else Merge(r->left, l, r->left), p = r;
    Update(p);
}

void Split(item *p, item* &l, item* &r, int key, int add = 0)
{
    if (!p) { l = r = nullptr; return; }
    int curkey = add + Count(p->left);
    if (key  < = curkey) Split(p->left, l, p->left, key, add), r = p;
    else Split(p->right, p->right, r, key, curkey + 1), l = p;
    Update(p);
}

void Print(item *tr)
{
    if (tr) {
        Print(tr->left);
        printf("%d ", tr->value);
        Print(tr->right);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i  <  n; i++) {
        int a; scanf("%d", &a);
        Merge(tr, tr, new item(a));
    }
    while (m--) {
        int typ, l, r; scanf("%d %d %d", &typ, &l, &r); l--, r--;
        item *p1, *p2; Split(tr, tr, p2, r + 1); Split(tr, p1, tr, l);
        if (typ == 1) { Merge(tr, tr, p1); Merge(tr, tr, p2); }
        else { Merge(tr, p2, tr); Merge(tr, p1, tr); }
    }
    if (n == 1) printf("0\n");
    else {
        item *p1, *p2; Split(tr, tr, p2, n - 1); Split(tr, p1, tr, 1);
        printf("%d\n", abs(p1->value - p2->value));
        Merge(tr, p1, tr); Merge(tr, tr, p2);
    }
    Print(tr);
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class Solution {

    public static class Treap {

        public static class Node {
            public int payload;
            public int y;
            public int count = 1;

            Node left;
            Node right;

            public Node(int payload, int y) {
                this.payload = payload;
                this.y = y;
            }

            public Node(int payload, int y, Node left, Node right) {
                this.payload = payload;
                this.y = y;
                this.left = left;
                this.right = right;
            }

            public void fixCount() {
                count = (left == null ? 0 : left.count) +
                        (right == null ? 0 : right.count) + 1;
            }

            public List < Integer> toList() {
                List list = new ArrayList<>();
                printNode(this, list);
                return list;
            }

            private void printNode(Node node, List < Integer> list) {
                if (node == null) return;
                printNode(node.left, list);
                list.add(node.payload);
                printNode(node.right, list);
            }
        }

        public static Node merge(Node left, Node right) {
            if (left == null) return right;
            if (right == null) return left;

            if (left.y > right.y) {
                left.right = merge(left.right, right);
                left.fixCount();
                return left;
            } else {
                right.left = merge(left, right.left);
                right.fixCount();
                return right;
            }
        }

        public static Node[] splitByOrder(Node node, int order) {
            if (order == 0) {
                return new Node[]{null, node};
            } else if (node.count  < = order) {
                return new Node[]{node, null};
            } else if (node.left != null && node.left.count >= order) {
                Node[] subResult = splitByOrder(node.left, order);
                node.left = subResult[1];
                node.fixCount();
                return new Node[]{subResult[0], node};
            } else {
                Node[] subResult = splitByOrder(node.right,
                        order - (node.left != null ? node.left.count : 0) - 1);
                node.right = subResult[0];
                node.fixCount();
                return new Node[]{node, subResult[1]};
            }
        }

    }

    static Random random = new Random();

    public static void main(String[] args) {
        FastReader fastReader = new FastReader();
        int n = fastReader.nextInt();
        int m = fastReader.nextInt();

        Treap.Node root = new Treap.Node(fastReader.nextInt(), random.nextInt());
        for (int i = 1; i  <  n; i++) {
            root = Treap.merge(root, new Treap.Node(fastReader.nextInt(), random.nextInt()));
        }

        for (int i = 0; i  <  m; i++) {
            int a = fastReader.nextInt();
            int from = fastReader.nextInt();
            int to = fastReader.nextInt();

            Treap.Node[] subResult1 = Treap.splitByOrder(root, from - 1);
            Treap.Node first = subResult1[0];
            Treap.Node temp = subResult1[1];
            Treap.Node[] subResult2 = Treap.splitByOrder(temp,
                    to - (first != null ? first.count : 0));
            Treap.Node second = subResult2[0];
            Treap.Node third = subResult2[1];

            Treap.Node node = Treap.merge(first, third);

            if (a == 1) {
                root = Treap.merge(second, node);
            } else {
                root = Treap.merge(node, second);
            }
        }
        List < Integer> integers = root.toList();
        System.out.println(Math.abs(integers.get(0) - integers.get(integers.size() - 1)));
        System.out.println(integers.stream().map(i -> Integer.toString(i)).collect(Collectors.joining(" ")));
    }

    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - Javascript Programming


class TreeNode {
    _left = 0;
    _right = 1;

    constructor(value, parent = null, priority = null) {
        this.value = value;
        this.parent = parent;
        this.children = [];
        this.multiplicity = 1;
        this.priority = priority || this.getRandom();
        this.size = 1;
        this.leftSize = 0;
        this.rightSize = 0;
    }

    get left() {
        return this.children[this._left];
    }

    set left(node) {
        this.children[this._left] = node;

        if (node) {
            node.parent = this;
        }
    }

    get right() {
        return this.children[this._right];
    }

    set right(node) {
        this.children[this._right] = node;

        if (node) {
            node.parent = this;
        }
    }

    get rightSize() {
        return this._rightSize;
    }

    set rightSize(value) {
        this._rightSize = value;
    }

    get leftSize() {
        return this._leftSize;
    }

    set leftSize(value) {
        this._leftSize = value;
    }

    get size() {
        return this._size;
    }

    set size(value) {
        this._size = value;
    }

    getRandom() {
        return Math.floor(Math.random() * Number.MAX_SAFE_INTEGER) + 1;
    }
    
    swapChild(oldChild, newChild) {
        const side = this.left === oldChild ? 'left' : 'right';

        this[side] = newChild;
    }

    removeChild(child) {
        this.swapChild(child);
    }

    removeParent(undirected = false) {
        if (undirected) {
            const { parent } = this;

            if (parent) {
                parent.removeChild(this);
            }
        }

        this.parent = null;
    }
    
    updateSize() {
        this.leftSize = this.left ? this.left.size : 0;
        this.rightSize = this.right ? this.right.size : 0;

        this.size = this.leftSize + this.rightSize + 1;
    }

    split(key, implicitIndex = false) {
        const index = implicitIndex ? this.leftSize + 1 : this.value;

        if (key >= index) {
            const { right } = this;

            let r;

            if (right) {
                right.removeParent(true);

                if (implicitIndex) {
                    key -= index;
                }

                const { l: l2, r: r2 } = right.split(key, implicitIndex);

                this.right = l2;
                r = r2;
            }

            this.updateSize();

            return { l: this, r };
        }

        const { left } = this;

        let l;

        if (left) {
            left.removeParent(true);

            const { l: l2, r: r2 } = left.split(key, implicitIndex);

            l = l2;
            this.left = r2;
        }

        this.updateSize();

        return { l, r: this };
    }

    merge(node) {
        if (!node) return this;

        if (this.priority > node.priority) {
            const { left } = node;

            if (left) {
                left.removeParent(true);

                node.left = this.merge(left);
            } else {
                node.left = this;
            }

            node.updateSize();

            return node;
        }

        const { right } = this;

        if (right) {
            right.removeParent(true);

            this.right = right.merge(node);
        } else {
            this.right = node;
        }

        this.updateSize();

        return this;
    }
}

class ImplicitTreap {
    _root;

    constructor(root) {
        this.root = root;
    }

    get root() {
        return this._root;
    }

    set root(node) {
        this._root = node;

        if (node) {
            this.length = node.size;
        } else {
            this.length = 0;
        }
    }

    add(value, priority = null) {
        const newNode = new TreeNode(value, null, priority);

        if (!this.root) {
            this.root = newNode;
        } else {
            const { root, length } = this;
            const { l, r } = root.split(length + 1, true);
            
            this.root = l.merge(newNode).merge(r);
        }

        return newNode;
    }

    traverseInOrder(node = this.root) {
        let tree = [];

        if (node) {
            if (node.left) {
                tree = tree.concat(this.traverseInOrder(node.left));
            }

            tree.push(node.value);

            if (node.right) {
                tree = tree.concat(this.traverseInOrder(node.right));
            }
        }

        return tree;
    }
}

function print(arr) {
    const n = arr.length;
    const abs = Math.abs(arr[0] - arr[n - 1]);
    const elements = arr.join(' ');

    console.log(abs);
    console.log(elements);
}

function processData(arr, queries) {
    const t = new ImplicitTreap();
    for (const item of arr) {
        t.add(item);
    }

    for (const query of queries) {
        const [type, start, end] = query.split(' ');
        const startIndex = start - 1;
        const endIndex = end - 1;

        const { root } = t;
        const { l: p1, r: p2 } = root.split(startIndex, true);
        const { l: p3, r: p4 } = p2.split(endIndex - startIndex + 1, true);
        const p5 = (p1) ? p1.merge(p4) : p4;

        if (type == 1) {
            t.root = p3.merge(p5);
        } else {
            t.root = p5.merge(p3);
        }
    }

    const result = [];
    for (const item of t.traverseInOrder()) {
        result.push(item);
    }
    
    return result;
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   const args = _input.split('\n');
   const n = args.shift().split(' ')[0];
   const arr = args.shift().split(' ');
   const result = processData(arr, args);

   print(result);
});
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - Python Programming


#!/bin/python3
# Enter your code here. Read input from STDIN. Print output to STDOUT

import os
import array


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
        
    n, m = [int(s) for s in input().split()]           
    a = array.array('i', [int(s) for s in input().split()])
            
    for _ in range(m):
        t, i, j = [int(s) for s in input().split()]
        if t == 1:
            a = a[i-1:j] + a[:i-1] + a[j:]
        else:
            a = a[:i-1] + a[j:] + a[i-1:j]
            
    fptr.write(f'{abs(a[0] - a[-1])}\n')
    fptr.write(' '.join([str(aa) for aa in a]))
    fptr.write('\n')
    
    fptr.close()
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Array Pairs solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Median Updates solution in Hackerrank - Hacerrank solution C, C++, java,js, Python