Problem Description
There are n soldiers standing in a line. Each soldier is assigned a unique rating value. You have to form a team of 3 soldiers amongst them under the following rules: Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]). A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n). Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).
Key Insights
- A valid team consists of three soldiers whose ratings are either strictly increasing or strictly decreasing.
- For each soldier at position j, count how many soldiers to the left (i) and to the right (k) can form valid teams with j.
- Use two nested loops to count potential team members for each soldier.
Space and Time Complexity
Time Complexity: O(n^2)
Space Complexity: O(1)
Solution
To solve this problem, we can use a brute-force approach where we iterate through each soldier as a potential middle member of a team. For each soldier at index j, we count how many soldiers to the left (i) can form a valid team with j and how many soldiers to the right (k) can also form a valid team. We accumulate the count of valid combinations based on the conditions given for increasing and decreasing sequences.