Sorting, Two Pointers, and Binary Search | 30ms O(n * log(n)) | Rust
Complexity\n- Time complexity: O(n \times{log(n)})\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n)\n Add your space complexity here, e.g
# Complexity\n- Time complexity: $$O(n \\times{log(n)})$$\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```\nimpl Solution {\n    pub fn max_frequency_score(mut nums: Vec<i32>, k: i64) -> i32 {\n        let n = nums.len();\n        let (mut l, mut ans) = (0, 1);\n        let mut sums = vec![0; n + 1];\n\n        nums.sort_unstable();\n        (0..n).for_each(|i| sums[i + 1] = nums[i] as i64 + sums[i]);\n\n        for r in 0..n {\n            while find_minima(&nums[l..=r], &sums[l..=r+1]) > k {\n                l += 1;\n            }\n            ans = ans.max(r - l + 1);\n        }\n\n        ans as i32\n    }\n}\n\nfn find_minima(nums: &[i32], sums: &[i64]) -> i64 {\n    let n = nums.len();\n    let (mut l, mut r) = (0, n);\n\n    let get_cost = |mid| {\n        let left = (mid + 1) as i64 * nums[mid] as i64;\n        let left_sum = left - (sums[mid + 1] - sums[0]);\n        let right = (n - mid) as i64 * nums[mid] as i64;\n        let right_sum = (sums[n] - sums[mid]) - right;\n\n        left_sum + right_sum\n    };\n\n    while l < r {\n        let mid = l + (r - l) / 2;\n\n        if (mid == 0 || get_cost(mid - 1) >= get_cost(mid))\n            && (mid == n - 1 || get_cost(mid + 1) >= get_cost(mid))\n        {\n            return get_cost(mid);\n        } else if mid > 0 && get_cost(mid - 1) < get_cost(mid) {\n            r = mid - 1;\n        } else {\n            l = mid + 1;\n        }\n    }\n\n    unreachable!("Couldn\'t find minima!");\n}\n```
['Rust']