Assume given an array [1, 2, 3, ..., n]. Now randomly shuffle it. What is the best way (in terms of time and space complexity to find the number of unique consecutively increasing subsequences in the shuffled array?
As an example, a=[1,2,3,6,5,4,7,8,9] there are 3 such subsequences: [1,2,3,4], [6,7,8,9], [5]. ([5] trivially fulfills the definition)
Thanks in advance.
Edit: One approach I was thinking is that whenever we encounter a new element check if it is +1 of the previous element, if not put it in a new array. But when there are many such arrays then checking if the next element is +1 of the last element of any of the existing array takes longer time. So the space complexity is n, but time taken in the worst case a=[n,n-1,n-2,...,1] is 1 + 2 + 3 +...+ n-1=O(n^2). But there might be a better way.
Edit 2: Sorry I just realized that being able to output the explicit forms of those subsequences are also important (as shown in the example given). So there are two best complexity cases, one for counting the number and the other one for outputting the explicit forms.
You could count the streaks by counting the streak starts. A value x is a streak start iff you haven't seen x - 1 before. In your example, that's 1, 6 and 5. Takes O(n) time and space.
a = [1,2,3,6,5,4,7,8,9]
streaks = 0
seen = set()
for x in a:
if x - 1 not in seen:
streaks += 1
seen.add(x)
print(streaks)
Output, Try it online!:
3
Can be O(1) space if you allow modification of a (e.g., remember x as seen by negating a[x-1]).
a = [1,2,3,6,5,4,7,8,9]
streaks = 0
for x in map(abs, a):
if a[x-2] > 0:
streaks += 1
a[x-1] *= -1
print(streaks)
Output, Try it online!:
3
A version collecting the streaks, O(n) time and space:
a = [1,2,3,6,5,4,7,8,9]
streaks = {}
for x in a:
streak = streaks.pop(x - 1, [])
streak.append(x)
streaks[x] = streak
print(*streaks.values())
Output, Try it online!:
[5] [1, 2, 3, 4] [6, 7, 8, 9]