Problem

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

Examples

Example 1:

1
2
3

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:

1
2
3

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

Example 3:

1
2

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

Solution

Here is the video explanation of below approaches:

Method 1 - Brute Force

We can use three nested loops to check all possible triplets. This approach is simple but not efficient for larger values of ( n ) (time complexity O(n^3)).

Method 2 - Count Left and Right

  • For each soldier at index ( j ), we can count the number of soldiers before ( j ) that are either less than or greater than the rating of ( j ).
  • Similarly, count the number of soldiers after ( j ) that are either less than or greater than the rating of ( j ).
  • Using these counts, we can determine the number of valid teams for which ( j ) is the middle soldier.

We will iterate through each soldier to collect these counts and then compute the number of valid teams.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {

	public int numTeams(int[] rating) {
		int n = rating.length;
		int count = 0;

		for (int j = 0; j < n; j++) {
			int leftSmaller = 0;
			int leftGreater = 0;
			int rightSmaller = 0;
			int rightGreater = 0;

			// Count soldiers before j
			for (int i = 0; i < j; i++) {
				if (rating[i]<rating[j]) {
					leftSmaller++;
				} else if (rating[i] > rating[j]) {
					leftGreater++;
				}
			}

			// Count soldiers after j
			for (int k = j + 1; k < n; k++) {
				if (rating[k]<rating[j]) {
					rightSmaller++;
				} else if (rating[k] > rating[j]) {
					rightGreater++;
				}
			}

			// Valid teams with j as the middle soldier
			count += (leftSmaller * rightGreater) + (leftGreater * rightSmaller);
		}

		return count;
	}

}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 3 - Recursion

  • This problem is a variation of the Longest Increasing Subsequence LIS.
  • Instead of finding the LIS and Longest Decreasing Subsequence (LDS), we need to count the total number of increasing and decreasing subsequences of length 3 in the given array.
  • While LIS determines the maximum length of increasing subsequences, our goal here is to specifically focus on subsequences of length 3.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Solution {

    public int numTeams(int[] rating) {
        
        int ans1 = dfsAsc(rating, 0, -1, 3);

        int ans2 = dfsDesc(rating, 0, -1, 3);

        return ans1+ans2;

    }

    public int dfsAsc(int[] rating, int ind, int prev, int count){

        if(count == 0){
            return 1;
        }

        if(ind == rating.length){
            return 0;
        }

        int notPick = dfsAsc(rating, ind+1, prev, count);

        int pick = 0;

        if(prev == -1 || rating[ind]>rating[prev]){
            pick = dfsAsc(rating, ind+1, ind, count-1);
        }

        return pick + notPick;

    }
    
    public int dfsDesc(int[] rating, int ind, int prev, int count){

        if(count == 0){
            return 1;
        }

        if(ind == rating.length){
            return 0;
        }

        int notPick = dfsDesc(rating, ind+1, prev, count);

        int pick = 0;

        if(prev == -1 || rating[ind]<rating[prev]){
            pick = dfsDesc(rating, ind+1, ind, count-1);
        }

        return pick + notPick;

    }
}

Complexity

  • ⏰ Time complexity: O(2^n)
    • Each element can be either included or excluded, leading to (O(2^n)) combinations in total.
    • For each combination, checking if it forms a valid team takes constant time.
  • 🧺 Space complexity: O(n) for recursion stack

Method 4 - Top Down DP with memoization

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

class Solution {

	private Integer[][][] dpAsc;
    private Integer[][][] dpDesc;
    
    public int numTeams(int[] rating) {
        dpAsc = new Integer[rating.length][rating.length+1][4];
		dpDesc = new Integer[rating.length][rating.length+1][4];
        int ans1 = dfsAsc(rating, 0, -1, 3);

        int ans2 = dfsDesc(rating, 0, -1, 3);

        return ans1+ans2;

    }

    public int dfsAsc(int[] rating, int ind, int prev, int count){

        if(count == 0){
            return 1;
        }

        if(ind == rating.length){
            return 0;
        }

        if(dpAsc[ind][prev+1][count]!=null){
            return dpAsc[ind][prev+1][count];
        }


        int notPick = dfsAsc(rating, ind+1, prev, count);

        int pick = 0;

        if(prev == -1 || rating[ind]>rating[prev]){
            pick = dfsAsc(rating, ind+1, ind, count-1);
        }

        return dpAsc[ind][prev+1][count] = pick + notPick;

    }
    
    public int dfsDesc(int[] rating, int ind, int prev, int count){
		
        if(count == 0){
            return 1;
        }

        if(ind == rating.length){
            return 0;
        }
        if(dpDesc[ind][prev+1][count]!=null){
            return dpDesc[ind][prev+1][count];
        }


        int notPick = dfsDesc(rating, ind+1, prev, count);

        int pick = 0;

        if(prev == -1 || rating[ind]<rating[prev]){
            pick = dfsDesc(rating, ind+1, ind, count-1);
        }

        return dpDesc[ind][prev+1][count] = pick + notPick;

    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
    • The function is called with different values of (ind, prev, count).
    • ind ranges from 0 to n.
    • prev can be any of the n indices or -1, resulting in n + 1 possible values.
    • count ranges from 0 to 3.
  • 🧺 Space complexity: O(n^2) due to memoization table and recursion stack (of size of O(n))

Method 5 - Bottom up DP

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    
	public int numTeams(int [] rating) {

		int n = rating.length;

		int [] dp = new int[n];

		int count = 0;

		for (int i=0; i< n; i++) {
			for (int j=i; j>=0; j--) {
				if (rating[i] < rating[j]) {
					dp[i] += 1;
					count += dp[j];
				}
			}
		}

		dp = new int[n];

		for (int i=0; i<n; i++) {
			for (int j=i; j>=0; j--) {
				if (rating[i] > rating[j]) {
					dp[i] += 1;
					count += dp[j];
				}
			}
		}

		return count;

    }

}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n^2)