Find Greater Elements using Binary Search || Easy Solution
The main challenge in this problem is to find the number of greater elements each time in the ith operation.\n\nIf we implement the greaterCount function by bru
The main challenge in this problem is to find the number of greater elements each time in the ith operation.\n\nIf we implement the greaterCount function by brute force method, then it will take O(n) time. And for each element of nums, if we execute greaterCount function, then it will take a total time of O(n * n) which will, of course, give us TLE.\n\nNow lets say if we get sorted array then we can easily find the number of greater elements by finding the correct index of the element to be inserted.\n\nFor example consider this sorted array\n```\n[1,2,4,5]\nIf we want to find the number of element greater than 3 then we can\nperform binary search and find the index where 3 should be inserted \nso that the array remains sorted. Here this index is 2 where 3 should\nbe inserted. Since array is sorted we know all the elements after\nthis index will be greater than 3. So we can find the total greater\nelements greater than given element in log(n) time.\n```\n\n**Now the Question arrises how will we use this in this question because order is important so we can\'t normally sort the array.**\n\n1. Create two arrays arr1 and arr2.\n2. Create two more arrays sorted1 and sorted2.\n3. Now, according to the question, we will insert the first element in Arr1 and 2nd element in Arr2.\n4. Now, for the every ith operation, we will find the correct index of nums[i] ```(findIndexInSorted())``` in both the arrays, sorted1 and sorted2 And using the above logic, we can find the number of greater elements available for nums[i] and according to that, we will insert element in partitioning array and sorted arrays.\n5. After all, the operations are done we will merge both the arrays and that will be our answer.\nB\n# Code\n```\nclass Solution {\n\n    // Function to find the correct index to insert the element in sorted array\n    public int findIndexInSorted(List<Integer> arr, int val) {\n        int left = 0, right = arr.size() - 1; \n        int ans = -1;\n\n        while(left <= right) {\n            int mid = left + (right - left) / 2;\n\n            if (arr.get(mid) < val) {\n                left = mid + 1;\n            } else if(arr.get(mid) > val) {\n                right = mid - 1;\n            } else {\n                ans = mid;\n                left = mid + 1;\n            }\n        }\n\n        if(ans == -1) {\n            return Math.max(left, right);\n        } else {\n            return left;\n        }\n    }\n\n    // Function to insert element in the sorted array\n    public void insertElementInSortedArray(List<Integer> arr, int index, int value) {\n        if(index == arr.size()) {\n            arr.add(value);\n        } else {\n            arr.add(index, value);\n        }\n\n        return;\n    }\n    public int[] resultArray(int[] nums) {\n        // Define 2 Arrays to partition nums\n        var arr1 = new ArrayList<Integer>();\n        var arr2 = new ArrayList<Integer>();\n\n        // Maintain sorted Arrays to find number of greater elements in log(n) time\n        var sorted1 = new ArrayList<Integer>();\n        var sorted2 = new ArrayList<Integer>();\n\n        // 1st element in arr1\n        arr1.add(nums[0]);\n        sorted1.add(nums[0]);\n\n        // 2nd element in arr2\n        arr2.add(nums[1]);\n        sorted2.add(nums[1]);\n\n        // For each ith operation from i = 2 to n\n        for(int i = 2; i < nums.length; i++) {\n            // Index where the current element will be inserted im sorted arrays\n            int i1 = findIndexInSorted(sorted1, nums[i]);\n            int i2 = findIndexInSorted(sorted2, nums[i]);\n\n            // Since array is sorted we can find number of greater elements easily now\n            int greaterElementsInArr1 = arr1.size() - i1;\n            int greaterElementsInArr2 = arr2.size() - i2;\n\n            // Insert element according to the given conditions and also insert in sorted array\n            if(greaterElementsInArr1 > greaterElementsInArr2) {\n                insertElementInSortedArray(sorted1, i1, nums[i]);\n                arr1.add(nums[i]);\n            } else if(greaterElementsInArr2 > greaterElementsInArr1) {\n                insertElementInSortedArray(sorted2, i2, nums[i]);\n                arr2.add(nums[i]);\n            } else {\n                if(arr1.size() <= arr2.size()) {\n                    insertElementInSortedArray(sorted1, i1, nums[i]);\n                    arr1.add(nums[i]);\n                } else {\n                    insertElementInSortedArray(sorted2, i2, nums[i]);\n                    arr2.add(nums[i]);\n                }\n            }\n        }\n            \n        // Concatinate both array into result array\n        int result [] = new int [nums.length];\n\n        int idx = 0;\n        for(int i : arr1) {\n            result[idx] = i;\n            idx += 1;\n        }\n\n        for(int i : arr2) {\n            result[idx] = i;\n            idx += 1;\n        }\n\n        return result;\n    }\n}\n```
['Binary Search', 'Java']