[JavaScript] 87ms + Prefix Sum + BinarySearch + Comments
Approach\nTo solve this problem, I divided it into three steps: Sorting the nums array, create a prefix sum array of sorted nums and use binary search to get th
# Approach\nTo solve this problem, I divided it into three steps: Sorting the nums array, create a prefix sum array of sorted nums and use binary search to get the index of the last fitting prefix sum.\n\n## 1. Sort Nums array:\nTo create our prefix sum arr we have to sort the input nums array. For this I simply used the already defined sort function of JavaScript: \n\n`nums.sort((a, b) => a - b); // Sort nums array`\n\nThe input array `nums = [4, 5, 2, 1];` will be `[1, 2, 4, 5]`.\n\n## 2. Create Prefix sum vector/array of nums\n<table>\n    <tr>\n        <td>Input Numbers:</td>\n        <td>1</td>\n        <td>2</td>\n        <td>4</td>\n        <td>5</td>\n    </tr>\n    <tr>\n        <td>Prefix sums:</td>\n        <td>1</td>\n        <td>3</td>\n        <td>7</td>\n        <td>12</td>\n    </tr>\n</table>\n\nThe prefix sum array will be: `prefixSum = [1, 3, 7, 12]`\n\n## 3. Binary Search \nNow I use Binary Search to find element in prefix lesser or equal to query (`queries = [3, 10, 21]`): Search query in prefixSum array and push index + 1 to the answer array.\n\n- For query `3`: \nNumber `3` at index `1` in `prefixSum` is found. Store `1 + 1 = 2` (index + 1) in answer array.\n\n- For query `10`: \nNumber `7` at index `2` in `prefixSum` is found (7 first element lesser than 10). Store `2 + 1 = 3` (index + 1) in answer array.\n\n- For query `21`: \nNumber `12` at index `3` in `prefixSum` is found (12 first element lesser than 21). Store `3 + 1 = 4` (index + 1) in answer array.\n\nAt last return answer array.\n\n# Code\n```\n/**\n * @param {number[]} nums\n * @param {number[]} queries\n * @return {number[]}\n */\nvar answerQueries = function(nums, queries) {\n    nums.sort((a, b) => a - b); // Sort nums array\n    \n    const prefixSum = [nums[0]]; // Initialize prefix sum array with first element\n    for (let i = 1; i < nums.length; i++) { // For loop to traverse the input array\n        prefixSum.push(prefixSum[i - 1] + nums[i]); // Add sum of present element with previous element to prefixSum\n    }\n\n    const binarySearch = (arr, l, r, x) => { // Recursive binary search\n        if (r >= l) {\n            let mid = l + Math.floor((r - l) / 2); // Calculate mid\n            if (arr[mid] == x) { // Check if element is present in middle\n                return mid; // Return if element \n            } else if (x < arr[mid]) { // Check if element is smaller than mid\n                return binarySearch(arr, l, mid - 1, x); // Return left side\n            } else { // x is bigger than mid\n                return binarySearch(arr, mid + 1, r, x); // Return right side\n            } \n        } else { // Any element was checked\n            return r; // Return oldMid\n        }\n    }\n\n    const answer = []; // Initialize answer array\n    for(let j = 0; j < queries.length; j++) { // Loop all queries\n        answer.push(binarySearch(prefixSum, 0, prefixSum.length - 1, queries[j]) + 1); // Use binary search on each query\n    }\n    return answer; // Return answer array\n};\n```
['Binary Search', 'Prefix Sum', 'JavaScript']