1395. Count Number of Teams

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).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

---

Intuition

DFS - Number of combinations

Permutations are not expected, so increment current index by 1 in each DFS call

---

	class Solution {
	public int numTeams(int[] rating) {
	if (rating == null \|\| rating.length < 3) {
	return 0;
	}

	return dfs(rating, 0, new ArrayList<Integer>(), true) + dfs(rating, 0, new ArrayList<Integer>(), false);
	}

	private int dfs(int[] rating, int current, List<Integer> list, boolean isIncreasing) {
	if (list.size() == 3) {
	return 1;
	}

	int ans = 0;
	for (int i = current; i < rating.length; i++) {
	if (list.size() == 0 \|\| (isIncreasing && rating[i] > list.get(list.size() - 1)) \|\| (!isIncreasing && rating[i] < list.get(list.size() - 1))) {

	list.add(rating[i]);
	ans += dfs(rating, i + 1, list, isIncreasing);
	list.remove(list.size() - 1);
	}
	}
	return ans;
	}
	}

SWE Interview preparation