## Google Interview Question

Software Engineer / Developers**Team:**Autocomplete

**Country:**United States

**Interview Type:**Written Test

Here is code:

```
void UpdateQAZ(int low, int mid, int high)
{
int i,j;
added_qaz = 0;
i = mid;
j = high;
while ( ( i >= 0 ) && ( j > mid ) )
{
if ( A[ j ] > A[ i ] )
{
added_qaz++;
j--;
}
else
{
A[ i ].qaz += added_qaz;
i--;
}
}
if ( j <= mid )
{
for ( x = i ; x >=low ; x-- )
{
A[ x ].qaz += added_qaz;
}
}
}
```

Modified the MergeSort algorithm for this problem - Time Complexity - O(nlogn)

```
#include<utility>
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<int, int> q;
unordered_map<int, int> initializeQAZ(vector<int> &A, int vsize)
{
unordered_map<int, int> qaz;
for(int i = 0; i < vsize; i++)
{
qaz[A[i]] = 0;
}
return qaz;
}
vector<int> merge_sort(vector<int> &l, vector<int> &r)
{
vector<int> result;
unsigned left_it = 0, right_it = 0;
while(left_it < l.size() && right_it < r.size())
{
if(l[left_it] < r[right_it])
{
result.push_back(l[left_it]);
q[l[left_it]] += (r.size() - right_it);
left_it++;
}
else
{
result.push_back(r[right_it]);
right_it++;
}
}
while(left_it < l.size())
{
result.push_back(l[left_it]);
left_it++;
}
while(right_it < r.size())
{
result.push_back(r[right_it]);
right_it++;
}
return result;
}
vector<int> mergeSort(vector<int> &A)
{
if(A.size() == 1)
return A;
vector<int>::iterator middle = A.begin() + A.size()/2;
vector<int> leftV(A.begin(), middle);
vector<int> rightV(middle, A.end());
leftV = mergeSort(leftV);
rightV = mergeSort(rightV);
return merge_sort(leftV, rightV);
}
int main(int argc, char** argv)
{
int B[] = {33, 25, 26, 58, 41, 59};
vector<int> A(B, B + sizeof(B) / sizeof(B[0]));
q = initializeQAZ(A, A.size());
vector<int> sortedA = mergeSort(A);
for(int i = 0; i < A.size(); i++)
{
cout << A[i] << " ";
}
cout << endl;
for(int i = 0; i < sortedA.size(); i++)
{
cout << sortedA[i] << " ";
}
cout << endl;
for(int i = 0; i < A.size(); i++)
{
cout << A[i] << " " << q[A[i]] << endl;
}
return 0;
}
```

This is another MergeSort-like solution in Java, that just tries to be easier to read.

It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

```
public class QAZ {
public static void main(String[] args) {
int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
System.out.println(getMaxQAZ(array));
}
public static int getMaxQAZ(int[] array){
if (array == null) {
return 0;
}
return getMaxQAZ(array, 0, array.length).qaz;
}
private static QAZResult getMaxQAZ(int[] array, int start, int end) {
if (end - start <= 3) {
return getLastLocalMaxQAZ(array, start, end);
}
int middle = (end + start) / 2;
QAZResult leftResult = getMaxQAZ(array, start, middle);
QAZResult rightResult = getMaxQAZ(array, middle, end);
if (leftResult.minVal < rightResult.minVal) {
return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
}
for (int i = middle; i < end; i++) {
if (leftResult.minVal < array[i]) {
leftResult.qaz++;
}
}
return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;
}
private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){
int minVal = array[start];
int qaz = 0;
for (int i = start + 1; i < end; i++) {
if (array[i -1] < array[i]) {
qaz++;
} else {
minVal = array[i];
}
}
return new QAZResult(minVal, qaz);
}
}
class QAZResult {
int minVal;
int qaz;
public QAZResult(int minVal, int qaz) {
this.minVal = minVal;
this.qaz = qaz;
}
}
```

Does this work for {7, 8, 2, 3, 4, 5}? The Answer Should be 3, but i believe your program produces 4?

If input is {4, 33 , 25 , 26 , 58 , 41 , 59 }, your code returns 4. Right answer should be 6.

This is really easy and nice approach with small flaw in it. Better to keep the granularity to 2 while dividing, the merging works perfect. Here is the updated code:

```
public class HelloWorld {
public static void main(String[] args) {
int[] array = {7, 8, 2, 3, 4, 5 };
System.out.println(getMaxQAZ(array));
}
public static int getMaxQAZ(int[] array){
if (array == null) {
return 0;
}
return getMaxQAZ(array, 0, array.length-1).qaz;
}
private static QAZResult getMaxQAZ(int[] array, int start, int end) {
if (end <= start) {
return new QAZResult(array[end], 0);
}
if (end == start+1) {
if (array[start] < array[end]) {
return new QAZResult(array[start], 1);
}
return new QAZResult(array[end], 0);
}
int middle = (end + start) / 2;
QAZResult leftResult = getMaxQAZ(array, start, middle);
QAZResult rightResult = getMaxQAZ(array, middle+1, end);
if (leftResult.minVal < rightResult.minVal) {
return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
}
for (int i = middle; i < end; i++) {
if (leftResult.minVal < array[i]) {
leftResult.qaz++;
}
}
return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;
}
}
class QAZResult {
int minVal;
int qaz;
public QAZResult(int minVal, int qaz) {
this.minVal = minVal;
this.qaz = qaz;
}
}
```

To pavelkushtia,

This is not a correct solution!

What Anselmo said about "It is based on the observation that the element that holds the max QAZ is a local minimum of the array" is not correct.

For example, for array = { 25, 33, 26, 58, 41, 59, 4 }. The minimum of array is 4. the QAZ of 4 is 0. Obviously, the QAZ of this array is from 25, which is 5.

You should try this test case in your code and see the result.

Allen,

my code had a couple of minor bugs that Pavelkushtia noticed and fixed brilliantly (thanks Pavel!).

But the implant of my solution, I believe, is substantially correct and the observation about local minimums is correct as well.

A local minimum of a function is a different concept than absolute minimum. In the array you posted: { 25, 33, 26, 58, 41, 59, 4 }, 4 is a local and absolute minimum, but 25 is another local minimum.

A local minimum needs to be smaller or equal to the values besides it, is any, that's it.

Now think again, and you will see that the max QAZ holder needs to be a local minimum.

modified merge sort is nice solution.

I do have 1 more algo which is having complexity : O(nlogn).

say array is

A [] = { 33 , 25 , 26 , 58 , 41 , 59}

step 1 : create ArrayList of size = A.length

step 2 : sort ArrayList in ascending order O(nlog(n))

ArrayList => { 25 , 26 , 33, 41, 58 , 59 }

step 3 : choose 1st element of A[] ie 33

=> qaz(33) => total elements in ArrayList after 33

=> qaz(33) = 3

remove element 33 from ArrayList

now ArrayList = {25 , 26 , 41, 58 , 59 }

step 4: choose next element from A[] ie 25

