Maximize fixed points after deletions

18.6% acceptance

May 14, 2026

You are given an integer array nums. A position i is called a fixed point if nums[i] == i. You are allowed to delete any number of elements (including zero) from the array. After each deletion, the remaining elements shift left, and indices are reassigned starting from 0. Return an integer denoting the maximum number of fixed points that can be achieved after performing any number of deletions.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_fixed_points(nums: Vec<i32>) -> i32 {
    let mut points: Vec<(i32, i32)> = Vec::new();
    for (i, &v) in nums.iter().enumerate() {
      let q = i as i32 - v;
      if q >= 0 {
        points.push((v, q));
      }
    }
    points.sort_by(|a, b| a.0.cmp(&b.0).then(b.1.cmp(&a.1)));
    let mut tails: Vec<i32> = Vec::new();
    for &(_, q) in &points {
      let pos = tails.partition_point(|&t| t <= q);
      if pos == tails.len() {
        tails.push(q);
      } else {
        tails[pos] = q;
      }
    }
    tails.len() as i32
  }
}