Short Problem Definition:
Given an array of integers, find and print the maximum number of integers you can select from the array such that the absolute difference between any two of the chosen integers is less than or equal to 1. For example, if your array is a = [1, 1, 2, 2, 4, 4, 5, 5, 5], you can create two subarrays meeting the criterion: [1 ,1 ,2 ,2] and [4, 4, 5, 5, 5]. The maximum length subarray has 5 elements.
Link
Complexity:
time complexity is O(N*log(N))
space complexity is O(N)
Execution:
There is a simple solution. Sort the array and iterate over it, counting pairs. But I don’t like it.
The solution proposed here never sorts the array. Depending on the Ocomplexity of a map implementation, it could be O(N) or O(NlogN).
The idea is to check the +/1 neighbors of each value as you iterate over them.
Solution:
1
2
3
4
5
6
7
8
9
10

from collections import defaultdict def pickingNumbers(a): d = defaultdict( int ) r_val = 0 for val in a: d[val] + = 1 r_val = max (r_val, d[val] + d[val + 1 ], d[val] + d[val  1 ]) return r_val 