=> qaz(25) = total elements in ArrayList after 25

=> qaz(25) = 4

remove element 25 from ArrayList

now ArrayList = {26 , 41, 58 , 59 }

step 5: choose next element from A[] ie 26

=> qaz(26) = total elements in ArrayList after 26

=> qaz(26) = 3

remove element 26 from ArrayList

now ArrayList = {41, 58 , 59 }

step 6: choose next element from A[] ie 58

=> qaz(58) = total elements in ArrayList after 58

=> qaz(58) = 1

remove element 58 from ArrayList

now ArrayList = {41 , 59 }

step 7: choose next element from A[] ie 41

=> qaz(41) = total elements in ArrayList after 41

=> qaz(41) = 1

remove element 41 from ArrayList

now ArrayList = { 59 }

last step: choose next element from A[] ie 59

=> qaz(59) = total elements in ArrayList after 59

=> qaz(59) = 0

remove element 59 from ArrayList

now ArrayList = {}

are you physically removing items from ArrayList ? if yes, then it'd be O(n), if No, then finding number of elements after a certain element is again O(n),

your algorithm works, but I'm afraid it's O(n^2)

thanks Koosha ,

As the array list is already sorted, we can use binary search ( O(logn) ) for finding the index of element to be removed.

once the index of element is known then deletion is O(1) .

Similarly Binary search can be used for finding number of elements after a certain element .

Hence the over all complexity would be O(nlogn) only!

How the delete operation can take O(1)?

Doesn't the delete required to shifts any elements after the index to the left ?

@Boris : sorted elements are stored in ArrayList , but not in array. And arrayList tooks O(1) for delete operation

If I'm not mistaken, you are removing the element logically, which takes O(1); in the case when you remove 33 from { 25 , 26 , 33, 41, 58 , 59 } , you will have

{ 25 , 26 , NULL, 41, 58 , 59 }, now finding elements after 25 (step 4) will be O(n)

yes koosha you are correct.

Is there any method in O(logn) to determine number of elements after specific element in sorted list excluding ones that are already processed?

You should think the difference between array and list.

array - can use binary search but delete costs O(n)

list - the time complexity of binary search for the linked list is not nLogn since it takes O(n/2) to find mid of the list.

```
I think this is the right idea or approach especially during a 40 min interview. The merge-sort like solutions are great but i doubt many people can code those cleanly under duress and mistake-free.
Here is what I came up with to correct the slow search:
MAX-QAZ ( int[] array )
1. maxQaz = 0
2. Q = PRIORITY-QUEUE
3. for i = array.length - 1 to 0 // starts from the back
4. index pos = Q.insert ( array[i] ) // this Q returns the index of the element
5. qaz = Q.size - pos
6. if qaz > maxQaz
7. maxQaz = qaz
8. return maxQaz
```

```
MAXIMUM-QUAZ ( int[] array )
1. MaxQaz = 0
2. Q = PRIORITY-QUEUE
3. for i = array.length - 1 to 0
4. index = Q.insert ( array [ i ] ) // return index of newly inserted element
5. qaz = Q.size - index
6. if ( qaz > MaxQaz )
7. MazQaz = qaz
8. return MazQaz
```

```
MAXIMUM-QUAZ ( int[] array )
1. MaxQaz = 0
2. Q = PRIORITY-QUEUE
3. for i = array.length - 1 to 0
4. index = Q.insert ( array [ i ] ) // return index of newly inserted element
5. qaz = Q.size - index
6. if ( qaz > MaxQaz )
7. MazQaz = qaz
8. return MazQaz
```

This is another MergeSort-like solution in Java, that just tries to be easier to read.

It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

```
public class QAZ {
public static void main(String[] args) {
int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
System.out.println(getMaxQAZ(array));
}
public static int getMaxQAZ(int[] array){
if (array == null) {
return 0;
}
return getMaxQAZ(array, 0, array.length).qaz;
}
private static QAZResult getMaxQAZ(int[] array, int start, int end) {
if (end - start <= 3) {
return getLastLocalMaxQAZ(array, start, end);
}
int middle = (end + start) / 2;
QAZResult leftResult = getMaxQAZ(array, start, middle);
QAZResult rightResult = getMaxQAZ(array, middle, end);
if (leftResult.minVal < rightResult.minVal) {
return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
}
for (int i = middle; i < end; i++) {
if (leftResult.minVal < array[i]) {
leftResult.qaz++;
}
}
return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;
}
private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){
int minVal = array[start];
int qaz = 0;
for (int i = start + 1; i < end; i++) {
if (array[i -1] < array[i]) {
qaz++;
} else {
minVal = array[i];
}
}
return new QAZResult(minVal, qaz);
}
}
class QAZResult {
int minVal;
int qaz;
public QAZResult(int minVal, int qaz) {
this.minVal = minVal;
this.qaz = qaz;
}
}
```

Since they want O(nlogn) they probably want something to do with sorting or divide and conquer. My solution is merge sort, but you have another array storing counts :

Lets call the original array A, and the max array Max

1. Recursively cut the array in half like in merge sort

2. Merge Process:

Let's assume leftIndex is the starting index of the left side and rightIndex is the starting of the right side. Lets say endRight is the end of the right and endLeft is end of left.

1. Check to see whether the starting index of the right side or left side is bigger.

2. If the left side is bigger, update Max[leftIndex] += endLeft - rightIndex. Then do the swapping in the same way you would for both arrays.

3. If the right side is bigger, just do the swapping for both array like you would normally.

Once you are done you can just search for the biggest number in Max[], which would take O(n). So the complexity is nLgn + n, or O(nLgn).

I wonder if there is a way to do this without an extra array. You can probably keep track of the max during the merge process so you can cut out the last O(n) operation. Let me know if I made any mistakes!

hi, I think you are in the right way, but can you please code it ( write a code ).

if you can show us what is happening in each step.

they ask me to write a code.

The code is kind of big to write, but I pretty much rewrote Merge sort and added a little extra so it wasn't too bad. Obviously I had the luxury of a IDE, but the interviewer should steer you in the right direction if you make any mistakes.

```
static public int maxQaz(int[] A) {
int[] max = new int[A.length];
return mergeQazUtil(A, max, 0, A.length - 1);
}
static public int mergeQazUtil(int[] A, int[] Max, int start, int end) {
if(start == end) return 0;
int mid = (start + end)/2;
int leftRes = mergeQazUtil(A, Max, start, mid);
int rightRes = mergeQazUtil(A, Max, mid + 1, end);
int merged = merge(A, Max, start, end, mid);
return Math.max(leftRes, Math.max(rightRes, merged));
}
static public int merge(int[] A, int[] Max, int start, int end, int mid) {
int[] AHelper = new int[A.length];
int[] MaxHelper = new int[Max.length];
for(int i = 0; i < A.length; i++) {
AHelper[i] = A[i];
MaxHelper[i] = Max[i];
}
int leftStart = start, leftEnd = mid, rightStart = mid + 1, rightEnd = end;
int index = start;
int max = 0;
while(leftStart <= leftEnd && rightStart <= rightEnd) {
int curMax = 0;
//this is assuming no numbers are equal
if(AHelper[leftStart] < AHelper[rightStart]) {
MaxHelper[leftStart] += (rightEnd - rightStart) + 1;
curMax = MaxHelper[leftStart];
A[index] = AHelper[leftStart];
Max[index] = MaxHelper[leftStart];
leftStart++;
} else {
A[index] = AHelper[rightStart];
Max[index] = MaxHelper[rightStart];
rightStart++;
}
if(curMax > max) max = curMax;
index++;
}
if(index <= end) {
A[index] = AHelper[leftStart];
Max[index] = MaxHelper[leftStart];
}
return max;
}
```

