Maximize Fixed Points After Deletions - Solution & Explanation

Problem Overview: You are given an array and can delete any elements. After deletions, the remaining elements are reindexed starting from 1. A fixed point occurs when a[i] == i. The goal is to delete elements so the resulting array contains the maximum possible number of fixed points.

Approach 1: Brute Force Subsequence Enumeration (O(2^n) time, O(n) space)

Generate every possible subsequence and check whether elements satisfy the fixed-point condition after reindexing. For each subsequence of length k, verify that the element placed at index j equals j. This approach uses recursion or bitmasks to explore all subsets. It demonstrates the problem mechanics but quickly becomes infeasible once n grows because the search space doubles with each element.

Approach 2: Dynamic Programming on Value Matching (O(n^2) time, O(n) space)

Observe that if the final array has k fixed points, its values must be exactly 1, 2, ..., k in that order. Any valid solution is therefore a subsequence whose values strictly follow this sequence. Define dp[v] as the maximum subsequence length ending with value v. Iterate through the array and attempt to extend subsequences where the previous value is v-1. This ensures the subsequence forms the exact increasing sequence required for fixed points. The DP formulation is straightforward but requires scanning states repeatedly, which leads to quadratic behavior.

Approach 3: Greedy Target Matching (O(n) time, O(1) space)

The optimal observation is that the final array must contain the sequence 1,2,3,...,k in order. While scanning the array from left to right, maintain the next required value target. Whenever a[i] == target, keep that element and increment target. Otherwise, delete the element. Because deletions shift indices left, selecting values in this exact order guarantees each chosen element becomes a fixed point after reindexing. This works because picking the earliest valid match always preserves the maximum remaining opportunities for larger targets. The result is target - 1 fixed points.

This greedy strategy mirrors subsequence matching patterns used in problems involving ordered constraints. The idea also appears in variations of greedy algorithms and subsequence construction problems related to arrays and dynamic programming.

Recommended for interviews: Start by explaining that the final array must equal the sequence 1..k. Mentioning the brute force or DP interpretation shows understanding of the constraint. Interviewers typically expect the greedy scan because it reduces the problem to a simple subsequence match with O(n) time and constant space.