Maximize Fixed Positions After Deletions
Company: Point72
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
Given an integer array `a`, delete zero or more elements while preserving the relative order of the elements that remain. Let the resulting array be `b`, indexed from `1`.
The beauty of `b` is the number of positions `i` such that `b[i] == i`. Return the maximum beauty obtainable by choosing which elements to delete. Elements that do not satisfy the equality may remain when keeping them helps position later elements; the objective is the number of matching positions, not the length of `b`.
## Constraints
- `1 <= a.length <= 200,000`
- `-1,000,000,000 <= a[i] <= 1,000,000,000`
- The answer is an integer between `0` and `a.length`.
- A backtracking solution that enumerates retained subsequences is too slow for the largest inputs.
## Example 1
```text
a = [1, 4, 2, 3, 5]
```
Deleting `4` produces `[1, 2, 3, 5]`. Its first three positions match their values, so the maximum beauty is `3`.
## Example 2
```text
a = [2, 2, 2]
```
Keeping any two elements produces `[2, 2]`, whose second position matches. The maximum beauty is `1`.
Quick Answer: Choose a subsequence of an integer array that maximizes positions whose retained value equals its one-based index. Reason about deletions, shifted positions, useful nonmatching elements, edge cases, and scalability to two hundred thousand inputs.
Given an integer array `a`, delete zero or more of its elements. The elements you keep stay in their original relative order and together form a new array `b`, which is indexed starting from `1`.
The **beauty** of `b` is the number of positions `i` such that `b[i] == i`.
Return the maximum beauty obtainable over every choice of which elements to delete. Elements that do not satisfy the equality may remain when keeping them helps position later elements, because every kept element pushes each later element one position further right; the objective is the number of matching positions, not the length of `b`.
Deleting everything is allowed and leaves `b` empty with beauty `0`, so the answer is never negative.
Return a single integer, the maximum beauty. That number is uniquely determined even though several different sets of deletions may attain it -- you are never asked to report which elements to delete.
## Constraints
- `1 <= a.length <= 200000`
- `-1000000000 <= a[i] <= 1000000000`
- The answer is an integer between `0` and `a.length`.
- A backtracking solution that enumerates retained subsequences is too slow for the largest inputs.
- Every natural intermediate fits in a signed 32-bit integer: the largest magnitude reached by comparing or subtracting an index and a value is `|a[i]| + a.length <= 1000200000 < 2^31 - 1`, and the answer is at most `200000`. No 64-bit widening is required.
## Example 1
```text
a = [1, 4, 2, 3, 5]
answer = 3
```
Deleting `4` produces `b = [1, 2, 3, 5]`. Positions `1`, `2` and `3` hold `1`, `2` and `3`, so three positions match. Position `4` holds `5` and does not.
## Example 2
```text
a = [2, 2, 2]
answer = 1
```
Keeping any two of the elements produces `b = [2, 2]`, whose second position matches. No choice of deletions can match two positions at once, because both would need the value `2` to sit at two different positions.
## Example 3
```text
a = [1, 5, 2, 6, 3, 7, 4, 8, 9, 10]
answer = 4
```
Deleting nothing already matches positions `1`, `8`, `9` and `10`. Deleting `5`, `6` and `7` instead gives `b = [1, 2, 3, 4, 8, 9, 10]`, which matches positions `1` through `4`. Both choices reach `4`, and the two groups cannot be combined: the three deletions that pull `2`, `3` and `4` into place simultaneously shift `8`, `9` and `10` off theirs.
Constraints
- 1 <= a.length <= 200000
- -1000000000 <= a[i] <= 1000000000
- The answer is an integer between 0 and a.length
- A backtracking solution that enumerates retained subsequences is too slow for the largest inputs
- Every natural intermediate fits in a signed 32-bit integer: |index - a[index]| <= 1000200000 < 2^31 - 1 and the answer is at most 200000
Examples
Input: ([1, 4, 2, 3, 5],)
Expected Output: 3
Explanation: Source example 1. Deleting 4 gives [1, 2, 3, 5], matching positions 1, 2 and 3. Rejects a solution that only takes a longest strictly increasing run of reachable values, which would answer 4.
Input: ([2, 2, 2],)
Expected Output: 1
Explanation: Source example 2. Two entries share the value 2, and only one of them can ever occupy position 2, so ties on the value must not both be counted (a wrong tie-break answers 2).
Hints
- If the element originally at 1-based index j survives and lands on position i of b, then exactly j - i earlier elements were deleted. Rewrite the matching condition b[i] == i using only j and a[j], and work out which indices can never be matched at all.
- The number of deleted elements can only grow from left to right, and between two kept elements you can delete at most the elements strictly between them. Turn each of those two facts into a condition relating two matched indices.
- Each candidate match is now a point with two coordinates that must move in fixed directions, so the answer is a longest-chain length. One sort reduces it to a longest non-decreasing subsequence -- the only subtlety is which direction to break ties in so that two candidates sharing a coordinate can never both be counted.