Not enough time to complete the code, but this is the basic idea. We modify merge sort, so that whenever we add in an element from "the left side", we will add the difference between the end of the right side and the right side iterator to a hashed stored value for the element's qez.

For example, if we merge:

[11, 10, 5, 12, 20]

Our steps look like this:

[11, 10] -> [10, 11], No QEZ

[5, 12] -> QEZ of 5 is 1

[5, 12], [20] -> QEZ of 5 increases by 1, QEZ of 12 becomes 1

now when we merge

[10, 11] and [5, 12, 20]

[5] -> no QEZ change

[5,10] -> QEZ of 10 is now 2 because right pointer is pointing at 12

[5, 10, 11] -> QEZ of 11 is 2 because right pointer is pointing at 12

[5, 10, 11, 12, 20] -> No QEZ change for 12 and 20 since while loop ends the merge

Not enough time to complete the code, but the basic gist of the merge method is like this:

end refers to the location of the end of right pointer so in the case of [10, 11] and [5, 12, 20], right would be = to 2 and end would be equal to 2 + 2 = 4.

Sorry, again for incompleteness

```
merge(int[] arr, int[] new, int l, int r, int end, HashMap hm) {
boolean done = false;
int i = l;
int j = r;
int k = l;
while(!done) {
if (arr[left] >= arr[right]) {
new[k++] = arr[j++];
//handle ending case of merge here
}
else {
new[k++] = arr[j++];
hm.put(arr[k], hm.get(arr[k] + (end - j)) );
}
}
}
```

This can be helpful:

a recursive function which returns a TreeMap<Integer,Integer> where it contains the number and the qaz of this number.

this function divide each time the array into 2 sub-arrays and then merge them, iterate the left tree map and for each number , do a binary search to find the first larger number than this number the add to the value of this number -> rightTreeMap.size()-1-(the index of the number) and so on.

I think this is just O(n). Keep 2 pairs. One has smallest number and one has max qaz. Update them while traversing the array. Am I missing something?

```
#include <stdio.h>
struct Pair
{
int v;
int qaz;
Pair(int _v = 0, int _qaz = 0): v(_v), qaz(_qaz){}
};
void findMaxQaz(int v[], int len)
{
Pair smallest(v[0], 0);
Pair maxQaz(v[0], 0);
for (int i = 1; i < len; ++i)
{
if (v[i] > smallest.v)
{
smallest.qaz++;
}
else
{
smallest.qaz = 0;
smallest.v = v[i];
}
if (v[i] > maxQaz.v)
{
maxQaz.qaz++;
}
if (smallest.qaz > maxQaz.qaz)
{
maxQaz.v = smallest.v;
maxQaz.qaz = smallest.qaz;
}
}
printf("%d qaz:%d", maxQaz.v, maxQaz.qaz);
}
int main()
{
//int v[] = {2, 3, 1, 4, 5};
int v[] = {33 , 25 , 26 , 1 , 5 ,6 ,7 ,9 , 14 ,20,21,23,29};
findMaxQaz(v, sizeof(v)/sizeof(int));
return 0;
}
```

No, there is a problem.

For {33, 34, 21, 22, 20, 23, 19, 24, 21, 22}, it gives 19 qaz:3 when correct answer is 21 qaz:4.

Fundamental problem in your solution. Suppose, we can find QAZ of all elements in O(n). By reversing array, finding QAZ and reversing it once again we can find QAZ in "opposite direction" in O(n). By adding this values for each elements we can figure out how many elements in array are lesser than this element, i.e. position of this element in sorted array. In O(n).

Than, applying a permutation to initial array (can be done in O(n)) we get sorted arry in O(n), which is impossible, as you know.

Walk the array in reverse, inserting values into a min-oriented heap as you go. The 'qaz' for each number is the number of elements beneath it in the heap when you insert it. Keep track of the max qaz after each insertion. This will be an O(n log n) algorithm.

Could you please elaborate? how do you take care of the following case:

1- let's say a number smaller than all the existing numbers is entered, that number will be at the top of the heap, and the qaz of that number should be zero, but your algorithm suggests something else,

For every element when you traverse a heap to update values doesnt that have a higher complexity that nLogn

Traversing the array in reverse and inserting into heap will not give the correct answer, let's assume a number, say x, is inserted and x is NOT the smallest number so far, the qaz of x would be all the numbers greater than x, but the number of elements beneath x in the heap doesn't represent ALL the numbers that are greater than x

how about this:

sort the array, scan the sorted array, for each item i, let ans = max(ans, size - i - ori_i) where ori_i is the original index of the item.

This is another MergeSort-like solution in Java, that just tries to be easier to read.

It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

```
public class QAZ {
public static void main(String[] args) {
int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
System.out.println(getMaxQAZ(array));
}
public static int getMaxQAZ(int[] array){
if (array == null) {
return 0;
}
return getMaxQAZ(array, 0, array.length).qaz;
}
private static QAZResult getMaxQAZ(int[] array, int start, int end) {
if (end - start <= 3) {
return getLastLocalMaxQAZ(array, start, end);
}
int middle = (end + start) / 2;
QAZResult leftResult = getMaxQAZ(array, start, middle);
QAZResult rightResult = getMaxQAZ(array, middle, end);
if (leftResult.minVal < rightResult.minVal) {
return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
}
for (int i = middle; i < end; i++) {
if (leftResult.minVal < array[i]) {
leftResult.qaz++;
}
}
return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;
}
private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){
int minVal = array[start];
int qaz = 0;
for (int i = start + 1; i < end; i++) {
if (array[i -1] < array[i]) {
qaz++;
} else {
minVal = array[i];
}
}
return new QAZResult(minVal, qaz);
}
}
class QAZResult {
int minVal;
int qaz;
public QAZResult(int minVal, int qaz) {
this.minVal = minVal;
this.qaz = qaz;
}
}
```

It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

