0

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.

Improve this question
1
  • Is this problem online somewhere so we can try submitting our solutions there? Commented Mar 20, 2021 at 8:21

2 Answers 2

Reset to default
1

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]
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

I have come up with this (in Java):

public int countSubSequences(int[] array){
    int numberOfSubSequences = 0;
    for (int i = 0; i < array.length-1; i++) {
        if(array[i]>array[i+1]){
            numberOfSubSequences++;
        }
    }
    numberOfSubSequences++;
    return numberOfSubSequences;
}

I just iterate through the array and check if the next element in the array is smaller than my current element. If that is the case the current element is the end of a subsequence, and we can increment our count. Before returning we need to increment too because the end of the array is also the end of the last subsequence.

Time complexity is linear so O=(n) and space complexity should be constant O=(1) as we don't need to remember the subsequences with this method in order to count them.

Improve this answer

4 Comments

'check if the next element in the array is smaller than my current element. If that is the case the next element is the end of a subsequence'. In my example the first case of such would be 5, but 6 is already the beginning of another such subsequence. Sorry I didn't really follow
Also the end of the first subsequence meets the requirement is actually 4.
I made an error in explaining. I meant If that is the case the current element is the end of a subsequence. Are you sure the subsequences from [1,2,3,6,5,4,7,8,9] should be [1,2,3,4], [6,7,8,9], [5] and not [1,2,3,6][5][4,7,8,9]?
For example for [1,6,2,7,3,8,4,9,5] you return 5. Correct answer is 2 (since the subsequences are [1,2,3,4,5] and [6,7,8,9]).

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.