maximize-fixed-points-after-deletions

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>nums</code>.

A position <code>i</code> is called a fixed point if <code>nums[i] == i</code>.

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.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [0,2,1]

Output: 2

Explanation:

<ul>
	<li>Delete <code>nums[1] = 2</code>. The array becomes <code>[0, 1]</code>.</li>
	<li>Now, <code>nums[0] = 0</code> and <code>nums[1] = 1</code>, so both indices are fixed points.</li>
	<li>Thus, the answer is 2.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: nums = [3,1,2]

Output: 2

Explanation:

<ul>
	<li>Do not delete any elements. The array remains <code>[3, 1, 2]</code>.</li>
	<li>Here, <code>nums[1] = 1</code> and <code>nums[2] = 2</code>, so these indices are fixed points.</li>
	<li>Thus, the answer is 2.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: nums = [1,0,1,2]

Output: 3

Explanation:

<ul>
	<li>Delete <code>nums[0] = 1</code>. The array becomes <code>[0, 1, 2]</code>.</li>
	<li>Now, <code>nums[0] = 0</code>, <code>nums[1] = 1</code>, and <code>nums[2] = 2</code>, so all indices are fixed points.</li>
	<li>Thus, the answer is 3.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 105</code></li>
</ul>