```
public class QAZ {
public static void main(String[] args) {
int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
System.out.println(getMaxQAZ(array));
}
public static int getMaxQAZ(int[] array){
if (array == null) {
return 0;
}
return getMaxQAZ(array, 0, array.length).qaz;
}
private static QAZResult getMaxQAZ(int[] array, int start, int end) {
if (end - start <= 3) {
return getLastLocalMaxQAZ(array, start, end);
}
int middle = (end + start) / 2;
QAZResult leftResult = getMaxQAZ(array, start, middle);
QAZResult rightResult = getMaxQAZ(array, middle, end);
if (leftResult.minVal < rightResult.minVal) {
return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
}
for (int i = middle; i < end; i++) {
if (leftResult.minVal < array[i]) {
leftResult.qaz++;
}
}
return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;
}
private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){
int minVal = array[start];
int qaz = 0;
for (int i = start + 1; i < end; i++) {
if (array[i -1] < array[i]) {
qaz++;
} else {
minVal = array[i];
}
}
return new QAZResult(minVal, qaz);
}
}
class QAZResult {
int minVal;
int qaz;
public QAZResult(int minVal, int qaz) {
this.minVal = minVal;
this.qaz = qaz;
}
}
```

```
struct qaz_pair
{
int value;
size_t index;
};
bool operator < (const qaz_pair& lhs, const qaz_pair& rhs)
{
return lhs.value < rhs.value;
}
int qaz(const vector<int>& numbers, int number)
{
// O(n)
vector<qaz_pair> tmp;
for (const auto n : numbers )
tmp.push_back( qaz_pair{ n, tmp.size() } );
// O(nlogn)
sort(tmp.begin(), tmp.end());
qaz_pair number_pair;
number_pair.value = number;
auto found = lower_bound(tmp.begin(), tmp.end(), number_pair);
if (tmp.end() == found || found->value != number)
return -1;
// O(n)
int result = 0;
int previous = found->value;
const size_t index = found->index;
for (; tmp.end() != found ; previous = found->value, ++found )
{
if (found->index > index)
if (previous != found->value)
result++;
}
return result;
}
void Google6()
{
const vector<int> numbers { 33 , 25 , 26, 26 , 58 , 41, 41 , 59, 59 };
assert( -1 == qaz(numbers, 0) );
assert( -1 == qaz(numbers, 100) );
assert( 3 == qaz(numbers, 33) );
assert( 4 == qaz(numbers, 25) );
assert( 3 == qaz(numbers, 26) );
assert( 1 == qaz(numbers, 58) );
assert( 1 == qaz(numbers, 41) );
assert( 0 == qaz(numbers, 59) );
}
```

If we know for an array (having N elements) index i (0<=i<N), the number of elements which are smaller than array[i], say X, then the QAZ value of array[i] = (N-i-1)-X.

The number of elements smaller than array[i], say X, will introduce X array inversions to the right of index i. So we can just count the number of inversions at index i and calculate the QAZ value keeping track of the maximum. Since this is reduced to counting inversions we can of course use a modified merge sort algorithm but I suggest using a Fenwick tree which is much simpler to code. Complexity: O(nlogn).

Here's the code to elaborate:

```
public void solve(int[] A){
int N = A.length;
int[] bit = new int[N+1];
int[] rank = Arrays.copyOf(A, N);
Arrays.sort(rank);
for (int i = 0; i < A.length; i++) {
int idx = Arrays.binarySearch(rank, A[i]);
A[i] = idx+1;
}
int maxQAZ = Integer.MIN_VALUE;
for(int i=N-1;i>=0;i--)
{
int qaz = (N-i-1) - read(bit, A[i]-1);
maxQAZ = Math.max(maxQAZ, qaz);
update(bit, A[i],1,N);
}
System.out.println(maxQAZ);
}
private int read(int[] bit, int idx){
int sum=0;
while (idx>0)
{
sum += bit[idx];
idx -= (idx & -idx);
}
return sum;
}
private void update(int[] bit, int idx, int val, int max){
while (idx <= max)
{
bit[idx] += val;
idx += (idx & -idx);
}
}
```

I couldn't understand how your algorithm works, but how do you prove O(nlogn)?

for(int i=N-1;i>=0;i--) => O(N) and it calls the function "Update", to maintain O(nlogn), the complexity of the function "Update" must be equal or smaller than O(logn), How do you prove that?

The number of iterations in both read & update methods is the number of set bits in the "idx" parameter which is at max log N.

The line idx&(-idx) isolates the last set bit in idx.

Shorter algo based on the observation that the qaz(#i) = max(0, order of #i in the sorted array - #i).

```
int maxQaz(const vector<int> &v) {
vector<pair<int, int> > pv;
int n = v.size();
for (int i = 0; i < n; i++) {
pv.push_back(make_pair(v[i], i));
}
stable_sort(pv.begin(), pv.end());
reverse(pv.begin(), pv.end());
int ret = 0; // when input is empty, result is 0.
for (int i = 0; i < n; i++) {
ret = max(ret, i - pv[i].second);
}
return ret;
}
```

As many people discussed, a O(nlogn) solution can be achieved by merge sort. Please check my analysis and solution: allenlipeng47.com/PersonalPage/index/view/126/nkey

```
package feb;
public class QAZ {
public static void main(String[] args) {
int[] arr = { 7, 8, 2, 3, 4, 5 };
int qaz = qaz(arr);
System.out.println(qaz);
}
public static int qaz(int[] arr) {
int[] eleTimes = new int[arr.length];
int[] helperQaz = new int[arr.length];
int[] helperTimes = new int[arr.length];
return qazUtil(arr, eleTimes, 0, arr.length - 1, helperQaz, helperTimes);
}
public static int qazUtil(int[] arr, int[] eleTimes, int start, int end,
int[] helperQaz, int[] helperTimes) {
if (start > end) {
return 0;
}
if (start == end) {
return 0;
}
int mid = start + (end - start) / 2;
int qazLeft = qazUtil(arr, eleTimes, start, mid, helperQaz, helperTimes);
int qazRight = qazUtil(arr, eleTimes, mid + 1, end, helperQaz,
helperTimes);
// 1. Update eleTimes in left part.
int pointerL = mid, pointerR = end;
int added = 0;
while (pointerL >= start) {
while (arr[pointerL] < arr[pointerR] && pointerR >= mid + 1) {
pointerR--;
added++;
}
eleTimes[pointerL] += added;
qazLeft = (eleTimes[pointerL] > qazLeft) ? eleTimes[pointerL]
: qazLeft;
pointerL--;
}
// 2. Mergesort left and right part into helperQaz, helperTimes
pointerL = start;
pointerR = mid + 1;
int helpIndex = start;
while (pointerL <= mid && pointerR <= end) {
if (arr[pointerL] < arr[pointerR]) {
helperQaz[helpIndex] = arr[pointerL];
helperTimes[helpIndex] = eleTimes[pointerL];
pointerL++;
} else {
helperQaz[helpIndex] = arr[pointerR];
helperTimes[helpIndex] = eleTimes[pointerR];
pointerR++;
}
helpIndex++;
}
while (pointerL <= mid) {
helperQaz[helpIndex] = arr[pointerL];
helperTimes[helpIndex] = eleTimes[pointerL];
pointerL++;
helpIndex++;
}
while (pointerR <= end) {
helperQaz[helpIndex] = arr[pointerR];
helperTimes[helpIndex] = eleTimes[pointerR];
pointerR++;
helpIndex++;
}
// 2.2 Copy result from helperQaz, helperTimes back to arr, eleTimes
for (int i = start; i <= end; i++) {
arr[i] = helperQaz[i];
eleTimes[i] = helperTimes[i];
}
return Math.max(qazLeft, qazRight);
}
}
```

How about ~20 LOC in java:

```
import java.util.*;
public class QAZ {
static int findMaxQaz(List<Integer> list) {
TreeSet<Integer> set = new TreeSet<>();
int maxQaz = -1, maxVal = -1;
Collections.reverse(list);
for (int i : list) {
set.add(i);
int qaz = set.tailSet(i).size();
if (maxQaz < qaz) {
maxVal = i;
maxQaz = qaz;
}
}
return maxVal;
}
public static void main(String[] args) {
List<Integer> list = Arrays.asList(88, 77, 6, 5, 4, 3);
System.out.println(findMaxQaz(list));
}
}
```

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

alternate solution (not using merge sort):

Step1:

Make a second list and sort that list but keep track of where each element in the sorted list is stored within the original list.

[n log n, for the sorted list you can use a class that has a number as one class variables and "position in original list" as a second class variable]

Step 2:

Starting at the first element of the sorted list, for each element i, take

min ((n-1)-sortedListPosition, (n-1)-originalListPosition)

This is the myMaxPossibleQaz (weird name to make writing later easier),

the first item is the number of elements greater than the current element in the list as a whole,

the second item is the qaz assuming that all elements after the position of the current element in the original list are greater than the current element if all elements after element i within the original list are greater

The min of these is the highest possible qaz (given the set and the position of the current element in the original set). The highest possible qaz is lowered every time a smaller element is in front of i).

