Rust - Binary search to determine minimal acceptable value `s`.
Intuition\n\nEven finding the optimal value is not easy, it is possible to check whether the problem can be solved within s steps.\n\n# Approach\n\nVerify if th
# Intuition\n\nEven finding the optimal value is not easy, it is possible to check whether the problem can be solved within `s` steps.\n\n# Approach\n\nVerify if the problem can be solved withing `s` steps, update the search region from `[l, r]` to `[l, m]` or `[m, r]` using binary search.\n\n# Complexity\n\n- Time complexity: $$O((m+n) \\log n)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```\nimpl Solution {\n    fn enableToMarkIndices(nums: &Vec<i32>, change_indices: &Vec<i32>, m: i32) -> bool {\n        let n = nums.len();\n        let mut last_indices: Vec<(i32, usize)> = Vec::new();\n        let mut sum: i32 = 0;\n\n        last_indices.reserve(n);\n        for i in 0..n {\n            last_indices.push((-1, i));\n        }\n\n        for i in 0..m {\n            last_indices[change_indices[i as usize] as usize].0 = i as i32;\n        }\n\n        sum = 0;\n        last_indices.sort();\n        for (i, (last, x)) in last_indices.into_iter().enumerate() {\n            sum += nums[x];\n            if (last < (i as i32) + sum) {\n                return false;\n            }\n        }\n\n        return true;\n    }\n\n    pub fn earliest_second_to_mark_indices(nums: Vec<i32>, change_indices: Vec<i32>) -> i32 {\n        let mut change_indices = change_indices;\n        let m = change_indices.len() as i64;\n        let n = nums.len() as i64;\n        let mut l: i64;\n        let mut r: i64 = m + 1;\n        let mut mid: i64;\n\n        for x in change_indices.iter_mut() {\n            *x -= 1;\n        }\n\n        l = nums.iter().fold(0 as i64, |sum, x| sum + (*x as i64));\n        r = m + 1;\n\n        if (l > m) {\n            return -1;\n        }\n\n        while (l < r) {\n            mid = l + (r - l) / 2;\n            \n            if (Self::enableToMarkIndices(&nums, &change_indices, mid as i32)) {\n                r = mid;\n            } else {\n                l = mid + 1;\n            }\n        }\n\n        return if (l <= m) { l as i32 } else { -1 };\n    }\n}\n```
['Binary Search', 'Rust']