Find each element that is less than some element to its right

Question

I need to find elements of a vector that are less than one of more elements that come after it. It's easy to do in a loop:

x = some_vector_values;
for m = 1 : length(x)
  if( any( x(m+1:end) > x(m) )
    do_such_and_such;
  end
end

but the speed is killing me. I'm scratching my head trying to come up with an efficient work-around but am coming up blank. The array length can be on the order of thousands and I need to do this for many different arrays.

Answer 1

This uses a divide-and-conquer approach (similar to binary search):

1. Find the maximum of the vector.
2. All elements to its left are accepted, whereas the maximum itself is rejected.
3. For those elements to the right of the maximum, apply step 1.

Although I haven't done a careful analysis, I think average complexity is O(n), or at most O(n log n). Memory is O(n).

The result is a logical vector ind that contains true for accepted elements and false for rejected elements. The final result would be x(ind).

x = [3 4 3 5 6 3 4 1];
n = numel(x);
ind = false(1,n); %// intiallization
s = 1; %// starting index of the part of x that remains to be analyzed
while s <= n %// if s > n we have finished
    [~, m] = max(x(s:end)); %// index of maximum within remaining part of x
    ind(s:s-2+m) = true; %// elements to its left are accepted
    s = s+m; %// update start of remaining part
end

Running time could be reduced a little by changing the while condition to while s < n, because the last element is always rejected.

Answer 2

Your algorithm is so slow since if any(...)has to check n items on the first iteration, then n-1 items on the second iteration ... until checking a single item in the last iteration. Overal it thus has to do roughly n^2/2 comparisons, so its running time is quadratic as a function of the length of the input vector!

One solution that is linear in time and memory might be to first calculate a vector with the maximum from that point until the end, which can be calculated in one backwards pass (you could call this a reversed cumulative maximum, which cannot be vectorized). After this, this vector is compared directly to x (untested):

% calculate vector mx for which mx(i) = max(x(i:end))
mx = zeros(size(x));
mx(end) = x(end);
for i = length(x)-1:-1:1 % iterate backwards
    mx(i) = max(x(i), mx(i+1));
end

for i = 1:length(x) - 1
    if mx(i) > x(i)
        do_such_and_such(i);
    end
end

In case you don't care about the order in which do_such_and_such is executed, these for loops can even be combined like so:

mx = x(end);
for i = length(x)-1:-1:1 % iterate backwards
    if x(i) < mx
        do_such_and_such(i);
    end
    mx = max(x(i), mx); % maximum of x(i:end)
end

Answer 3

This should be an algorithm that takes O(n) time and O(n) memory: Label the last element in your array the maximum element. Iterate backwards over the array. Whenever you have an element smaller than your maximum, save it. Otherwise, it becomes your new maximum. This should get you all of the elements you need with a single pass.

Answer 4

One-liner version

comparisons = any(triu(bsxfun(@gt,x(:).',x(:))),2)