Rust | Prefix Sum + Binary Search | With Comments
This is my unaltered submission to the 2022-08-28 Weekly Contest 308. We can take whichever numbers we want, as long as their sum is less than queries[i]. So we
This is my unaltered submission to the 2022-08-28 Weekly Contest 308. We can take whichever numbers we want, as long as their sum is less than `queries[i]`. So we can sort `nums` (O(n log(n)) where n is the length of `nums`) and take as many numbers as we can while their sum is less that `queries[i]` (O(q * n) where q is the length of `queries`). Do do better, we can compute the prefix sums of the sorted `nums` (O(n)), and since the sums are themselves strictly increasing, we can perform binary searches to find the answers to the queries (O(q * log(n))).\n\nTime: O(n log(n) + q log(n))\nSpace: O(n) for vector of prefix sums (could be computed in place for O(1))\n\nComment: My first contest submisson ever, which threw me off a bit since it was more difficult than typical LeetCode "easy" problems. I should focus more on solving the problem quickly and less on clean functional-style code, at least for contests.\n\n```\nimpl Solution {\n    pub fn answer_queries(mut nums: Vec<i32>, queries: Vec<i32>) -> Vec<i32> {\n        nums.sort_unstable();\n        let mut acc = 0;\n        let sums = nums.into_iter().map(|num| { acc += num; acc }).collect::<Vec<i32>>();\n        queries.into_iter().map(|q| match sums.binary_search(&q) {\n            Ok(i) => i + 1,\n            Err(i) => i,\n        } as i32).collect::<Vec<_>>()\n    }\n}\n```
['Rust']