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.
time complexity is O(N*log(N))
space complexity is O(N)
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 O-complexity 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.
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
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.