Skip to content

3920. Maximize Fixed Points After Deletions

SourceWeekly Contest 500 Q4DifficultyHardRating2263

Description

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.

 

Example 1:

Input: nums = [0,2,1]

Output: 2

Explanation:

  • Delete nums[1] = 2. The array becomes [0, 1].
  • Now, nums[0] = 0 and nums[1] = 1, so both indices are fixed points.
  • Thus, the answer is 2.

Example 2:

Input: nums = [3,1,2]

Output: 2

Explanation:

  • Do not delete any elements. The array remains [3, 1, 2].
  • Here, nums[1] = 1 and nums[2] = 2, so these indices are fixed points.
  • Thus, the answer is 2.

Example 3:

Input: nums = [1,0,1,2]

Output: 3

Explanation:

  • Delete nums[0] = 1. The array becomes [0, 1, 2].
  • Now, nums[0] = 0, nums[1] = 1, and nums[2] = 2, so all indices are fixed points.
  • Thus, the answer is 3.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105

Solutions

Solution 1

Thinking

Deletions shift later indices, so enumerating deletion sets is exponential and impossible for \(n\le 10^5\). A value \(x\) becomes a fixed point only if it is placed at index \(x\), which means exactly \(x\) elements remain to its left.

Hence each \(x\) contributes at most one fixed point, and a candidate must satisfy \(\textit{nums}[i]\) being large enough for its final index. The task is to keep as many such placements as possible without breaking the prefix length required by smaller fixed points.

This directory has no implemented solution yet; the walkthrough stops at that index-to-value correspondence.

1


1


1


1

Comments