Katkat
Back

Maximize Fixed Positions After Deletions

Point72Software Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to use dynamic programming and data structures to maximize elements in a subsequence that align with their new indices after removing elements.

Problem Description

Given an array of integers nums, you want to choose a subsequence of the array such that you maximize the number of indices i (1-based) where subsequence[i] == i.

When you form a subsequence, the elements keep their relative order, and their new 1-based index is determined by their position in the resulting subsequence. If you select elements at original indices p1, p2, ..., pk (where p1 int:

Constraints

  • 1 <= len(nums) <= 200,000
  • 1 <= nums[i] <= 200,000

Examples

Example 1: Input: nums = [1, 5, 2, 3] Output: 3 Explanation: Choosing the subsequence [1, 2, 3] results in positions 1, 2, and 3 matching the values. All three match.

Example 2: Input: nums = [2, 2, 3] Output: 2 Explanation: Choosing the subsequence [2, 3] results in position 1 having value 2 (no match) and position 2 having value 3 (no match). Choosing [2, 2] gives one match. Choosing [?, 3] where ? is any index gives one match. However, picking [2, 3] doesn't work, but picking indices 0 and 2 gives [2, 3] (size 2), while picking indices 1 and 2 gives [2, 3] (size 2). Actually, picking [2, 2] gives one match. The optimal is picking [2, 3] where 2 is at index 2 (wait, 2 is at index 2), so we get one match.

Edge Cases

  • Array contains values larger than the array length.
  • Array contains duplicates.
  • Empty array or array where no nums[i] == i is possible.

Hints

Hint 1

An element `nums[i]` can be a fixed point at index `k` if there are exactly `k-1` elements chosen from the original indices `0` to `i-1`.

Hint 2

For a fixed element `nums[i]`, it can be a fixed point if `nums[i] <= i + 1` (using 0-based indexing for `i`), and we have enough preceding elements to fill the gap `nums[i] - 1`.

Hint 3

Consider processing elements by value; if `nums[i] = v`, you need to have already selected `v-1` elements that appeared before index `i`.

Follow-up questions

  • How does the complexity change if we require the subsequence to use exactly half of the original array's length?
  • If the array were circular, how would you redefine the fixed-point condition?
  • Can you solve this if you are allowed to modify the values of the array by at most `k` units?