Consecutive Subsequence
You are given an integer array nums of length n.
Your task is to find the maximum length of a consecutive subsequence of nums.
A consecutive subsequence is formed by taking some elements from the original array (without changing their relative order) such that each subsequent element is exactly 1 greater than the previous one.
If there are multiple subsequences of the maximum length, you must output the one where the sequence of indices is lexicographically smallest.
Output the 1-based indices of the elements forming the subsequence.
Example 1:
Input : n = 7 , nums = [3, 3, 4, 7, 5, 6, 8]
Output : [1, 3, 5, 6]
Explanation: Subsequence: 3 → 4 → 5 → 6
Indices: [1, 3, 5, 6]
It could even have been [2, 3, 5, 6] but it is not the lexicographically smallest hence the answer would be
Example 2:
Input: n = 6 , nums = [1,3,5,2,4,6]
Output : [1, 4]
Explanation : Possible subsequences : 1 → 2 , 3 → 4, 5 →6
but since 1 → 2 is at [1, 4] (lexicographically smallest it should be reported as the answer)
Now Your Turn!
Pick the correct output for the given inputInput : n = 6 , nums = [1,2,2,3,3,4]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= n <= 2 * 105
- 1 <= nums[i] <= 109