Binary Search | Easy to Understand | ArrayList/LinkedList
Working with ArrayList;\n\n---\n\nUpdated Solution (Passed)\n---\n\nclass Solution {\n    public int[] resultArray(int[] nums) {\n        ArrayList<Integer> arr
Working with ArrayList;\n\n---\n\nUpdated Solution (Passed)\n---\n```\nclass Solution {\n    public int[] resultArray(int[] nums) {\n        ArrayList<Integer> arr1 = new ArrayList<>(), arr2 = new ArrayList<>();\n        ArrayList<Integer> arr1Sorted = new ArrayList<>(), arr2Sorted = new ArrayList<>();\n        \n        arr1.add(nums[0]); \n        arr2.add(nums[1]);\n        arr1Sorted.add(nums[0]);\n        arr2Sorted.add(nums[1]);\n        \n        for(int i=2; i<nums.length; i++){\n            int val = nums[i];\n            int pos1 = binarySearch(arr1Sorted, val), pos2 = binarySearch(arr2Sorted, val);\n            int gc1 = arr1.size() - pos1;\n            int gc2 = arr2.size() - pos2;\n            \n            if(gc1 > gc2){\n                arr1.add(val);\n                arr1Sorted.add(pos1, val);\n            }\n            \n            else if(gc2 > gc1){\n                arr2.add(val);\n                arr2Sorted.add(pos2, val);\n            }\n            \n            else{\n                if(arr2.size() < arr1.size()){\n                    arr2.add(val);\n                    arr2Sorted.add(pos2, val);\n                }\n                else{\n                    arr1.add(val);\n                    arr1Sorted.add(pos1, val);\n                }\n            }\n        }\n        int i=0;\n        for(int num : arr1){\n            nums[i++] = num;\n        }\n        for(int num : arr2){\n            nums[i++] = num;\n        }\n        return nums;\n    }\n    public int binarySearch(List<Integer> arr, int val){\n        int left = 0;\n        int right = arr.size() - 1;\n        \n        while(left <= right){\n            int mid = left + (right-left)/2;\n            if(arr.get(mid) <= val)\n                left = mid + 1;\n            else\n                right = mid - 1;\n        }\n        return left;\n    }\n}\n```\nPrevious Solution (TLE 778/784)\n----\n```\nclass Solution {\n    public int[] resultArray(int[] nums) {\n        LinkedList<Integer> arr1 = new LinkedList<>(), arr2 = new LinkedList<>();\n        LinkedList<Integer> arr1Sorted = new LinkedList<>(), arr2Sorted = new LinkedList<>();\n        \n        arr1.add(nums[0]); \n        arr2.add(nums[1]);\n        arr1Sorted.add(nums[0]);\n        arr2Sorted.add(nums[1]);\n        \n        for(int i=2; i<nums.length; i++){\n            int val = nums[i];\n            int pos1 = binarySearch(arr1Sorted, val), pos2 = binarySearch(arr2Sorted, val);\n            int gc1 = arr1.size() - pos1;\n            int gc2 = arr2.size() - pos2;\n            \n            if(gc1 > gc2){\n                arr1.add(val);\n                arr1Sorted.add(pos1, val);\n            }\n            \n            else if(gc2 > gc1){\n                arr2.add(val);\n                arr2Sorted.add(pos2, val);\n            }\n            \n            else{\n                if(arr2.size() < arr1.size()){\n                    arr2.add(val);\n                    arr2Sorted.add(pos2, val);\n                }\n                else{\n                    arr1.add(val);\n                    arr1Sorted.add(pos1, val);\n                }\n            }\n        }\n        int i=0;\n        for(int num : arr1){\n            nums[i++] = num;\n        }\n        for(int num : arr2){\n            nums[i++] = num;\n        }\n        return nums;\n    }\n    public int binarySearch(List<Integer> arr, int val){\n        int left = 0;\n        int right = arr.size() - 1;\n        \n        while(left <= right){\n            int mid = left + (right-left)/2;\n            if(arr.get(mid) <= val)\n                left = mid + 1;\n            else\n                right = mid - 1;\n        }\n        return left;\n    }\n}
['Binary Search', 'Java']