This is one of those problems where the clean idea matters more than the amount of code. For 1395. Count Number of Teams, the solution in this repository is mainly a two pointers solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, sliding window, prefix sums, backtracking.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are isValid, backtrack, numTeams, smaller, update.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N^2), space: O(1)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//Runtime: 344 ms, faster than 5.07% of C++ online submissions for Count Number of Teams.
02//Memory Usage: 7.7 MB, less than 100.00% of C++ online submissions for Count Number of Teams.
03class Solution {
04public:
05 vector<int> rating;
06 int ans;
07
08 bool isValid(vector<int>& comb){
09 int i = comb[0], j = comb[1], k = comb[2];
10 //0 <= i < j < k < n must hold
11 if(rating[i] > rating[j] && rating[j] > rating[k]){
12 return true;
13 }
14 if(rating[i] < rating[j] && rating[j] < rating[k]){
15 return true;
16 }
17 return false;
18 };
19
20 void backtrack(vector<int>& comb, int start, int end){
21 if(comb.size() == 3){
22 if(isValid(comb)){
23 ans++;
24 }
25 return;
26 }
27 for(int i = start; end-i+1 >= 3-comb.size(); i++){
28 // cout << "aaa: " << end-i+1 << ", " << 3-comb.size() << endl;
29 // cout << start << ", " << end << endl;
30 comb.push_back(i);
31 backtrack(comb, i+1, end);
32 comb.pop_back();
33 }
34 };
35
36 int numTeams(vector<int>& rating) {
37 ans = 0;
38 this->rating = rating;
39
40 vector<int> comb;
41
42 backtrack(comb, 0, rating.size()-1);
43
44 return ans;
45 }
46};
47
48//https://leetcode.com/problems/count-number-of-teams/discuss/554795/C%2B%2BJava-O(n-*-n)
49//Runtime: 8 ms, faster than 87.37% of C++ online submissions for Count Number of Teams.
50//Memory Usage: 7.8 MB, less than 100.00% of C++ online submissions for Count Number of Teams.
51//time: O(N^2), space: O(1)
52class Solution {
53public:
54 int numTeams(vector<int>& rating) {
55 int N = rating.size();
56 int ans = 0;
57
58 for(int i = 1; i < N-1; i++){
59 vector<int> smaller(2), larger(2);
60
61 for(int j = 0; j < N; j++){
62 //whether j is at the left of i
63 int left = (j < i);
64 if(rating[i] < rating[j]){
65 smaller[left]++;
66 }
67 if(rating[i] > rating[j]){
68 larger[left]++;
69 }
70 }
71
72 ans += smaller[0]*larger[1] + smaller[1]*larger[0];
73 }
74
75 return ans;
76 }
77};
78
79//Binary Indexed Tree, BIT
80//https://leetcode.com/problems/count-number-of-teams/discuss/554907/Java-Detailed-Explanation-TreeSet-greater-BIT-(Fenwick-Tree)-O(NlogN)
81//Runtime: 16 ms, faster than 73.69% of C++ online submissions for Count Number of Teams.
82//Memory Usage: 55.6 MB, less than 100.00% of C++ online submissions for Count Number of Teams.
83class Solution {
84public:
85 void update(vector<int>& BIT, int idx, int val){
86 while(idx < BIT.size()){
87 BIT[idx] += val;
88 idx += idx & (-idx);
89 }
90 };
91
92 int getPrefixSum(vector<int>& BIT, int idx){
93 int sum = 0;
94
95 while(idx > 0){
96 sum += BIT[idx];
97 idx -= idx & (-idx);
98 }
99
100 return sum;
101 };
102
103 int getSuffixSum(vector<int>& BIT, int idx){
104 return getPrefixSum(BIT, BIT.size()-1) - getPrefixSum(BIT, idx-1);
105 };
106
107 int numTeams(vector<int>& rating) {
108 int N = rating.size();
109 if(N < 3) return 0;
110
111 //rating's range: [1, 1e5]
112 //use rating as index, and count as value
113 vector<int> leftTree(1e5+1, 0);
114 vector<int> rightTree(1e5+1, 0);
115
116 for(int r : rating){
117 update(rightTree, r, 1);
118 }
119
120 int ans = 0;
121
122 //store the count of each rating into rightTree
123 for(int r : rating){
124 //rightTree contains the info of soldiers to the right of current soldier, so we need to remove the info of current soldier from rightTree
125 update(rightTree, r, -1);
126
127 ans += getPrefixSum(leftTree, r-1)*getSuffixSum(rightTree,r+1);
128 ans += getSuffixSum(leftTree, r+1)*getPrefixSum(rightTree, r-1);
129
130 //record current soldier's info into leftTree
131 update(leftTree, r, 1);
132 }
133
134 return ans;
135 }
136};Cost