## Implement Queue using Stacks

We are given a stack data structure with push and pop operations, the task is to implement a queue using instances of stack data structure and operations on them.

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:

Method 1 (By making enQueue operation costly) This method makes sure that oldest entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.

```enQueue(q, x)
1) While stack1 is not empty, push everything from satck1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.

dnQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it
```

Method 2 (By making deQueue operation costly)In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

```enQueue(q,  x)
1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.
```

Method 2 is definitely better than method 1.
Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.
Implementation of method 2:

`/* Program to implement a queue using two stacks */`
`#include<stdio.h>`
`#include<stdlib.h>`
`/* structure of a stack node */`
`struct` `sNode`
`{`
`    ``int` `data;`
`    ``struct` `sNode *next;`
`};`
`/* Function to push an item to stack*/`
`void` `push(``struct` `sNode** top_ref, ``int` `new_data);`
`/* Function to pop an item from stack*/`
`int` `pop(``struct` `sNode** top_ref);`
`/* structure of queue having two stacks */`
`struct` `queue`
`{`
`    ``struct` `sNode *stack1;`
`    ``struct` `sNode *stack2;`
`};`
`/* Function to enqueue an item to queue */`
`void` `enQueue(``struct` `queue *q, ``int` `x)`
`{`
`    ``push(&q->stack1, x);`
`}`
`/* Function to dequeue an item from queue */`
`int` `deQueue(``struct` `queue *q)`
`{`
`    ``int` `x;`
`    ``/* If both stacks are empty then error */`
`    ``if``(q->stack1 == NULL && q->stack2 == NULL)`
`    ``{`
`        ``printf``(``"Q is empty"``);`
`        ``getchar``();`
`        ``exit``(0);`
`    ``}`
`/* Move elements from satck1 to stack 2 only if`
`stack2 is empty */`
`if``(q->stack2 == NULL)`
`{`
`    ``while``(q->stack1 != NULL)`
`    ``{`
`        ``x = pop(&q->stack1);`
`        ``push(&q->stack2, x);`
`        `
`    ``}`
`}`
`x = pop(&q->stack2);`
`return` `x;`
`}`
`/* Function to push an item to stack*/`
`void` `push(``struct` `sNode** top_ref, ``int` `new_data)`
`{`
`    ``/* allocate node */`
`    ``struct` `sNode* new_node =`
`        ``(``struct` `sNode*) ``malloc``(``sizeof``(``struct` `sNode));`
`        ``if``(new_node == NULL)`
`        ``{`
`            ``printf``(``"Stack overflow \n"``);`
`            ``getchar``();`
`            ``exit``(0);`
`            `
`        ``}`
`/* put in the data */`
`new_node->data = new_data;`
`/* link the old list off the new node */`
`new_node->next = (*top_ref);`
`/* move the head to point to the new node */`
`(*top_ref) = new_node;`
`}`
`/* Function to pop an item from stack*/`
`int` `pop(``struct` `sNode** top_ref)`
`{`
`    ``int` `res;`
`    ``struct` `sNode *top;`
`    `
`    ``/*If stack is empty then error */`
`    ``if``(*top_ref == NULL)`
`    ``{`
`        ``printf``(``"Stack overflow \n"``);`
`        ``getchar``();`
`        ``exit``(0);`
`        `
`    ``}`
`    ``else`
`    ``{`
`        ``top = *top_ref;`
`        ``res = top->data;`
`        ``*top_ref = top->next;`
`        ``free``(top);`
`        ``return` `res;`
`        `
`    ``}`
`}`
`/* Driver function to test anove functions */`
`int` `main()`
`{`
`    ``/* Create a queue with items 1 2 3*/`
`    ``struct` `queue *q = (``struct` `queue*)``malloc``(``sizeof``(``struct` `queue));`
`    ``q->stack1 = NULL;`
`    ``q->stack2 = NULL;`
`    ``enQueue(q, 1);`
`    ``enQueue(q, 2);`
`    ``enQueue(q, 3);`
`    `
`    ``/* Dequeue items */`
`    ``printf``(``"%d "``, deQueue(q));`
`    ``printf``(``"%d "``, deQueue(q));`
`    ``printf``(``"%d "``, deQueue(q));`
`getchar``();`
`}`

Output:

`1 2 3`

Queue can also be implemented using one user stack and one Function Call Stack. Below is modified Method 2 where recursion (or Function Call Stack) is used to implement queue using only one user defined stack.

```enQueue(x)
1) Push x to stack1.

deQueue:
1) If stack1 is empty then error.
2) If stack1 has only one element then return it.
3) Recursively pop everything from the stack1, store the popped item
in a variable res,  push the res back to stack1 and return res
```

The step 3 makes sure that the last popped item is always returned and since the recursion stops when there is only one item in stack1 (step 2), we get the last element of stack1 in dequeue() and all other items are pushed back in step

3. Implementation of method 2 using Function Call Stack:

`/* Program to implement a queue using one user defined stack `
`and one Function Call Stack */`
`#include<stdio.h>`
`#include<stdlib.h>`
`/* structure of a stack node */`
`struct` `sNode`
`{`
`    ``int` `data;`
`    ``struct` `sNode *next;`
`};`
`/* structure of queue having two stacks */`
`struct` `queue`
`{`
`    ``struct` `sNode *stack1;`
`};`
`/* Function to push an item to stack*/`
`void` `push(``struct` `sNode** top_ref, ``int` `new_data);`
`/* Function to pop an item from stack*/`
`int` `pop(``struct` `sNode** top_ref);`
`/* Function to enqueue an item to queue */`
`void` `enQueue(``struct` `queue *q, ``int` `x)`
`{`
`    ``push(&q->stack1, x);`
`}`
`/* Function to dequeue an item from queue */`
`int` `deQueue(``struct` `queue *q)`
`{`
`    ``int` `x, res;`
`    `
`    ``/* If both stacks are empty then error */`
`    ``if``(q->stack1 == NULL)`
`    ``{`
`        ``printf``(``"Q is empty"``);`
`        ``getchar``();`
`        ``exit``(0);`
`        `
`    ``}`
`    ``else` `if``(q->stack1->next == NULL)`
`    ``{`
`        ``return` `pop(&q->stack1);`
`        `
`    ``}`
`    ``else`
`    ``{`
`        ``/* pop an item from the stack1 */`
`        ``x = pop(&q->stack1);`
`        ``/* store the last dequeued item */`
`        ``res = deQueue(q);`
`        `
`        ``/* push everything back to stack1 */`
`        ``push(&q->stack1, x);`
`        ``return` `res;`
`        `
`    ``}`
`}`
`/* Function to push an item to stack*/`
`void` `push(``struct` `sNode** top_ref, ``int` `new_data)`
`{`
`    ``/* allocate node */`
`    ``struct` `sNode* new_node =`
`           ``(``struct` `sNode*) ``malloc``(``sizeof``(``struct` `sNode));`
`           `
`    ``if``(new_node == NULL)`
`    ``{`
`        ``printf``(``"Stack overflow \n"``);`
`        ``getchar``();`
`        ``exit``(0);`
`        `
`    ``}`
`/* put in the data */`
`new_node->data = new_data;`
`/* link the old list off the new node */`
`new_node->next = (*top_ref);`
`/* move the head to point to the new node */`
`(*top_ref) = new_node;`
`}`
`/* Function to pop an item from stack*/`
`int` `pop(``struct` `sNode** top_ref)`
`{`
`    ``int` `res;`
`    ``struct` `sNode *top;`
`    `
`    ``/*If stack is empty then error */`
`    ``if``(*top_ref == NULL)`
`    ``{`
`        ``printf``(``"Stack overflow \n"``);`
`        ``getchar``();`
`        ``exit``(0);`
`        `
`    ``}`
`    ``else`
`    ``{`
`    ``top = *top_ref;`
`    ``res = top->data;`
`    ``*top_ref = top->next;`
`    ``free``(top);`
`    ``return` `res;`
`    ``}`
`}`
`/* Driver function to test above functions */`
`int` `main()`
`{`
`    ``/* Create a queue with items 1 2 3*/`
`    ``struct` `queue *q = (``struct` `queue*)``malloc``(``sizeof``(``struct` `queue));`
`    ``q->stack1 = NULL;`
`    `
`    ``enQueue(q, 1);`
`    ``enQueue(q, 2);`
`    ``enQueue(q, 3);`
`    `
`    ``/* Dequeue items */`
`    ``printf``(``"%d "``, deQueue(q));`
`    ``printf``(``"%d "``, deQueue(q));`
`    ``printf``(``"%d "``, deQueue(q));`
`    `
`getchar``();`
`}`