Make a list of these myMaxPossibleQaz values (or add another class variable to the objects within the sorted list) [n time].

Step 3.0

Going through each element i in the sorted list and keep track of the farthest left original position so far (this is because, any future elements in the sorted list that have an original position greater than this will definitely have a greater qaz, so we can ignore them. They will have a greater qaz because, in the original list, they appear after at least one number that they are greater than, so whatever their qaz is, the earlier number will have at least their qaz + 1)

Step 3.5

If future elements within the sorted list have an earlier position within the original list than we have seen so far then their qaz is

myMaxPossibleQaz - mySortedListPosition

This is because maxPossibleQaz is reduced by having numbers that are smaller than you appear after you in the original list, and every element so far has been smaller than the current element and after the current element in the original list.

So when iterating through the sorted list if the elements are to the right of the leftmost original position seen so far, we move on, if they are to the left, we update the leftmost seen position and calculate the qaz using the (myPossibleQaz - mySortedListPosition) formula.

Step 3.0 and 3.5 (well, same step, but two different cases) take n time. Calculating qaz is instant (when the qaz can possibly be larger than something we've seen so far. When it could be smaller, we ignore it).

{{

std::pair<int,int> qaz(int* A, int len)

{

std::vector<std::pair<int,int>> VA;

for(int i = 0; i < len; ++i)

VA.push_back(std::make_pair(A[i], i));

std::sort(VA.begin(), VA.end()); O(n log n)

std::pair<int,int> B = std::make_pair(-1,-1);

for(int i = len-1; i >= 0; --i) //O(n)

{

int v = std::min(len-(VA[i].second+1), len-(i+1));

if(v > B.second)

{

B = VA[i];

B.second = v;

}

}

return B;

}

}}

I would think that replacing std::sort with a radix sort would even give a O(n) solution.

qaz problem is just longest incrementing subsequence in diguise.

There is a solution to this problem in O(nlogn).

Consider { 10,11,12,13,1,14,15,16,17}

QAZ(10) = 7

longest incrementing sub sequence = { 10,11,12,13 }

```
# n squared qaz solution
def qaz(data):
n = len(data)
max_counter = 0
elements = []
for i in range(0,n):
candidate_counter = 0
for j in range(i + 1,n):
if data[j] > data[i]:
candidate_counter += 1
if candidate_counter > max_counter:
max_counter = candidate_counter
del elements[:]
elements.append(data[i])
elif candidate_counter == max_counter:
elements.append(data[i])
return max_counter, elements[0]
##### This is nlogn solution in case you replace the data structure which holds the local minimums with an AVL tree.
##### I did not use an AVL tree since it is easier to understand the solution this way.
##### in the worst case we are doing a binary search ~n times to find max over all candidates which is smaller then new value in case it is bigger the min over all minimums.
##### so nlogn in the worst case. This is not optimal since deleting from an array may result linear time while deleting from AVL will result logarithmic time.
##### a tester which validates against the trivial solution runs.
##### By the way it took a day to think about and implement.could not have done it in an interview.
class QAZcandidate(object):
def __init__(self, value):
self.value = value
self.rankUP = 0
self.rankDOWN = 0
def find_max_smaller_minimum(data,key, index=0):
if len(data) == 0:
return data[0], index
middle = len(data)/2
element = data[middle]
if element.value > key:
return find_max_smaller_minimum(data[middle:],key,index + middle)
else:
#element.value < key
if middle > 0:
if data[middle - 1].value < key:
return find_max_smaller_minimum(data[0:middle],key,index)
else:
#we found max smaller minimum
return data[middle], middle + index
#element.value < key and its the largest minimum
else:
return data[middle], middle + index
def qaz_hard(data):
if len(data) <= 1:
return
local_minimals = []
local_minimals_last_minimal_index = 0
array_minimal_index = 0
local_minimals.append(QAZcandidate(value=data[0]))
for i in range(1,len(data)):
if data[i] < local_minimals[local_minimals_last_minimal_index].value:
# we overwrite the previous suspected local minimal
if array_minimal_index + 1 == i:
local_minimals[local_minimals_last_minimal_index] = QAZcandidate(value=data[i])
array_minimal_index += 1
continue
else:
# new candidate for a wining local minimum
local_minimals.append(QAZcandidate(value=data[i]))
local_minimals_last_minimal_index += 1
array_minimal_index = i
continue
# data[i] > local_minimals[last_minimal_index].value
else:
# need to find maximum over all minimums which are smaller then data[i]
max_smaller_minimum_element, max_smaller_minimum_element_index = find_max_smaller_minimum(local_minimals,data[i])
# one candidate.
if max_smaller_minimum_element is local_minimals[0]:
local_minimals[local_minimals_last_minimal_index].rankDOWN += 1
# last element
elif max_smaller_minimum_element is local_minimals[local_minimals_last_minimal_index]:
max_smaller_minimum_element.rankUP += 1
max_smaller_minimum_element.rankDOWN += 1
# element in the middle so improves position against previous elements and last minimum gains advantage against future elements
else:
max_smaller_minimum_element.rankUP += 1
local_minimals[local_minimals_last_minimal_index].rankDOWN += 1
# check if need to update winner
if max_smaller_minimum_element is not local_minimals[0]:
prev_candidate = local_minimals[max_smaller_minimum_element_index - 1]
#we improve ranking
if max_smaller_minimum_element.rankUP >= prev_candidate.rankDOWN:
local_minimals = local_minimals[0:max_smaller_minimum_element_index - 1] + local_minimals[max_smaller_minimum_element_index:]
local_minimals_last_minimal_index -= 1
# max smaller minimum element is the first one so everybody gains
else:
pass
x = local_minimals[0].value
i = 0
while data[i] != x:
i += 1
counter = 0
j = i+1
while j < len(data):
if data[j] > x:
counter += 1
j += 1
return counter, local_minimals[0].value
if __name__ == "__main__":
import random
for i in range(0,10):
d = random.sample(range(1000), 1000)
c1, val1 = qaz(d)
c2, val2 = qaz_hard(d)
if c1 != c2:
print "error"
print str(d)
print "easy: qaz:"+str(c1)+" val:"+str(val1)
print "hard: qaz:"+str(c2)+" val:"+str(val2)
else:
print "ok"
```

```
# n squared qaz solution
def qaz(data):
n = len(data)
max_counter = 0
elements = []
for i in range(0,n):
candidate_counter = 0
for j in range(i + 1,n):
if data[j] > data[i]:
candidate_counter += 1
if candidate_counter > max_counter:
max_counter = candidate_counter
del elements[:]
elements.append(data[i])
elif candidate_counter == max_counter:
elements.append(data[i])
return max_counter, elements[0]
##### This is nlogn solution in case you replace the data structure which holds the local minimums with an AVL tree.
##### I did not use an AVL tree since it is easier to understand the solution this way.
##### in the worst case we are doing a binary search ~n times to find max over all candidates which is smaller then new value in case it is bigger the min over all minimums.
##### so nlogn in the worst case. This is not optimal since deleting from an array may result linear time while deleting from AVL will result logarithmic time.
##### a tester which validates against the trivial solution runs.
##### By the way it took a day to think about and implement.could not have done it in an interview.
class QAZcandidate(object):
def __init__(self, value):
self.value = value
self.rankUP = 0
self.rankDOWN = 0
def find_max_smaller_minimum(data,key, index=0):
if len(data) == 0:
return data[0], index
middle = len(data)/2
element = data[middle]
if element.value > key:
return find_max_smaller_minimum(data[middle:],key,index + middle)
else:
#element.value < key
if middle > 0:
if data[middle - 1].value < key:
return find_max_smaller_minimum(data[0:middle],key,index)
else:
#we found max smaller minimum
return data[middle], middle + index
#element.value < key and its the largest minimum
else:
return data[middle], middle + index
def qaz_hard(data):
if len(data) <= 1:
return
local_minimals = []
local_minimals_last_minimal_index = 0
array_minimal_index = 0
local_minimals.append(QAZcandidate(value=data[0]))
for i in range(1,len(data)):
if data[i] < local_minimals[local_minimals_last_minimal_index].value:
# we overwrite the previous suspected local minimal
if array_minimal_index + 1 == i:
local_minimals[local_minimals_last_minimal_index] = QAZcandidate(value=data[i])
array_minimal_index += 1
continue
else:
# new candidate for a wining local minimum
local_minimals.append(QAZcandidate(value=data[i]))
local_minimals_last_minimal_index += 1
array_minimal_index = i
continue
# data[i] > local_minimals[last_minimal_index].value
else:
# need to find maximum over all minimums which are smaller then data[i]
max_smaller_minimum_element, max_smaller_minimum_element_index = find_max_smaller_minimum(local_minimals,data[i])
# one candidate.
if max_smaller_minimum_element is local_minimals[0]:
local_minimals[local_minimals_last_minimal_index].rankDOWN += 1
# last element
elif max_smaller_minimum_element is local_minimals[local_minimals_last_minimal_index]:
max_smaller_minimum_element.rankUP += 1
max_smaller_minimum_element.rankDOWN += 1
# element in the middle so improves position against previous elements and last minimum gains advantage against future elements
else:
max_smaller_minimum_element.rankUP += 1
local_minimals[local_minimals_last_minimal_index].rankDOWN += 1
# check if need to update winner
if max_smaller_minimum_element is not local_minimals[0]:
prev_candidate = local_minimals[max_smaller_minimum_element_index - 1]
#we improve ranking
if max_smaller_minimum_element.rankUP >= prev_candidate.rankDOWN:
local_minimals = local_minimals[0:max_smaller_minimum_element_index - 1] + local_minimals[max_smaller_minimum_element_index:]
local_minimals_last_minimal_index -= 1
# max smaller minimum element is the first one so everybody gains
else:
pass
x = local_minimals[0].value
i = 0
while data[i] != x:
i += 1
counter = 0
j = i+1
while j < len(data):
if data[j] > x:
counter += 1
j += 1
return counter, local_minimals[0].value
if __name__ == "__main__":
import random
for i in range(0,10):
d = random.sample(range(1000), 1000)
c1, val1 = qaz(d)
c2, val2 = qaz_hard(d)
if c1 != c2:
print "error"
print str(d)
print "easy: qaz:"+str(c1)+" val:"+str(val1)
print "hard: qaz:"+str(c2)+" val:"+str(val2)
else:
print "ok"
```

Another approach is to build a binary search tree while adding the elements in the array from right to left (end to start). This works because:

1. Each time we go "down the tree" to the left all the elements in the tree above are larger than the current one so, add 1 + count the number of elements on the right side of the parent node.

2. When going "down the tree" to the right, the prev. element is small than the current one so don't count it.

3. For n elements we are traversing the tree which is max logN in height there for o(nlogn)

```
public int findMaxQaz(int[] buff) {
int max = 0;
int qaz = 0;
// create the root
TreeNode<int> root = new TreeNode(buff[buff.length-1]);
TreeNode<int> node = root;
for(int index=buff.length-2; index>=0; index--) {
if(buff[index] < node.value) {
qaz += countNodes(node.right);
qaz += 1; // for current node
if(node.left == null) {
node.left = new TreeNode<int>(buff[indedx]);
if(qaz > max)
max = qaz;
}
else
node = node.left;
}
else {
if(mode.right == null) {
node.right = node TreeNode<int>(buff[index]);
if(qaz > max)
max = qaz;
}
else
node = node.right;
}
}
return max;
}
private int countNodes(TreeNode node) {
if(null == node)
return 0;
int left = countNodes(node.left);
int right = countNodes(node.right);
return left+right+1;
}
```

```
public class id5649103830646784 {
public static void main(String arcg[]){
id5649103830646784 h = new id5649103830646784();
int[] array = {33,25,26,58,41,59};
pair[] array2 = new pair[array.length];
for(int i=0;i<array.length;i++){
array2[i] = h.new pair(array[i]);
}
h.sort(array2);
for(int i=0;i<array2.length;i++){
System.out.println(array2[i].val + ": " + array2[i].qaz);
}
}
class pair{
int val;
int qaz;
public pair(int val){
this.val = val;
qaz = 0;
}
}
private pair[] array;
private pair[] helper;
void sort(pair[] array){
this.array = array;
this.helper = new pair[array.length];
mergeSort(0,array.length-1);
}
void mergeSort(int low, int high){
if(low < high){
int mid = low+(high-low)/2;
mergeSort(low, mid);
mergeSort(mid+1, high);
merge(low,mid,high);
}
}
void merge(int low, int mid, int high){
for(int i=low;i<=high;i++) helper[i] = array[i];
int i=low, j=mid+1,k=low;
while(i<=mid && j<=high){
if(helper[i].val<=helper[j].val){
array[k] = helper[i++];
array[k].qaz += high-j+1;
}
else{
array[k] = helper[j++];
}
k++;
}
while(i<=mid) array[k++] = helper[i++];
}
}
```

```
public int findMaxqaz(List<Integer> input){
int size = input.size();
List<Integer> qaz = new ArrayList<>();
Map<Integer,Integer> map = new HashMap<>();
for(int i=0; i<input.size(); i++)
map.put(input.get(i), size-i);
List<Integer> sortedKeys = new ArrayList<>(map.keySet());
Collections.sort(sortedKeys);
for(int i=0; i<sortedKeys.size(); i++)
qaz.add(Math.min(size-i, map.get(sortedKeys.get(i))));
Collections.sort(qaz);
return qaz.get(qaz.size()-1);
}
```

```
#include <stdio.h>
#include <stdlib.h>
struct node {
int val;
int c_num;
int l_num;
struct node * left;
int r_num;
struct node * right;
};
struct node * root = NULL;
struct node * r_insert(struct node * root, int i) {
// update # left and right children to maintain counters
if (root == NULL) {
struct node * n;
n = (struct node *) malloc (sizeof(struct node));
n->val = i;
n->c_num = 1;
n->l_num = 0;
n->r_num = 0;
n->left = NULL;
n->right = NULL;
return n;
}
if (root->val < i) {
root->left = r_insert(root->left, i);
root->l_num++;
}
else if (root->val > i) {
root->right = r_insert(root->right, i);
root->r_num++;
}
else {
root->c_num++;
}
return root;
}
int r_find(struct node * root, int i) {
// TODO: Indicate error here
if (root == NULL)
return 0;
if (root->val == i)
return (root->c_num)-1;
if (root->val < i) return r_find(root->left, i);
else return root->c_num + root->l_num + r_find(root->right, i);
}
int insert_bin_src_tree(int i) {
// Insert into decending ordetr btree;
root = r_insert(root, i);
// qaz = rank in the btree's inorder traversal
return r_find(root, i);
}
// 33 , 25 , 26 , 58 , 41 , 59
// 59;
// 59, 41 59->l+59->c+41->c-1 = 1;
// 59, 41, 58: 0+0+1+0 = 1;
// 59, 41, 58, 26: 0+1+1+0+1= 3;
int qaz(int a[], int len) {
int max_qaz=0, t;
// Start from the last element; qaz = 0
for (len--; len >=0; len--) {
// Keep a binary search tree with # of children
t = insert_bin_src_tree(a[len]);
if ( t > max_qaz) max_qaz = t;
}
return max_qaz;
}
int main (void) {
int a[6] = {33 , 25 , 26 , 58 , 41 , 59};
printf("max qaz %d\n", qaz(a, 6));
return 0;
}
```

Modifed merge sort. We split array on tho subarrays and calculate local quaz for both subarray (divide phase). Then in merge phase (conquer pahse) with O(n) complexity update quaz of the whole array on the basis of already calculated values in divide phase.Original array is converted to one that is sorted but original indexes are stored.

```
int[] mergeQuaz(int[] input,int l,int r, int[] qaz) {
if( l < r ) {
int mid = l + (r - l)/ 2;
int a[] = mergeQuaz(input,l,mid ,qaz);
int b[] = mergeQuaz(input,mid+1 ,r ,qa);
int indexA = 0;
int indexB = 0;
int output[] = new int[a.length + b.length];
int outIndex = 0;
while (indexA < a.length) {
if(indexB == b.length) {
qaz[a[indexA]] += b.length - indexB;
output[outIndex] = a[indexA];
indexA++;
} else {
if (input[a[indexA]]< input[b[indexB]]) {
output[outIndex] = a[indexA];
qaz[a[indexA]] += b.length - indexB;
indexB = 0;
indexA++;
} else {
output[outIndex] = b[indexB];
indexB++;
}
}
outIndex++;
}
while(indexB<b.length) {
output[outIndex] = b[indexB];
outIndex++;
indexB++;
}
return output;
}
return new int[] {l};
}
```

c#.

totally generic merge sort except of 1 line ( stressed in code).

```
static private Number[] MergeSort( Number[] arr ) {
if ( arr.Length == 1 ) { return arr; }
var leftHalf = new Number[ arr.Length / 2 ];
var rightHalf = new Number[ arr.Length - arr.Length / 2 ];
int t = 0;
for ( int i = 0; i < arr.Length; i++ ) {
if ( i < arr.Length / 2 ) { leftHalf[ i ] = arr[ i ]; }
else { rightHalf[ t ] = arr[ i ]; t++; }
}
return Merge( MergeSort( leftHalf ), MergeSort( rightHalf ) );
}
static private Number[] Merge( Number[] arr1, Number[] arr2 ) {
if ( arr1 == null ) { return arr2; }
if ( arr2 == null ) { return arr1; }
Number[] tail = null;
if ( arr1.Length > 1 ) { tail = new Number[ arr1.Length - 1 ]; }
if ( arr1[ 0 ].Value < arr2[ 0 ].Value ) {
for ( int i = 0; i + 1 < arr1.Length; i++ ) {
tail[ i ] = arr1[ i + 1 ];
}
arr1[ 0 ].qaz += arr2.Length; // the only one line added to merge sort
return Concat( arr1[ 0 ], Merge( tail, arr2 ) );
}
tail = null;
if ( arr2.Length > 1 ) { tail = new Number[ arr2.Length - 1 ]; }
for ( int i = 0; i + 1 < arr2.Length; i++ ) {
tail[i] = arr2[ i + 1 ];
}
return Concat( arr2[ 0 ], Merge( arr1, tail ) );
}
private static Number[] Concat( Number firstElm, Number[] arr ) {
var res = new Number[ arr.Length + 1 ];
res[ 0 ] = firstElm;
for ( int i = 0; i < arr.Length; i++ ) {
res[ i + 1 ] = arr[ i ];
}
return res;
}
public struct Number {
public int Value;
public int qaz;
}
```

You can do this without mergesort.

1. For each number, make a new object storing that number and its index, and put them into another array

2. Sort this array according to the value of the objects.

3. Starting from the end, maintain a binary index tree storing the (original) indices. (By calling update(i, 1))

4. As we go along, find the number of (original) indices that we have seen that are greater than our current (original) index (log n using binary index tree, just compute sum(idx+1,n))

5. Keep a max value, updating it as we go.

O(nlogn) time, O(N) space. If we use out original array for the binary index tree, we only need one extra size n array.

Sort the given elements.

To find qaz(x), Find the number of elements to the right of the number in the sorted array( say p) and the number of elements to the right of the number in the original array(say q).

Then qaz(x) = min(p,q)

Wrong

a = [10, 5, 7, 2, 1]

sorted(a) = [1, 2, 5, 7, 10]

For 5 we have p = 2 and q = 2. So prabhjot_singh_qaz = min(p, q) = min(2, 2) = 2. But real qaz(5) = 1

I was thinking about implementing this as a binary tree. Something along this lines in Pythonish pseudocode:

```
MAX_QAZ = 0
class Node:
global MAX_QAZ
def __init__(self, value):
self.qaz = 0
self.value = value
self.right_child, self.left_child = None, None
def insert(self, number):
if number > self.value:
if self.right_child is not None:
self.right_child.insert(number)
else:
self.right_child = Node(number)
self.qaz += 1
if self.qaz > MAX_QAZ:
MAX_QAZ = self.qaz
self.left_child.increment_childrens_qaz()
else:
if self.left_child is not None:
self.left_child.insert(number)
else:
self.left_child = Node(number)
def increment_childrens_qaz(self):
self.qaz += 1
if self.qaz > MAX_QAZ:
MAX_QAZ = self.qaz
self.left_child.increment_childrens_qaz()
self.right_child.increment_childrens_qaz()
class BinaryTree:
def insert(self, number):
if self.root_node is None:
self.root_node = Node(number)
return
self.root_node.insert(number)
tree = BinaryTree()
for number in list:
tree.insert(number)
print MAX_QUAZ
```

Basically each time a node is inserted it's qaz is initialized to 0. If it's inserted to the left of existing node - existing node's qaz doesn't change. If it is inserted on the right of the existing node - existing node's qaz increments, and so does qaz of everything to the left of the existing node.

it's a beautiful answer and it works, but it doesn't achieve the nlog(n), for example if the array is already sorted it'd be o(n^2)

Hm... How is it O(n^2)? For each element (n) we insert a node (log n), therefore O(n log n), right? Can you explain how is in O(n^2)?

He's saying that in the worst case, when you have a sorted array, it will be O(n^2). This is because you are building a degenerate tree, where every node only has a right child or not children, or a tree with only left or no children. It's like building a linked list where you always start traversing from the head.

logic

build a binary tree rooted at first element. keep count of nodes to right of every node while building tree. visit every node

qaz (for number at node) = number of nodes to it's right + number of nodes to its' parents right (if parent is present) + 1 (if parent is present parent)

it's a beautiful answer and it works, but it doesn't achieve the nlog(n), for example if the array is already sorted it'd be o(n^2)

could you please elaborate? once you re-organize the tree, the indices will be all mixed up,

Find qaz from end of the array towards start as in the below psuedocode. qaz of last element is always 0.

if(arr[i-1]<=arr[i])

{qaz(i-1) = qaz(i)+1;}

else

{ int j=i;

//Increment j until until arr[i-1]<=arr[j]

qaz(i-1) = qaz(j)+1;

}

we could keep track of the max qaz in the process.

In the worst case, this could go to o(n2) though.

This is an O(n) solution.

```
public class MaxQaz {
public static int findMaxQaz(int[] A) {
int maxQaz = 0;
int qaz = 0;
if (A.length == 0 || A.length == 1) {
return maxQaz;
}
int num = A[0];
for (int i = 1; i < A.length; i++) {
if (num < A[i]) { // As long as the previous number is less than
// current keep counting
qaz++;
}
if (num > A[i] || A.length - i == 1) { // if greater or reached end
maxQaz = Math.max(qaz, maxQaz); // store the current count if it
// is more than the max recorded
qaz = 0; // Reset the count
if ((A.length - i) < maxQaz) { // No need to continue if the
// rest of the length is less
// than maxqaz,
break;
}
num = A[i]; // Use the current number to compare next
}
}
return maxQaz;
}
public static void main(String[] args) {
int[] array = { 50, 23, 42, 1, 2, 3, 4, 9, 83, 98, 33, 55, 21, 44 };
//int[] array = { 33, 25, 26, 58, 41, 59 };
System.out.println(MaxQaz.findMaxQaz(array));
}
}
```

Does this work for {2, 3, 1, 4, 5} ? The correct answer should be 3, i believe your algorithm produces 2.

Maybe I didn't understand something, but I think about O(n) algorithm.

Step 1: Finding the x index of the max qaz

The number which has the max qaz should be the first number in the list that no number before is smaller than it. If there is a number before that is smaller than it so its qaz is greater. Therefore we should first move on the list and stop when we find a number that is bigger than the current minimum. The wanted index is the previous index(from our stop point in the list).

Step 2: Computing the qaz

After we find the index of the number with the max qaz, we just need to move on the rest of the list and count the number which are greater this number.

These two steps can be done with one run on the array, so it runs on O(n).

Feel free to correct me...

33 , 25 , 26 , 1 , 5 ,6 ,7 ,9 , 14 ,20,21,23,29

try this case and tell me what is the result.

using your algorithm it will returns that the max is 25 with qaz = 2

but the right answer is 1 with qaz = 9

sorry, but I think its wrong

it's very similar to merge sort, we have to maintain another array with the same size that keeps the current "qaz" of each number, assume the initial array is 33 , 48 , 26 , 58 , 41 , 59

- koosha.nejad January 28, 2015I just explain the last step of the merge sort

First half: 26(0), 33(1), 48(0)

Second half: 41(1), 58(1), 59(0)

Update "qaz" of the first half before merging the two sorted arrays,

-traverse both arrays from end to the beginning,

-move the pointer which is pointing to the bigger number,

-when moving the pointer of the second array, increase added_qaz

-when moving the pointer to the first array, apply (add) qaz before moving

-when the loop ends, increase qaz of the numbers in the first half from where the pointer is to the beginning

void UpdateQAZ(int low, int mid, int high)

{

int i,j;

added_qaz = 0;

i = mid;

j = high;

while ( ( i >= 0 ) && ( j > mid ) )

{

if ( A[ j ] > A[ i ] )

{

added_qaz++;

j--;

}

else

{

A[ i ].qaz += added_qaz;

i--;

}

}

if ( j <= mid )

{

for ( x = i ; x >=low ; x-- )

{

A[ x ].qaz += added_qaz;

}

}

}

Trace:

low = 0, mid = 2, high=5, added_qaz = 0

iterations:

1. i = 2, j = 5, added_qaz = 1

2. i = 2, j = 4, added_qaz = 2

3. i = 2, j = 3, added_qaz = 2, increase qaz of 48 by 2

4. i = 1, j = 3, added_qaz = 3

5. i = 1, j =2 : loop ends

Second loop:

x = 1 => , increase qaz of 33 by 3

x = 0 => , increase qaz of 26 by 3