2 Solutions in Java Using Linear & Binary Search
\n# Approach 1 (Using Linear Search) Describe your approach to solving the problem. \nThe code sorts the array. Then it creates a prefix sum array. The prefix s
\n# Approach 1 (Using Linear Search)<!-- Describe your approach to solving the problem. -->\nThe code sorts the array. Then it creates a prefix sum array. The prefix sum array contains the cumulative sum of all elements in the original array.\n\nThen for each query, it finds the index of the last element that is less than or equal to the query value and returns this index + 1 as an answer.\n\n# Complexity\n- Time complexity:  The time complexity is $$O(n^2)$$ because of the nested for loops.\n\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The space complexity is $$O(n)$$ because we are creating two arrays of size n.\n\n\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int[] answerQueries(int[] nums, int[] queries) {\n        int n = nums.length;\n        int m = queries.length;\n\n        Arrays.sort(nums);\n\n        int ans[] = new int[m];\n        int prefix[] = new int[n];\n   \n        prefix[0] = nums[0];\n\n        for(int i=1; i<n; i++){\n            prefix[i] = prefix[i-1] + nums[i];\n        }\n        for(int i=0; i<m; i++){\n            int idx= -1;\n            for(int j=0; j<n;j++){\n                if(prefix[j]<=queries[i]){\n                    idx=j;\n                }\n                else break;\n            }\n         ans[i]=idx+1;\n        }\n        return ans;\n    }\n}  }\n}\n```\n# Approach 2 (Using Binary Search)\nThe code takes two arrays as input. The first array is the array of integers and the second array is an array of queries. Each query contains a number that we want to find the number of elements less than or equal to it in the first array\nThe code sorts the array and then uses a prefix sum to calculate the number of elements that are less than or equal to a given integer.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int[] answerQueries(int[] nums, int[] queries) {\n        int n = nums.length;\n        int m = queries.length;\n        Arrays.sort(nums);\n        int ans[] = new int[m];\n        \n        for(int i=1; i<n; i++){\n            nums[i]+=nums[i-1];\n        }\n            for(int j=0; j<m;j++){\n               int i= Arrays.binarySearch(nums , queries[j]);\n               ans[j]= Math.abs(i+1);\n            }\n        return ans;\n    }\n}\n```
['Array', 'Binary Search', 'Greedy', 'Sorting', 'Java']