Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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;
}
#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;
}
#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;
}
}
}
#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);
});
#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()