Output:

```1 2 3

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Implement Stack using Queues

The problem is opposite of this post. We are given a Queue data structure that supports standard operations like enqueue() and dequeue(). We need to implement a Stack data structure using only instances of Queue and queue operations allowed on the instances.

A stack can be implemented using two queues. Let stack to be implemented be ‘s’ and queues used to implement be ‘q1’ and ‘q2’. Stack ‘s’ can be implemented in two ways:

Method 1 (By making push operation costly)
This method makes sure that newly entered element is always at the front of ‘q1’, so that pop operation just dequeues from ‘q1’. ‘q2’ is used to put every new element at front of ‘q1’.

```push(s, x) // x is the element to be pushed and s is stack
1) Enqueue x to q2
2) One by one dequeue everything from q1 and enqueue to q2.
3) Swap the names of q1 and q2
// Swapping of names is done to avoid one more movement of all elements
// from q2 to q1.

pop(s)
1) Dequeue an item from q1 and return it.
```
 ` `
`/* Program to implement a stack using `
`two queue */`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`class` `Stack`
`{ `
`    ``// Two inbuilt queues`
`    ``queue<``int``> q1, q2;`
`    `
`    ``// To maintain current number of`
`    ``// elements`
`    ``int` `curr_size;`
`    ``public``:`
`    ``Stack()`
`    ``{`
`        ``curr_size = 0;`
`    ``}`
`    ``void` `push(``int` `x)`
`    ``{`
`        ``curr_size++;`
`        ``// Push x first in empty q2`
`        ``q2.push(x);`
`        ``// Push all the remaining `
`        ``// elements in q1 to q2. `
`        ``while` `(!q1.empty())`
`        ``{`
`            ``q2.push(q1.front());`
`            ``q1.pop();`
`        ``}`
`        ``// swap the names of two queues`
`        ``queue<``int``> q = q1;`
`        ``q1 = q2;`
`        ``q2 = q;`
`    ``}`
`    ``void` `pop(){`
`        ``// if no elements are there in q1 `
`        ``if` `(q1.empty())`
`            ``return` `;`
`        ``q1.pop();`
`        ``curr_size--;`
`    ``}`
`    ``int` `top()`
`    ``{`
`        ``if` `(q1.empty())`
`            ``return` `-1;`
`        ``return` `q1.front();`
`    ``}`
`    ``int` `size()`
`    ``{`
`        ``return` `curr_size;`
`    ``}`
`};`
`// driver code`
`int` `main()`
`{`
`    ``Stack s;`
`    ``s.push(1);`
`    ``s.push(2);`
`    ``s.push(3);`
`    ``cout << ``"current size: "` `<< s.size() `
`         ``<< endl;`
`    ``cout << s.top() << endl;`
`    ``s.pop();`
`    ``cout << s.top() << endl;`
`    ``s.pop();`
`    ``cout << s.top() << endl;`
`    ``cout << ``"current size: "` `<< s.size() `
`         ``<< endl;`
`    ``return` `0;`
`}`

Output :

```current size: 3
3
2
1
current size: 1```

Method 2 (By making pop operation costly)
In push operation, the new element is always enqueued to q1. In pop() operation, if q2 is empty then all the elements except the last, are moved to q2. Finally the last element is dequeued from q1 and returned.

```push(s,  x)
1) Enqueue x to q1 (assuming size of q1 is unlimited).

pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
// Swapping of names is done to avoid one more movement of all elements
// from q2 to q1.
```
`/* Program to implement a stack `
`using two queue */`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`class` `Stack`
`{`
`    ``queue<``int``> q1, q2;`
`    ``int` `curr_size;`
`    ``public``:`
`    ``Stack()`
`    ``{`
`        ``curr_size = 0;`
`    ``}`
`    ``void` `pop()`
`    ``{`
`        ``if` `(q1.empty())`
`            ``return``;`
`        ``// Leave one element in q1 and `
`        ``// push others in q2.`
`        ``while` `(q1.size() != 1)`
`        ``{`
`            ``q2.push(q1.front());`
`            ``q1.pop();`
`        ``}`
`        ``// Pop the only left element `
`        ``// from q1`
`        ``q1.pop();`
`        ``curr_size--;`
`        ``// swap the names of two queues`
`        ``queue<``int``> q = q1;`
`        ``q1 = q2;`
`        ``q2 = q;`
`    ``}`
`    ``void` `push(``int` `x)`
`    ``{`
`        ``q1.push(x);`
`        ``curr_size++;`
`    ``}`
`    ``int` `top()`
`    ``{`
`        ``if` `(q1.empty())`
`            ``return` `-1;`
`        ``while``( q1.size() != 1 )`
`        ``{`
`           ``q2.push(q1.front());`
`           ``q1.pop();`
`        ``} `
`        `
`        ``// last pushed element`
`        ``int` `temp = q1.front();`
`        `
`        ``// push last element to q2`
`        ``q2.push(temp);`
`        ``// swap the two queues names`
`        ``queue<``int``> q = q1;`
`        ``q1 = q2;`
`        ``q2 = q;`
`        ``return` `temp;`
`    ``}`
`    ``int` `size()`
`    ``{`
`        ``return` `curr_size;`
`    ``}`
`};`
`// driver code`
`int` `main()`
`{`
`    ``Stack s;`
`    ``s.push(1);`
`    ``s.push(2);`
`    ``s.push(3);`
`    ``s.push(4);`
`    ``cout << ``"current size: "` `<< s.size() `
`         ``<< endl;`
`    ``cout << s.top() << endl;`
`    ``s.pop();`
`    ``cout << s.top() << endl;`
`    ``s.pop();`
`    ``cout << s.top() << endl;`
`    ``cout << ``"current size: "` `<< s.size() `
`         ``<< endl;`
`    ``return` `0;`
`}`

Output :

```current size: 4
4
3
2
current size: 2

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

```
```

## Implement a stack using single queue

We are given queue data structure, the task is to implement stack using only given queue data structure.

We have discussed a solution that uses two queues. In this article, a new solution is discussed that uses only one queue. This solution assumes that we can find size of queue at any point. The idea is to keep newly inserted element always at front, keeping order of previous elements same. Below are complete steps.

```// x is the element to be pushed and s is stack
push(s, x)
1) Let size of q be s.
1) Enqueue x to q
2) One by one Dequeue s items from queue and enqueue them.

