CODEWITHSUNDEEP
algorithmdata-structures
F5673
F5673

Reputation: 51

Finding number of length 3 increasing (or decreasing) subsequences?

Given an array of positive integers, how can I find the number of increasing (or decreasing) subsequences of length 3? E.g. [1,6,3,7,5,2,9,4,8] has 24 of these, such as [3,4,8] and [6,7,9].

I've found solutions for length k, but I believe those solutions can be made more efficient since we're only looking at k = 3.

For example, a naive O(n^3) solution can be made faster by looping over elements and counting how many elements to their left are less, and how many to their right are higher, then multiplying these two counts, and adding it to a sum. This is O(n^2), which obviously doesn't translate easily into k > 3.

Upvotes: 4

Views: 2583

Answers (2)

Pankaj
Pankaj

Reputation: 2110

For each curr element, count how many elements on the left and right have less and greater values.

This curr element can form less[left] * greater[right] + greater[left] * less[right] triplet.

Complexity Considerations

The straightforward approach to count elements on left and right yields a quadratic solution. You might be tempted to use a set or something to count solders in O(log n) time.

You can find a solder rating in a set in O(log n), however, counting elements before and after will still be linear. Unless you implement BST where each node tracks count of left children.

Check the solution here:

https://leetcode.com/problems/count-number-of-teams/discuss/554795/C%2B%2BJava-O(n-*-n)

Upvotes: 0

Humam Tlay
Humam Tlay

Reputation: 29

The solution can be by looping over elements, on every element you can count how many elements to their left and less be using segment tree algorithm which work in O(log(n)), and by this way you can count how many elements to their right and higher, then multiplying these two counts, and adding it to the sum. This is O(n*log(n)).

You can learn more about segment tree algorithm over here: Segment Tree Tutorial

Upvotes: 3

Related Questions