Qaz

This problem is from careercup, link
Problem description:
1. qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number.
for example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3 where 33 less than 3 numbers (58 , 41 , 59), qaz of (25) = 4 and not 5 because the index of 33 is less than the index of 25, qaz of (26) = 3 , qaz of (58) = 1 , qaz of (41) = 1 , qaz of (59) = 0.
the question is to find the max qaz.

A brute force solution is to iterate each element, and find how many elements after and larger than it.
A O(nlogn) solution can be achieved by mergesort:
For each array, it has a maxQaz. Let’s consider to merge {33, 48, 26} and {58, 41, 59}.
Final result of 2 arrays are:
{26(0), 33(1), 48(0)}, leftQaz = 1.
{41(1), 58(1), 59(0)}, rightQaz = 1.
-initial added_qaz = 0,
-traverse both arrays from end to the beginning,
-move the pointer which is pointing to the bigger number,
—when moving the pointer of the right sub array, increase added_qaz
—when moving the pointer of the left sub array, apply added_qaz to qaz of pointed element before moving 
Because only left sub array is updated.
Now, left sub array should be {26(3), 33(4), 48(2)}. And we know leftQaz is 4.
Before return, we use merge sort to merge 2 subarrays, and got:
{26(3), 33(4), 41(1), 48(2), 58(1), 59(0)}.
Now, we should return max(leftQaz, rightQaz). The result would be 4.

The code is kinda long. Because we use mergesort, so 2 helper arrays for auxiliary space are used.

1. package feb;
2. public class QAZ {
3.     public static void main(String[] args) {
4.         int[] arr = { 7, 8, 2, 3, 4, 5 };
5.         int qaz = qaz(arr);
6.         System.out.println(qaz);
7.     }
8.     public static int qaz(int[] arr) {
9.         int[] eleTimes = new int[arr.length];
10.         int[] helperQaz = new int[arr.length];
11.         int[] helperTimes = new int[arr.length];
12.         return qazUtil(arr, eleTimes, 0, arr.length – 1, helperQaz, helperTimes);
13.     }
14.     /*
15.      * Return qaz of arr[]
16.      * @param qazArr[], qazArr[i] stores the qaz of element arr[i] from arr[start,…,end].
17.      * @param start, the start position of arr[]
18.      * @param end, the end position of arr[]
19.      * @param helperQaz, this is a helper array for mergesort. It helps for arr[]
20.      * @param helperTimes, a helper array for merge sort. It is temporary place for eleTimes
21.      */
22.     private static int qazUtil(int[] arr, int[] qazArr, int start, int end,
23.             int[] helperQaz, int[] helperTimes) {
24.         if (start > end) {
25.             return 0;
26.         }
27.         if (start == end) {
28.             return 0;
29.         }
30.         int mid = start + (end – start) / 2;
31.         int qazLeft = qazUtil(arr, qazArr, start, mid, helperQaz, helperTimes);
32.         int qazRight = qazUtil(arr, qazArr, mid + 1, end, helperQaz, helperTimes);
33.         // 1. Update eleTimes in left part.
34.         int pointerL = mid, pointerR = end;
35.         int added = 0;
36.         while (pointerL >= start) {
37.             while (arr[pointerL] < arr[pointerR] && pointerR >= mid + 1) {
38.                 pointerR–;
39.                 added++;
40.             }
41.             qazArr[pointerL] += added;
42.             qazLeft = (qazArr[pointerL] > qazLeft) ? qazArr[pointerL]: qazLeft;
43.             pointerL–;
44.         }
45.         // 2. Mergesort left and right part into helperQaz, helperTimes
46.         pointerL = start;
47.         pointerR = mid + 1;
48.         int helpIndex = start;
49.         while (pointerL <= mid && pointerR <= end) {
50.             if (arr[pointerL] < arr[pointerR]) {
51.                 helperQaz[helpIndex] = arr[pointerL];
52.                 helperTimes[helpIndex] = qazArr[pointerL];
53.                 pointerL++;
54.             } else {
55.                 helperQaz[helpIndex] = arr[pointerR];
56.                 helperTimes[helpIndex] = qazArr[pointerR];
57.                 pointerR++;
58.             }
59.             helpIndex++;
60.         }
61.         while (pointerL <= mid) {
62.             helperQaz[helpIndex] = arr[pointerL];
63.             helperTimes[helpIndex] = qazArr[pointerL];
64.             pointerL++;
65.             helpIndex++;
66.         }
67.         while (pointerR <= end) {
68.             helperQaz[helpIndex] = arr[pointerR];
69.             helperTimes[helpIndex] = qazArr[pointerR];
70.             pointerR++;
71.             helpIndex++;
72.         }
73.         // 2.2 Copy result from helperQaz, helperTimes back to arr, eleTimes
74.         for (int i = start; i <= end; i++) {
75.             arr[i] = helperQaz[i];
76.             qazArr[i] = helperTimes[i];
77.         }
78.         return Math.max(qazLeft, qazRight);
79.     }
80. }