3 approaches | CodeDominar Solution
@1st approach --->\n\nThe Time complexity of this function is O(nq), where n is the length of the list nums and q is the length of the list queries.\n\n# Code\n
# @1st approach --->\n\n`The Time complexity of this function is O(nq), where n is the length of the list nums and q is the length of the list queries.`\n\n# Code\n```\nclass Solution:\n    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n        nums.sort()\n        ans = []\n        for q in queries:\n            cnt,val = 0,0\n            for n in nums:\n                if val+n<=q:\n                    cnt += 1\n                    val += n\n            ans.append(cnt)\n        return ans\n      \n```\n\n# @2nd approach --->\n\n`The time complexity of this implementation is O(N log N + Q log N), where N is the length of the array nums and Q is the length of the array queries. `\n\n# Code\n```\nclass Solution:\n    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n        # Sort the array nums in ascending order\n        nums.sort()\n\n        # Compute the prefix sum array\n        prefix_sum = [0] * len(nums)\n        prefix_sum[0] = nums[0]\n        for i in range(1, len(nums)):\n            prefix_sum[i] = prefix_sum[i-1] + nums[i]\n\n        # Store the prefix sum values in a TreeMap\n        tree_map = OrderedDict()\n        tree_map[prefix_sum[0]] = 1\n        for i in range(1, len(nums)):\n            tree_map[prefix_sum[i]] = i+1\n\n        # Answer the queries using the TreeMap\n        ans = []\n        for q in queries:\n            keys = list(tree_map.keys())\n            index = bisect.bisect_right(keys, q)\n            if index > 0:\n                key = keys[index-1]\n                ans.append(tree_map[key])\n            else:\n                ans.append(0)\n\n        return ans\n      \n```\n\n\n# @3rd approach --->\n\n`The time complexity of this algorithm is O(N log N + Q), where N is the length of the array nums and Q is the length of the array queries.` \n\n# Code\n```\n\nclass Solution:\n    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n        nums.sort()\n        # Compute the prefix sum array\n        prefix_sum = [0] * (len(nums) + 1)\n        for i in range(len(nums)):\n            prefix_sum[i+1] = nums[i] + prefix_sum[i]\n\n        # Answer the queries\n        ans = []\n        for q in queries:\n            i = 0\n            while i < len(nums) and prefix_sum[i+1] <= q:\n                i += 1\n            ans.append(i)\n\n        return ans\n```\n\n\n\n\n\n
['Ordered Map', 'Sorting', 'Python', 'Python3']