// Removes an item from stack
pop(s)
1) Dequeue an item from q

```

Below is implementation of the idea.

`// C++ program to implement a stack using`
`// single queue`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`// User defined stack that uses a queue`
`class` `Stack`
`{`
`    ``queue<``int``>q;`
`public``:`
`    ``void` `push(``int` `val);`
`    ``void` `pop();`
`    ``int` `top();`
`    ``bool` `empty();`
`};`
`// Push operation`
`void` `Stack::push(``int` `val)`
`{`
`    ``//  Get previous size of queue`
`    ``int` `s = q.size();`
`    ``// Push current element`
`    ``q.push(val);`
`    ``// Pop (or Dequeue) all previous`
`    ``// elements and put them after current`
`    ``// element`
`    ``for` `(``int` `i=0; i<s; i++)`
`    ``{`
`        ``// this will add front element into`
`        ``// rear of queue`
`        ``q.push(q.front());`
`        ``// this will delete front element`
`        ``q.pop();`
`    ``}`
`}`
`// Removes the top element`
`void` `Stack::pop()`
`{`
`    ``if` `(q.empty())`
`        ``cout << ``"No elements\n"``;`
`    ``else`
`        ``q.pop();`
`}`
`// Returns top of stack`
`int`  `Stack::top()`
`{`
`    ``return` `(q.empty())? -1 : q.front();`
`}`
`// Returns true if Stack is empty else false`
`bool` `Stack::empty()`
`{`
`    ``return` `(q.empty());`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``Stack s;`
`    ``s.push(10);`
`    ``s.push(20);`
`    ``cout << s.top() << endl;`
`    ``s.pop();`
`    ``s.push(30);`
`    ``s.pop();`
`    ``cout << s.top() << endl;`
`    ``return` `0;`
`}`

Output :

```20
10

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Find if an expression has duplicate parenthesis or not

Given an balanced expression, find if it contains duplicate parenthesis or not. A set of parenthesis are duplicate if same subexpression is surrounded by multiple parenthesis.

Examples:

```Below expressions have duplicate parenthesis -
((a+b)+((c+d)))
The subexpression "c+d" is surrounded by two
pairs of brackets.

(((a+(b)))+(c+d))
The subexpression "a+(b)" is surrounded by two
pairs of brackets.

(((a+(b))+c+d))
The whole expression is surrounded by two
pairs of brackets.

Below expressions don't have any duplicate parenthesis -
((a+b)+(c+d))
No subsexpression is surrounded by duplicate
brackets.

((a+(b))+(c+d))
No subsexpression is surrounded by duplicate
brackets.
```

It may be assumed that the given expression is valid and there are not any white spaces present.

