0

I am NOT looking to find the largest increasing subsequence.

I have a NumPy array similar to the following:

[0, 1, 5, 2, 4, 8, 8, 6, 10]

I need to find the indices of the elements that form a strictly increasing subsequence, with priority being given to earlier indices. So, for the above input, I would expect the output to be the following NumPy array:

[0, 1, 2, 5, 8]

I imagine the numbers representing the heights of buildings in a row, and I want to find the indices of the buildings I can see from one end.

I can easily do this with a for loop over the array elements, keeping track of the maximum value seen so far. But I was hoping that there exists a NumPy-based one line solution that would directly generate a NumPy int array.

Improve this question
3
  • 2
    How long is your data? If it's short enough, I would probably just do it with a loop rather than try to contort it into a numpy form. Commented Nov 1, 2023 at 22:19
  • Why do you hope for a one line solution? Trying to save some bytes in file size? Commented Nov 1, 2023 at 22:19
  • The data is several hundreds to thousands of elements in size. @Joe I'm seeking an elegant solution to hopefully expand my knowledge of NumPy that I might be able to reuse later. I've found a lot of functionality that I did not know about by reading the docs that would have otherwise required me to create for loops. Commented Nov 1, 2023 at 22:59

2 Answers 2

Reset to default
3

Maybe this could help

x = [0, 1, 5, 2, 4, 8, 8, 6, 10]
u, idx = np.unique(np.maximum.accumulate(x), return_index=True)

or might be more efficient

k = np.nonzero(np.diff(np.maximum.accumulate(x)))
idx = np.append(k[0][0],np.add(k,1))

where idx gives the indices

[0 1 2 5 8]
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

The unique call could be slow for a large array; a faster way might be to use np.diff with np.nonzero to find the indices
@lxop i didn't check that but I believe you are right. see my update
Using the prepend arguement to np.diff allows you to skip the append operation entirely: np.nonzero(np.diff(np.maximum.accumulate(x), prepend=[-1]))
@Woodford That's a good option, thanks! You prepend=[-1] since you know that 0 is the starting point of the strictly increasing subsequence. However, if the first entry is 2 for example, I don't think it would work properly.
-1

I don't know if you consider this "NumPy-based", but how about this:

import numpy as np
arr = np.array([0,1,5,2,4,8,8,6,10])
np.array([i for i in range(len(arr)) if all(arr[:i] < arr[i])])
Improve this answer

4 Comments

If someone doesn't think my answer is helpful, I'd appreciate the feedback in a comment.
That was me. Just converting a list to a numpy array doesn't make the solution "numpy-based". This is just a loop in Python, which is what OP has stated that they already can do.
Yeah, I wasn't sure if this would be considered Nump-based. It's not a for loop, which the OP didn't want, and it is a one liner, which the OP did want. I also don't know why the OP hopes for a NumPy function/method. Performance?
Sure it's a for loop - it's right there in your last line. OP hasn't stated why they want a numpy approach, but I would assume it is for performance, since that's the main reason for using numpy. I didn't read too much into the "one-line" requirement, and took that to just mean "numpy already has something to do this".

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.