Problem

You are given a 0-indexed array nums consisting of positive integers.

Initially, you can increase the value of any element in the array by at most 1.

After that, you need to select one or more elements from the final array such that those elements are consecutive when sorted in increasing order. For example, the elements [3, 4, 5] are consecutive while [3, 4, 6] and [1, 1, 2, 3] are not.

Return themaximum number of elements that you can select.

Examples

Example 1

1
2
3
4
5

Input: nums = [2,1,5,1,1]
Output: 3
Explanation: We can increase the elements at indices 0 and 3. The resulting array is nums = [3,1,5,2,1].
We select the elements [_**3**_ ,_**1**_ ,5,_**2**_ ,1] and we sort them to obtain [1,2,3], which are consecutive.
It can be shown that we cannot select more than 3 consecutive elements.

Example 2

1
2
3

Input: nums = [1,4,7,10]
Output: 1
Explanation: The maximum consecutive elements that we can select is 1.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

Solution

Method 1 – Sliding Window with Frequency Map

Intuition

Since each element can be increased by at most 1, every number in the array can become either itself or itself + 1. To maximize the length of a consecutive sequence, we can try to “shift” as many numbers as possible to fill consecutive slots. By counting the frequency of each possible value (original and original+1), we can use a sliding window to find the longest streak of consecutive numbers.

Approach

  1. For each number in nums, increment the count for both num and num+1 in a frequency map.
  2. Sort the unique keys of the frequency map.
  3. Use a sliding window over the sorted keys:
    • Expand the window as long as the numbers are consecutive.
    • If a gap is found, move the left pointer forward.
    • Track the sum of frequencies in the current window.
  4. The maximum sum found in any window is the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int maxSelectedElements(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int x : nums) {
            freq[x]++;
            freq[x+1]++;
        }
        vector<int> keys;
        for (auto& p : freq) keys.push_back(p.first);
        sort(keys.begin(), keys.end());
        int ans = 0, l = 0, sum = 0;
        for (int r = 0; r < keys.size(); ++r) {
            if (r > 0 && keys[r] != keys[r-1] + 1) {
                l = r;
                sum = 0;
            }
            sum += freq[keys[r]];
            while (l < r && sum - freq[keys[l]] >= sum) {
                sum -= freq[keys[l++]];
            }
            ans = max(ans, sum);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func maxSelectedElements(nums []int) int {
    freq := map[int]int{}
    for _, x := range nums {
        freq[x]++
        freq[x+1]++
    }
    keys := []int{}
    for k := range freq {
        keys = append(keys, k)
    }
    sort.Ints(keys)
    ans, l, sum := 0, 0, 0
    for r := 0; r < len(keys); r++ {
        if r > 0 && keys[r] != keys[r-1]+1 {
            l = r
            sum = 0
        }
        sum += freq[keys[r]]
        ans = max(ans, sum)
    }
    return ans
}
func max(a, b int) int { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int maxSelectedElements(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) {
            freq.put(x, freq.getOrDefault(x, 0) + 1);
            freq.put(x+1, freq.getOrDefault(x+1, 0) + 1);
        }
        List<Integer> keys = new ArrayList<>(freq.keySet());
        Collections.sort(keys);
        int ans = 0, l = 0, sum = 0;
        for (int r = 0; r < keys.size(); r++) {
            if (r > 0 && keys.get(r) != keys.get(r-1) + 1) {
                l = r;
                sum = 0;
            }
            sum += freq.get(keys.get(r));
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun maxSelectedElements(nums: IntArray): Int {
        val freq = mutableMapOf<Int, Int>()
        for (x in nums) {
            freq[x] = freq.getOrDefault(x, 0) + 1
            freq[x+1] = freq.getOrDefault(x+1, 0) + 1
        }
        val keys = freq.keys.sorted()
        var ans = 0
        var l = 0
        var sum = 0
        for (r in keys.indices) {
            if (r > 0 && keys[r] != keys[r-1] + 1) {
                l = r
                sum = 0
            }
            sum += freq[keys[r]]!!
            ans = maxOf(ans, sum)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def maxSelectedElements(self, nums: list[int]) -> int:
        from collections import Counter
        freq = Counter()
        for x in nums:
            freq[x] += 1
            freq[x+1] += 1
        keys = sorted(freq)
        ans = l = sum_ = 0
        for r in range(len(keys)):
            if r > 0 and keys[r] != keys[r-1] + 1:
                l = r
                sum_ = 0
            sum_ += freq[keys[r]]
            ans = max(ans, sum_)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn max_selected_elements(nums: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        for &x in &nums {
            *freq.entry(x).or_insert(0) += 1;
            *freq.entry(x+1).or_insert(0) += 1;
        }
        let mut keys: Vec<_> = freq.keys().cloned().collect();
        keys.sort();
        let mut ans = 0;
        let mut l = 0;
        let mut sum = 0;
        for r in 0..keys.len() {
            if r > 0 && keys[r] != keys[r-1] + 1 {
                l = r;
                sum = 0;
            }
            sum += freq[&keys[r]];
            ans = ans.max(sum);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    maxSelectedElements(nums: number[]): number {
        const freq: Record<number, number> = {};
        for (const x of nums) {
            freq[x] = (freq[x] || 0) + 1;
            freq[x+1] = (freq[x+1] || 0) + 1;
        }
        const keys = Object.keys(freq).map(Number).sort((a, b) => a - b);
        let ans = 0, l = 0, sum = 0;
        for (let r = 0; r < keys.length; r++) {
            if (r > 0 && keys[r] !== keys[r-1] + 1) {
                l = r;
                sum = 0;
            }
            sum += freq[keys[r]];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — for sorting the unique values and iterating through them.
  • 🧺 Space complexity: O(n) — for the frequency map and storing unique values.