The idea is to use stack. We iterate through the given expression and for each character in the expression, if the character is a open parenthesis ‘(‘ or any of the operators or operands, we push it to the stack. If the character is close parenthesis ‘)’, then pop characters from the stack till matching open parenthesis ‘(‘ is found. However if the immediate pop hits is open parenthesis ‘(‘, then we have found a duplicate parenthesis. For example, (((a+b))+c) has duplicate brackets around “a+b”. When we reach second “)” after a+b, we have “((” in the stack. Since the top of stack is a opening bracket, we conclude that there are duplicate brackets..

Below is C++ implementation of above idea :

`// C++ program to find duplicate parenthesis in a`
`// balanced expression`
`#include <iostream>`
`#include <stack>`
`using` `namespace` `std;`
`// Function to find duplicate parenthesis in a`
`// balanced expression`
`bool` `findDuplicateparenthesis(string str)`
`{`
`    ``// create a stack of characters`
`    ``stack<``char``> Stack;`
`    ``// Iterate through the given expression`
`    ``for` `(``char` `ch : str)`
`    ``{`
`        ``// if current character is close parenthesis ')'`
`        ``if` `(ch == ``')'``)`
`        ``{`
`            ``// pop character from the stack`
`            ``char` `top = Stack.top();`
`            ``Stack.pop();`
`            ``// if immediate pop is a open parenthesis '(',`
`            ``// we have found duplicate`
`            ``if` `(top == ``'('``)`
`                ``return` `true``;`
`            ``// else we continue popping characters from the`
`            ``// stack till open parenthesis '(' is encountered`
`            ``else`
`            ``{`
`                ``while` `(top != ``'('``)`
`                ``{`
`                    ``top = Stack.top();`
`                    ``Stack.pop();`
`                ``}`
`            ``}`
`        ``}`
`        ``// push open parenthesis '(', operators and`
`        ``// operands to stack`
`        ``else`
`            ``Stack.push(ch);`
`    ``}`
`    ``// No duplicates found`
`    ``return` `false``;`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``// input balanced expression`
`    ``string str = ``"(((a+(b))+(c+d)))"``;`
`    ``if` `(findDuplicateparenthesis(str))`
`        ``cout << ``"Duplicate Found "``;`
`    ``else`
`        ``cout << ``"No Duplicates Found "``;`
`    ``return` `0;`
`}`

Output:

```Duplicate Found
```

Time complexity of above solution is O(n).
Auxiliary space used by the program is O(n).

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Find maximum difference between nearest left and right smaller elements

Given array of integers, the task is to find the maximum absolute difference between nearest left and right smaller element of every element in array.

Note : If there is no smaller element on right side or left side of any element then we take zero as smaller element. For example for leftmost element, nearest smaller element on left side is considered as 0. Similarly for rightmost elements, smaller element on right side is considered as 0.

Examples:

```Input : arr[] = {2, 1, 8}
Output : 1
Left smaller  LS[] {0, 0, 1}
Right smaller RS[] {1, 0, 0}
Maximum Diff of abs(LS[i] - RS[i]) = 1

Input  : arr[] = {2, 4, 8, 7, 7, 9, 3}
Output : 4
Left smaller   LS[] = {0, 2, 4, 4, 4, 7, 2}
Right smaller  RS[] = {0, 3, 7, 3, 3, 3, 0}
Maximum Diff of abs(LS[i] - RS[i]) = 7 - 3 = 4

Input : arr[] = {5, 1, 9, 2, 5, 1, 7}
Output : 1
```

simple solution is to find nearest left and right smaller elements for every element and then update the maximum difference between left and right smaller element , this take O(n^2) time.

An efficient solution takes O(n) time. We use a stack. The idea is based on the approach discussed in next greater element article. The interesting part here is we compute both left smaller and right smaller using same function.

```Let input array be 'arr[]' and size of array be 'n'

Find all smaller element on left side
1. Create a new empty stack S and an array LS[]
2. For every element 'arr[i]' in the input arr[],
where 'i' goes from 0 to n-1.
a) while S is nonempty and the top element of
S is greater than or equal to 'arr[i]':
pop S

b) if S is empty:
'arr[i]' has no preceding smaller value
LS[i] = 0

c) else:
the nearest smaller value to 'arr[i]' is top
of stack
LS[i] = s.top()

d) push 'arr[i]' onto S

Find all smaller element on right side
3. First reverse array arr[]. After reversing the array,
right smaller become left smaller.
4. Create an array RRS[] and repeat steps  1 and 2 to
fill RRS (in-place of LS).

5. Initialize result as -1 and do following for every element
arr[i]. In the reversed array right smaller for arr[i] is
stored at RRS[n-i-1]
return result = max(result, LS[i]-RRS[n-i-1])
```

Below is implementation of above idea

`// C++ program to find the difference b/w left and`
`// right smaller element of every element in array`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`// Function to fill left smaller element for every`
`// element of arr[0..n-1]. These values are filled`
`// in SE[0..n-1]`
`void` `leftSmaller(``int` `arr[], ``int` `n, ``int` `SE[])`
`{`
`    ``// Create an empty stack`
`    ``stack<``int``>S;`
`    ``// Traverse all array elements`
`    ``// compute nearest smaller elements of every element`
`    ``for` `(``int` `i=0; i<n; i++)`
`    ``{`
`        ``// Keep removing top element from S while the top`
`        ``// element is greater than or equal to arr[i]`
`        ``while` `(!S.empty()  && S.top() >= arr[i])`
`            ``S.pop();`
`        ``// Store the smaller element of current element`
`        ``if` `(!S.empty())`
`            ``SE[i] = S.top();`
`        ``// If all elements in S were greater than arr[i]`
`        ``else`
`            ``SE[i] = 0;`
`        ``// Push this element`
`        ``S.push(arr[i]);`
`    ``}`
`}`
`// Function returns maximum difference b/w  Left  &`
`// right smaller element`
`int` `findMaxDiff(``int` `arr[], ``int` `n)`
`{`
`    ``int` `LS[n];  ``// To store left smaller elements`
`    ``// find left smaller element of every element`
`    ``leftSmaller(arr, n, LS);`
`    ``// find right smaller element of every element`
`    ``// first reverse the array and do the same process`
`    ``int` `RRS[n];  ``// To store right smaller elements in`
`                 ``// reverse array`
`    ``reverse(arr, arr + n);`
`    ``leftSmaller(arr, n, RRS);`
`    ``// find maximum absolute difference b/w LS  & RRS`
`    ``// In the reversed array right smaller for arr[i] is`
`    ``// stored at RRS[n-i-1]`
`    ``int` `result = -1;`
`    ``for` `(``int` `i=0 ; i< n ; i++)`
`        ``result = max(result, ``abs``(LS[i] - RRS[n-1-i]));`
`    ``// return maximum difference b/w LS  & RRS`
`    ``return` `result;`
`}`
`// Driver program`
`int` `main()`
`{`
`    ``int` `arr[] = {2, 4, 8, 7, 7, 9, 3};`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`    ``cout << ``"Maximum diff :  "`
`         ``<< findMaxDiff(arr, n) << endl;`
`    ``return` `0;`
`}`

Output:

``` Maximum Diff  : 4
```

Time complexity : O(n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Minimum swaps to make two arrays identical

Given two arrays which have same values but in different order, we need to make second array same as first array using minimum number of swaps.
Examples:

```Input  : arrA[] = {3, 6, 4, 8},
arrB[] = {4, 6, 8, 3}
Output : 2
we can make arrB to same as arrA in 2 swaps
which are shown below,
swap 4 with 8,   arrB = {8, 6, 4, 3}
swap 8 with 3,   arrB = {3, 6, 4, 8}```

This problem can be solved by modifying the array B. We save the index of array A elements in array B i.e. if ith element of array A is at jth position in array B, then we will make arrB[i] = j
For above given example, modified array B will be, arrB = {3, 1, 0, 2}. This modified array represents distribution of array A element in array B and our goal is to sort this modified array in minimum number of swaps because after sorting only array B element will be aligned with array A elements.

So we count these swaps in modified array and that will be our final answer.
Please see below code for better understanding.

`// C++ program to make an array same to another`
`// using minimum number of swap`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// Function returns the minimum number of swaps`
`// required to sort the array`
`int` `minSwapsToSort(``int` `arr[], ``int` `n)`
`{`
`    ``// Create an array of pairs where first`
`    ``// element is array element and second element`
`    ``// is position of first element`
`    ``pair<``int``, ``int``> arrPos[n];`
`    ``for` `(``int` `i = 0; i < n; i++)`
`    ``{`
`        ``arrPos[i].first = arr[i];`
`        ``arrPos[i].second = i;`
`    ``}`
`    ``// Sort the array by array element values to`
`    ``// get right position of every element as second`
`    ``// element of pair.`
`    ``sort(arrPos, arrPos + n);`
`    ``// To keep track of visited elements. Initialize`
`    ``// all elements as not visited or false.`
`    ``vector<``bool``> vis(n, ``false``);`
`    ``// Initialize result`
`    ``int` `ans = 0;`
`    ``// Traverse array elements`
`    ``for` `(``int` `i = 0; i < n; i++)`
`    ``{`
`        ``// already swapped and corrected or`
`        ``// already present at correct pos`
`        ``if` `(vis[i] || arrPos[i].second == i)`
`            ``continue``;`
`        ``// find out the number of  node in`
`        ``// this cycle and add in ans`
`        ``int` `cycle_size = 0;`
`        ``int` `j = i;`
`        ``while` `(!vis[j])`
`        ``{`
`            ``vis[j] = 1;`
`            ``// move to next node`
`            ``j = arrPos[j].second;`
`            ``cycle_size++;`
`        ``}`
`        ``// Update answer by adding current cycle.`
`        ``ans += (cycle_size - 1);`
`    ``}`
`    ``// Return result`
`    ``return` `ans;`
`}`
`// method returns minimum number of swap to make`
`// array B same as array A`
`int` `minSwapToMakeArraySame(``int` `a[], ``int` `b[], ``int` `n)`
`{`
`    ``// map to store position of elements in array B`
`    ``// we basically store element to index mapping.`
`    ``map<``int``, ``int``> mp;`
`    ``for` `(``int` `i = 0; i < n; i++)`
`        ``mp[b[i]] = i;`
`    ``// now we're storing position of array A elements`
`    ``// in array B.`
`    ``for` `(``int` `i = 0; i < n; i++)`
`        ``b[i] = mp[a[i]];`
`    ``/* We can uncomment this section to print modified`
`      ``b array`
`    ``for (int i = 0; i < N; i++)`
`        ``cout << b[i] << " ";`
`    ``cout << endl; */`
`    ``// returing minimum swap for sorting in modified`
`    ``// array B as final answer`
`    ``return` `minSwapsToSort(b, n);`
`}`
`//  Driver code to test above methods`
`int` `main()`
`{`
`    ``int` `a[] = {3, 6, 4, 8};`
`    ``int` `b[] = {4, 6, 8, 3};`
`    ``int` `n = ``sizeof``(a) / ``sizeof``(``int``);`
`    ``cout << minSwapToMakeArraySame(a, b, n);`
`    ``return` `0;`
`}`

Output:

```2

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Number of swaps to sort when only adjacent swapping allowed

Given an array arr[] of non negative integers. We can perform a swap operation on any two adjacent elements in the array. Find the minimum number of swaps needed to sort the array in ascending order.

Examples:

```Input  : arr[] = {3, 2, 1}
Output : 3
We need to do following swaps
(3, 2), (3, 1) and (1, 2)

Input  : arr[] = {1, 20, 6, 4, 5}
Output : 5
```
)

There is an interesting solution to this problem. It can be solved using the fact that number of swaps needed is equal to number of inversions. So we basically need to count inversions in array.

The fact can be established using below observations:
1) A sorted array has no inversions.
2) An adjacent swap can reduce one inversion. Doing x adjacent swaps can reduce x inversions in an array.

`// C++ program to count number of swaps required`
`// to sort an array when only swapping of adjacent`
`// elements is allowed.`
`#include <bits/stdc++.h>`
`/* This function merges two sorted arrays and returns inversion`
`   ``count in the arrays.*/`
`int` `merge(``int` `arr[], ``int` `temp[], ``int` `left, ``int` `mid, ``int` `right)`
`{`
`    ``int` `inv_count = 0;`
`    ``int` `i = left; ``/* i is index for left subarray*/`
`    ``int` `j = mid;  ``/* i is index for right subarray*/`
`    ``int` `k = left; ``/* i is index for resultant merged subarray*/`
`    ``while` `((i <= mid - 1) && (j <= right))`
`    ``{`
`        ``if` `(arr[i] <= arr[j])`
`            ``temp[k++] = arr[i++];`
`        ``else`
`        ``{`
`            ``temp[k++] = arr[j++];`
`            ``/* this is tricky -- see above explanation/`
`              ``diagram for merge()*/`
`            ``inv_count = inv_count + (mid - i);`
`        ``}`
`    ``}`
`    ``/* Copy the remaining elements of left subarray`
`     ``(if there are any) to temp*/`
`    ``while` `(i <= mid - 1)`
`        ``temp[k++] = arr[i++];`
`    ``/* Copy the remaining elements of right subarray`
`     ``(if there are any) to temp*/`
`    ``while` `(j <= right)`
`        ``temp[k++] = arr[j++];`
`    ``/*Copy back the merged elements to original array*/`
`    ``for` `(i=left; i <= right; i++)`
`        ``arr[i] = temp[i];`
`    ``return` `inv_count;`
`}`
`/* An auxiliary recursive function that sorts the input`
`   ``array and returns the number of inversions in the`
`   ``array. */`
`int` `_mergeSort(``int` `arr[], ``int` `temp[], ``int` `left, ``int` `right)`
`{`
`    ``int` `mid, inv_count = 0;`
`    ``if` `(right > left)`
`    ``{`
`        ``/* Divide the array into two parts and call`
`          ``_mergeSortAndCountInv() for each of the parts */`
`        ``mid = (right + left)/2;`
`        ``/* Inversion count will be sum of inversions in`
`           ``left-part, right-part and number of inversions`
`           ``in merging */`
`        ``inv_count  = _mergeSort(arr, temp, left, mid);`
`        ``inv_count += _mergeSort(arr, temp, mid+1, right);`
`        ``/*Merge the two parts*/`
`        ``inv_count += merge(arr, temp, left, mid+1, right);`
`    ``}`
`    ``return` `inv_count;`
`}`
`/* This function sorts the input array and returns the`
`   ``number of inversions in the array */`
`int` `countSwaps(``int` `arr[], ``int` `n)`
`{`
`    ``int` `temp[n];`
`    ``return` `_mergeSort(arr, temp, 0, n - 1);`
`}`
`/* Driver progra to test above functions */`
`int` `main(``int` `argv, ``char``** args)`
`{`
`    ``int` `arr[] = {1, 20, 6, 4, 5};`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`    ``printf``(``"Number of swaps is %d \n"``, countSwaps(arr, n));`
`    ``return` `0;`
`}`

Output:

```Number of swaps is 5
```

Time Complexity : O(n Log n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Minimum number of swaps required to sort an array

Given an array of n distinct elements, find the minimum number of swaps required to sort the array.

Examples:

```Input : {4, 3, 2, 1}
Output : 2
Explanation : Swap index 0 with 3 and 1 with 2 to
form the sorted array {1, 2, 3, 4}.

Input : {1, 5, 4, 3, 2}
Output : 2
```

This can be easily done by visualizing the problem as a graph. We will have n nodes and an edge directed from node i to node j if the element at i’th index must be present at j’th index in the sorted array.

```
Graph for {4, 3, 2, 1}
```

The graph will now contain many non-intersecting cycles. Now a cycle with 2 nodes will only require 1 swap to reach the correct ordering, similarly a cycle with 3 nodes will only require 2 swap to do so.

```
Graph for {4, 5, 2, 1, 5}
```

Hence,

• ans = Σi = 1k(cycle_size – 1)

where k is the number of cycles

Below is the C++ implementation of the idea.

`// C++ program to find  minimum number of swaps`
`// required to sort an array`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`// Function returns the minimum number of swaps`
`// required to sort the array`
`int` `minSwaps(``int` `arr[], ``int` `n)`
`{`
`    ``// Create an array of pairs where first`
`    ``// element is array element and second element`
`    ``// is position of first element`
`    ``pair<``int``, ``int``> arrPos[n];`
`    ``for` `(``int` `i = 0; i < n; i++)`
`    ``{`
`        ``arrPos[i].first = arr[i];`
`        ``arrPos[i].second = i;`
`    ``}`
`    ``// Sort the array by array element values to`
`    ``// get right position of every element as second`
`    ``// element of pair.`
`    ``sort(arrPos, arrPos + n);`
`    ``// To keep track of visited elements. Initialize`
`    ``// all elements as not visited or false.`
`    ``vector<``bool``> vis(n, ``false``);`
`    ``// Initialize result`
`    ``int` `ans = 0;`
`    ``// Traverse array elements`
`    ``for` `(``int` `i = 0; i < n; i++)`
`    ``{`
`        ``// already swapped and corrected or`
`        ``// already present at correct pos`
`        ``if` `(vis[i] || arrPos[i].second == i)`
`            ``continue``;`
`        ``// find out the number of  node in`
`        ``// this cycle and add in ans`
`        ``int` `cycle_size = 0;`
`        ``int` `j = i;`
`        ``while` `(!vis[j])`
`        ``{`
`            ``vis[j] = 1;`
`            ``// move to next node`
`            ``j = arrPos[j].second;`
`            ``cycle_size++;`
`        ``}`
`        ``// Update answer by adding current cycle.`
`        ``ans += (cycle_size - 1);`
`    ``}`
`    ``// Return result`
`    ``return` `ans;`
`}`
`// Driver program to test the above function`
`int` `main()`
`{`
`    ``int` `arr[] = {1, 5, 4, 3, 2};`
`    ``int` `n = (``sizeof``(arr) / ``sizeof``(``int``));`
`    ``cout << minSwaps(arr, n);`
`    ``return` `0;`
`}`

Output:

```2
```

Time Complexity: O(n*log(n))
Auxiliary Space: O(n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Subarray Inversions

We have an array A of n integers that we’re planning on sorting. Specifically, we want to know how close the array is to sorted. In order to achieve this, we introduce the idea of an inversion. An inversion in array is a pair of two indices i and jsuch that i < j and A[i] > A[j]. If our array contains one inversion, we need only swap A[i]and A[j] in order to sort the array. An array that contains 0 inversions is by definition sorted.

Problem: Given an array A of n integers, find the sum of the number of inversions in all subarrays of length k. To clarify, one must determine the number of inversions in each of the n – k + 1 subarrays of length k and add them together.

Input: The first line contains two space separated integers n and k. The next line contains a sequence of n space separated integers where the ith integer in the sequence is A[i].

Examples:

```Input : arr[] = {1 2 3 4 5 6}
k = 2
Output : 0

Input : arr[] = {1 6 7 2}
k = 3
Output : 2
There are two subarrays of size 3,
{1, 6, 7} and {6, 7, 2}. Count of
inversions in first subarray is 0
and count of inversions in second
subarray is 2. So sum is 0 + 2 = 2

Input :  8 4
12 3 14 8 15 1 4 22
Output : 14

Input :  10 5
15 51 44 44 76 50 29 88 48 50
Output : 25
```

[1] Naive Approach

This problem seems fairly trivial at first, and we can easily implement a naive algorithm to brute force the solution. We simply create a window of length k and roll the window along A, adding the number of inversions in the window at each iteration. To find the number of inversions, the simplest approach is to use two for loops to consider all pairs of elements and increment a counter if the pair forms an inversion.

This approach is very easy to implement, but is it efficient? Let’s analyze the algorithm. The outermost loop runs n – k + 1 times, once for each k-subarray of A. At each of these iterations, we find the number of inversions in the window. To do this, we consider element 1 and elements 2, …, n, then element 2 and elements 3, …, n until element n – 1 and element n. Effectively, we’re performing n + (n – 1) + (n – 2) + … + 1 = n(n + 1)/2operations. Thus, our algorithm performs approximately (n – k + 1)(n)(n + 1)/2operations which is O(n^3 – kn^2). Since k can range from 1 to n, the worst case performance for this algorithm is O(n^3) when k = n/2. We can do better!

`public` `class` `Subarray_Inversions {`
`    ``// Inversion counting method, slides window of [start,`
`    ``// end] across array`
`    ``static` `int` `inversion_count(``int` `n, ``int` `k, ``int``[] a)`
`    ``{`
`        ``int` `count = ``0``;`
`        ``for` `(``int` `start = ``0``; start < n - k + ``1``; start++) {`
`            ``int` `end = start + k;`
`            ``count += bubble_count(a, start, end);`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// Helper function, counts number of inversions via `
`    ``// bubble sort loop`
`    ``public` `static` `int` `bubble_count(``int``[] arr, ``int` `start, ``int` `end)`
`    ``{`
`        ``int` `count = ``0``;`
`        ``for` `(``int` `i = start; i < end; i++) {`
`            ``for` `(``int` `j = i + ``1``; j < end; j++) {`
`                ``if` `(arr[i] > arr[j]) {`
`                    ``count++;`
`                ``}`
`            ``}`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``public` `static` `void` `main(String[] args)`
`    ``{`
`        ``int` `n = ``10``;`
`        ``int``[] arr = { ``15``, ``51``, ``44``, ``44``, ``76``, ``50``, ``29``, ``88``, ``48``, ``50` `};`
`        ``int` `k = ``5``;`
`        ``long` `result = inversion_count(n, k, arr);`
`        ``System.out.println(result);`
`    ``}`
`}`

Output:

``` 25
```

[2] Mergesort-based Implementation

One optimization we can make is improving our inefficient, quadratic-time inversion counting method. One approach could involve using a mergesort-based method as outlined in this article. Since this runs in O(nlogn), our overall runtime is reduced to O(n^2logn), which is better, but still won’t be able to handle cases for which n = 10^6 for instance.

`import` `java.util.*;`
`public` `class` `Subarray_Inversions {`
`    ``// Inversion counting method, slides window of [start,`
`    ``// end] across array`
`    ``static` `int` `inversion_count(``int` `n, ``int` `k, ``int``[] a)`
`    ``{`
`        ``int` `count = ``0``;`
`        ``for` `(``int` `start = ``0``; start < n - k + ``1``; start++) {`
`            ``int``[] sub_array = ``new` `int``[k];`
`            ``for` `(``int` `i = start; i < start + k; i++) {`
`                ``sub_array[i - start] = a[i];`
`            ``}`
`            ``count += subarray_inversion_count(sub_array);`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// Counts number of inversions when merging`
`    ``public` `static` `long` `merge_inversion_count(``int``[] arr,`
`                                ``int``[] left, ``int``[] right)`
`    ``{`
`        ``int` `i = ``0``, j = ``0``, count = ``0``;`
`        ``while` `(i < left.length || j < right.length) {`
`            ``if` `(i == left.length) {`
`                ``arr[i + j] = right[j];`
`                ``j++;`
`            ``} ``else` `if` `(j == right.length) {`
`                ``arr[i + j] = left[i];`
`                ``i++;`
`            ``} ``else` `if` `(left[i] <= right[j]) {`
`                ``arr[i + j] = left[i];`
`                ``i++;`
`            ``} ``else` `{`
`                ``arr[i + j] = right[j];`
`                ``count += left.length - i;`
`                ``j++;`
`            ``}`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// Divide and conquer approach -- splits array and counts `
`    ``// inversions via merge method`
`    ``public` `static` `long` `subarray_inversion_count(``int``[] arr)`
`    ``{`
`        ``if` `(arr.length < ``2``)`
`            ``return` `0``;`
`        ``int` `m = (arr.length + ``1``) / ``2``;`
`        ``int` `left[] = Arrays.copyOfRange(arr, ``0``, m);`
`        ``int` `right[] = Arrays.copyOfRange(arr, m, arr.length);`
`        ``return` `subarray_inversion_count(left) + `
`               ``subarray_inversion_count(right) + `
`               ``merge_inversion_count(arr, left, right);`
`    ``}`
`    ``public` `static` `void` `main(String[] args)`
`    ``{`
`        ``int` `n = ``10``;`
`        ``int``[] arr = { ``15``, ``51``, ``44``, ``44``, ``76``, ``50``, ``29``, ``88``, ``48``, ``50` `};`
`        ``int` `k = ``5``;`
`        ``long` `result = inversion_count(n, k, arr);`
`        ``System.out.println(result);`
`    ``}`
`}`

Output:

``` 25
```

[3] Overlapping Subarrays Implementation

Let’s revisit our overall approach. We’re looking at the window [0, k) and finding the number of inversions, then we look at [1, k+1). There’s a significant overlap in this range: we’ve already counted the number of inversions in [1, k) during the first iteration, and now we’re counting them again! Instead of counting inversions, let’s count the change in inversions from one window to the next. Effectively, shifting the window is just adding one element to the head of the window and removing an element from its tail — the body of the window remains the same. Checking for inversions among internal elements would be redundant; all we need to do is add the number of inversions induced by the new element and subtract the number of inversions induced by the removed element. We now only need to count the number of inversions in the first window, which we can do in O(klogk) time, and for each of the n – k additional windows, we simply perform one iteration through the k elements in the array to find the change in the number of inversions. Our overall runtime is now O(k(n – k) + klogk) = O(nk – k)which is still worst case O(n^2).

`import` `java.util.*;`
`public` `class` `Subarray_Inversions {`
`    ``// Inversion counting method, slides window of [start,`
`    ``// end] across array`
`    ``static` `long` `inversion_count(``int` `n, ``int` `m, ``int``[] arr)`
`    ``{`
`        ``long` `count = ``0``;`
`        ``count += subarray_inversion_count_initial(Arrays.copyOfRange(arr, ``0``, m));`
`        ``long` `subarray_count = subarray_inversion_count_initial(Arrays.copyOfRange(arr, ``1``, m));`
`        ``for` `(``int` `start = ``1``; start <= n - m; start++) {`
`            ``int` `end = start + m - ``1``;`
`            ``long``[] ans = subarray_inversion_count(arr, start, end, subarray_count);`
`            ``count += ans[``0``];`
`            ``subarray_count = ans[``1``];`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// start >=1; find inversion in interval [start, end)`
`    ``public` `static` `long``[] subarray_inversion_count(``int``[] arr, ``int` `start,`
`                                          ``int` `end, ``long` `subarray_count)`
`    ``{`
`        ``int` `new_element = arr[end];`
`        ``long` `count = subarray_count;`
`        ``for` `(``int` `i = start; i < end; i++) {`
`            ``if` `(new_element < arr[i])`
`                ``count++;`
`        ``}`
`        ``long` `totalSum = count;`
`        ``int` `last_element = arr[start];`
`        ``for` `(``int` `i = start + ``1``; i <= end; i++) {`
`            ``if` `(last_element > arr[i])`
`                ``count--;`
`        ``}`
`        ``long``[] ans = { totalSum, count };`
`        ``return` `ans;`
`    ``}`
`    ``// Counts number of inversions when merging`
`    ``public` `static` `long` `merge_inversion_count(``int``[] arr, ``int``[] left, `
`                                                       ``int``[] right)`
`    ``{`
`        ``int` `i = ``0``, j = ``0``, count = ``0``;`
`        ``while` `(i < left.length || j < right.length) {`
`            ``if` `(i == left.length) {`
`                ``arr[i + j] = right[j];`
`                ``j++;`
`            ``} ``else` `if` `(j == right.length) {`
`                ``arr[i + j] = left[i];`
`                ``i++;`
`            ``} ``else` `if` `(left[i] <= right[j]) {`
`                ``arr[i + j] = left[i];`
`                ``i++;`
`            ``} ``else` `{`
`                ``arr[i + j] = right[j];`
`                ``count += left.length - i;`
`                ``j++;`
`            ``}`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// Divide and conquer approach -- splits array and counts`
`    ``// inversions via merge method`
`    ``public` `static` `long` `subarray_inversion_count_initial(``int``[] arr)`
`    ``{`
`        ``if` `(arr.length < ``2``)`
`            ``return` `0``;`
`        ``int` `m = (arr.length + ``1``) / ``2``;`
`        ``int` `left[] = Arrays.copyOfRange(arr, ``0``, m);`
`        ``int` `right[] = Arrays.copyOfRange(arr, m, arr.length);`
`        ``return` `subarray_inversion_count_initial(left) + `
`               ``subarray_inversion_count_initial(right) + `
`               ``merge_inversion_count(arr, left, right);`
`    ``}`
`    ``public` `static` `void` `main(String[] args) ``throws` `Exception`
`    ``{`
`        ``int` `n = ``10``;`
`        ``int``[] arr = { ``15``, ``51``, ``44``, ``44``, ``76``, ``50``, ``29``, ``88``, ``48``, ``50` `};`
`        ``int` `k = ``5``;`
`        ``long` `result = inversion_count(n, k, arr);`
`        ``System.out.println(result);`
`    ``}`
`}`

Output:

``` 25
```

[4] Binary Indexed Tree Implementation

Iterating over each window seems inevitable, so the bottleneck here appears to be the way we handle the windows. We know that consecutive windows overlap significantly, so all we need to know is the number of elements greater than the newly added element and number of elements less than the newly removed element. Many times, algorithms that perform the same or similar operation(s) repeatedly can be improved by the use of a more robust data structure. In our case, we’re looking for a dynamic data structure that can efficiently answer queries about an element’s relative position when sorted. We can use a self-balancing binary tree to actually maintain a sorted list, but insertion/removal takes logarithmic time. We can do this in constant time using a Binary Indexed Tree, or Fenwick Tree.

A binary indexed tree is a tree represented in the form of an array. It uses clever bit manipulation to compute the cumulative sum of elements very efficiently. We can call the function update(index, val) function to add val to BIT[index] and all of the ancestors of index. The function read(index) returns the sum of the values stored at BIT[index]and all of the ancestors of index in the tree. Thus, calling read(index) returns the cumulative sum of all elements in BIT less than or equal to index. Instead of storing values, if we simply store 1, we can use read(index + 1) to determine the number of elements less than index. Now, we can construct a binary indexed tree by inserting the elements (updating) of the first window. For subsequent windows, we can remove the trailing element by calling update(tail_element, -1) and add the new element with update(head_element, 1). Since this is a tree, the longest possible root-node path is O(logk), Thus, we achieve an optimal runtime of O(nlogk + klogk) = O(nlogk)!

Or do we…? Remember, binary indexed trees allocate memory for every possible value in the range [0, max_element], so this requires O(max_element) time and space. For very sparse arrays, this can be quite costly. Instead, we can define a hash function to . We can do this because we’re only concerned about inversions — as long as we keep the relative magnitude the same (i.e. A[i] <= A ==> A[hash(i)] <= A[hash(j)]), our solution will still be correct. Thus, we can map all the elements in A to the set {0, 1, 2, …, n}, yielding a guaranteed runtime of O(nlogk).

`import` `java.util.*;`
`public` `class` `Subarray_Inversions {`
`    ``// Declare binary indexed tree with global scope`
`    ``static` `BIT bit;`
`    ``// first window, counts first k elements and creates`
`    ``// BIT`
`    ``static` `long` `inversionCountBIT1(``int``[] arr, ``int` `start, `
`                                               ``int` `end)`
`    ``{`
`        ``bit = ``new` `BIT(arr.length);`
`        ``long` `count = ``0``;`
`        ``for` `(``int` `index = start; index >= end; index--) {`
`            ``count += bit.read(arr[index]);`
`            ``bit.update(arr[index], ``1``);`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// subsequent windows, removes previous element, adds`
`    ``// new element, and increments change in inversions`
`    ``static` `long` `inversionCountBIT2(``int``[] arr, ``int` `start,`
`                                       ``int` `end, ``long` `val)`
`    ``{`
`        ``bit.update(arr[start + ``1``], -``1``); ``// remove trailing element`
`        ``// find number of elements in range [start, end-1] `
`        ``// greater than first`
`        ``int` `numGreaterThanFirst = start - end - bit.read(arr[start + ``1``] + ``1``);`
`        ``long` `count = val + bit.read(arr[end]) - numGreaterThanFirst;`
`        ``bit.update(arr[end], ``1``); ``// adds leading element`
`        ``return` `count;`
`    ``}`
`    ``// Main method to count inversions in size k subarrays`
`    ``public` `static` `long` `inversionCount(``int` `n, ``int` `k, ``int``[] arr)`
`    ``{`
`        ``bit = ``new` `BIT(n);`
`        ``HashMap<Integer, Integer> freq = ``new` `HashMap<Integer, Integer>();`
`        ``int``[] asort = arr.clone();`
`        ``// Map elements from [A[0]...A[n-1]] to [1...n]`
`        ``Arrays.sort(asort);`
`        ``int` `index = ``0``;`
`        ``int` `current = ``1``;`
`        ``for` `(``int` `i = ``0``; i < n; i++) {`
`            ``if` `(!freq.containsKey(asort[i])) {`
`                ``freq.put(asort[i], current);`
`                ``current++;`
`            ``}`
`        ``}`
`        ``for` `(``int` `i = ``0``; i < n; i++) {`
`            ``arr[i] = freq.get(arr[i]);`
`        ``}`
`        ``long` `count = ``0``;`
`        ``long` `val = ``0``;`
`        ``//[start - end] ==> start - end = k+1`
`        ``for` `(``int` `start = n - ``1``; start >= k - ``1``; start--) {`
`            ``int` `end = start - k + ``1``;`
`            ``if` `(start == n - ``1``) { ``// First pass`
`                ``val = inversionCountBIT1(arr, n - ``1``, n - k);`
`            ``} ``else` `{ ``// subsequent passes`
`                ``val = inversionCountBIT2(arr, start, end, val);`
`            ``}`
`            ``count += val;`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``public` `static` `void` `main(String[] args) ``throws` `Exception`
`    ``{`
`        ``int` `n = ``10``;`
`        ``int``[] arr = { ``15``, ``51``, ``44``, ``44``, ``76``, ``50``, ``29``, ``88``, ``48``, ``50` `};`
`        ``int` `k = ``5``;`
`        ``long` `result = inversionCount(n, k, arr);`
`        ``System.out.println(result);`
`    ``}`
`    ``// Implementation of Binary Indexed Tree`
`    ``static` `class` `BIT {`
`        ``int``[] tree;`
`        ``int` `maxVal;`
`    ``public` `BIT(``int` `N)`
`        ``{`
`            ``tree = ``new` `int``[N + ``1``];`
`            ``maxVal = N;`
`        ``}`
`        ``// Updates BIT, starting with element at index `
`        ``// and all ancestors`
`        ``void` `update(``int` `index, ``int` `val)`
`        ``{`
`            ``while` `(index <= maxVal) {`
`                ``tree[index] += val;`
`                ``index += (index & -index);`
`            ``}`
`        ``}`
`        ``// Returns the cumulative frequency of index `
`        ``// starting with element at index and all ancestors`
`        ``int` `read(``int` `index)`
`        ``{`
`            ``--index;`
`            ``int` `cumulative_sum = ``0``;`
`            ``while` `(index > ``0``) {`
`                ``cumulative_sum += tree[index];`
`                ``index -= (index & -index);`
`            ``}`
`            ``return` `cumulative_sum;`
`        ``}`
`    ``};`
`}`

Output:

``` 25

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Counting inversions in all subarrays of given size

Given an array and an integer k, count all inversions in all subarrays of size k.

Example:

```Input : a[] = {7, 3, 2, 4, 1},
k = 3;
Output : 6
Explanation: subarrays of size 3 are -
{7, 3, 2}
{3, 2, 4}
{2, 4, 1}
and there inversion count are 3, 1, 2
respectively. So, total number of
inversions are  6.```

It is strongly recommended to refer Inversion count in an array using BIT

The process of counting inversion is same as in the above linked article. First, we calculate the inversion in first k (k is given size of subarray) elements in the array using BIT. Now after this for every next subarray we subtract the inversion of first element of previous subarray and add the inversions of the next element not included in the previous subarray. This process is repeated until the last subarray is processed.On the above example this algorithm works like this-

```a[] = {7, 3, 2, 4, 1},
k = 3;

Inversion are counted for first subarray
A = {7, 3, 2} Let this be equal to invcount_A.

For counting the inversion of subarray B we
subtract the inversion of first element of A,
from invcount_A and add inversions of 4 (last
element of B) in the subarray B.
So, invcount_B = invcount_A - 2 + 0
= 3 - 2 + 0
= 1

Same process is repeated for next subarray
and sum of all inversion count is the answer.
```
`// C++ program to count inversions in all sub arrays`
`// of size k using Binary Indexed Tree`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// Returns sum of arr[0..index]. This function assumes`
`// that the array is preprocessed and partial sums of`
`// array elements are stored in BITree[].`
`int` `getSum(``int` `BITree[], ``int` `index)`
`{`
`    ``int` `sum = 0; ``// Initialize result`
`    ``// Traverse ancestors of BITree[index]`
`    ``while` `(index > 0) {`
`        ``// Add current element of BITree to sum`
`        ``sum += BITree[index];`
`        ``// Move index to parent node in getSum View`
`        ``index -= index & (-index);`
`    ``}`
`    ``return` `sum;`
`}`
`// Updates a node in Binary Index Tree (BITree) at`
`// given index in BITree.  The given value 'val' is `
`// added to BITree[i] and all of its ancestors in `
`// tree.`
`void` `updateBIT(``int` `BITree[], ``int` `n, ``int` `index, ``int` `val)`
`{`
`    ``// Traverse all ancestors and add 'val'`
`    ``while` `(index <= n) {`
`        ``// Add 'val' to current node of BI Tree`
`        ``BITree[index] += val;`
`        ``// Update index to that of parent `
`        ``// in update View`
`        ``index += index & (-index);`
`    ``}`
`}`
`// Converts an array to an array with values from 1 to n`
`// and relative order of smaller and greater elements `
`// remains same.  For example, {7, -90, 100, 1} is `
`// converted to {3, 1, 4, 2 }`
`void` `convert(``int` `arr[], ``int` `n)`
`{`
`    ``// Create a copy of arrp[] in temp and sort `
`    ``// the temp array in increasing order`
`    ``int` `temp[n];`
`    ``for` `(``int` `i = 0; i < n; i++)`
`        ``temp[i] = arr[i];`
`    ``sort(temp, temp + n);`
`    ``// Traverse all array elements`
`    ``for` `(``int` `i = 0; i < n; i++) {`
`        ``// lower_bound() Returns pointer to`
`        ``//  the first element greater than `
`        ``// or equal to arr[i]`
`        ``arr[i] = lower_bound(temp, temp + n, `
`                         ``arr[i]) - temp + 1;`
`    ``}`
`}`
`// Returns inversion count of all subarray `
`// of size k in arr[0..n-1]`
`int` `getInvCount(``int` `arr[], ``int` `k, ``int` `n)`
`{`
`    ``int` `invcount = 0; ``// Initialize result`
`    ``// Convert arr[] to an array with values from `
`    ``// 1 to n and relative order of smaller and `
`    ``// greater elements remains same.  For example, `
`    ``// {7, -90, 100, 1} is converted to {3, 1, 4, 2 }`
`    ``convert(arr, n);`
`    ``// Create a BIT with size equal to maxElement+1 `
`    ``// (Extra one is used so that elements can be`
`    ``// directly be used as index)`
`    ``int` `BIT[n + 1];`
`    ``for` `(``int` `i = 1; i <= n; i++)`
`        ``BIT[i] = 0;`
`    ``// Get inversion count of first subarray`
`    ``for` `(``int` `i = k - 1; i >= 0; i--) {`
`        ``// Get count of elements smaller than arr[i]`
`        ``invcount += getSum(BIT, arr[i] - 1);`
`        ``// Add current element to BIT`
`        ``updateBIT(BIT, n, arr[i], 1);`
`    ``}`
`    ``// now calculate the inversion of all other subarrays`
`    ``int` `ans = invcount;`
`    ``int` `i = 0, j = k, icnt = 0, jcnt = 0;`
`    ``while` `(j <= n - 1) {`
`        ``// calculate value of inversion count of first element`
`        ``// in previous subarray`
`        ``icnt = getSum(BIT, arr[i] - 1);`
`        ``updateBIT(BIT, n, arr[i], -1);`
`        ``// calculating inversion count of last element in the`
`        ``// current subarray`
`        ``jcnt = getSum(BIT, n) - getSum(BIT, arr[j]);`
`        ``updateBIT(BIT, n, arr[j], 1);`
`        ``// calculating inversion count of current subarray`
`        ``invcount = invcount - icnt + jcnt;`
`        ``// adding current inversion to the answer`
`        ``ans = ans + invcount;`
`        ``i++, j++;`
`    ``}`
`    ``return` `ans;`
`}`
`int` `main()`
`{`
`    ``int` `arr[] = { 7, 3, 2, 4, 1 };`
`    ``int` `k = 3;`
`    ``int` `n = ``sizeof``(arr) / ``sizeof``(``int``);`
`    ``cout << ``"Number of inversions in all "`
`         ``"subarrays of size "` `<< k <<``" are : "`
`         ``<< getInvCount(arr, k, n);`
`    ``return` `0;`
`}`

Output:

```Number of inversions in all subarrays of size 3 are : 6
```

Time Complexity :- inversion count of first subarray takes O(k log(n)) time and for all other subarray it takes O((n-k)log(n)). So overall time complexity is : O(n log n).
Auxiliary space:- O(n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at