{"id":6549,"date":"2020-03-28T21:55:23","date_gmt":"2020-03-29T04:55:23","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6549"},"modified":"2020-03-29T12:03:01","modified_gmt":"2020-03-29T19:03:01","slug":"leetcode-1395-count-number-of-teams","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1395-count-number-of-teams\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1395. Count Number of Teams"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1395. Count Number of Teams - \u5237\u9898\u627e\u5de5\u4f5c EP317\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/HrU-xrUnb8g?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>There are&nbsp;<code>n<\/code>&nbsp;soldiers standing in a line. Each soldier is assigned a&nbsp;<strong>unique<\/strong>&nbsp;<code>rating<\/code>&nbsp;value.<\/p>\n\n\n\n<p>You have to form a team of 3 soldiers&nbsp;amongst them under the following rules:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Choose 3 soldiers with index (<code>i<\/code>,&nbsp;<code>j<\/code>,&nbsp;<code>k<\/code>) with&nbsp;rating (<code>rating[i]<\/code>,&nbsp;<code>rating[j]<\/code>,&nbsp;<code>rating[k]<\/code>).<\/li><li>A team is valid if:&nbsp; (<code>rating[i] &lt; rating[j] &lt; rating[k]<\/code>) or (<code>rating[i] &gt; rating[j] &gt; rating[k]<\/code>) where (<code>0&nbsp;&lt;= i &lt;&nbsp;j &lt;&nbsp;k &lt;&nbsp;n<\/code>).<\/li><\/ul>\n\n\n\n<p>Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> rating = [2,5,3,4,1]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). \n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> rating = [2,1,3]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> We can't form any team given the conditions.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> rating = [1,2,3,4]\n<strong>Output:<\/strong> 4\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == rating.length<\/code><\/li><li><code>1 &lt;= n &lt;= 200<\/code><\/li><li><code>1 &lt;= rating[i] &lt;= 10^5<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Brute Force<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n^3)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int numTeams(vector<int>& rating) {\n    int n = rating.size();\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      for (int j = i + 1; j < n; ++j)\n        for (int k = j + 1; k < n; ++k)\n          if (rating[i] < rating[j] &#038;&#038; rating[j] < rating[k]\n             || rating[i] > rating[j] && rating[j] > rating[k])\n            ++ans;\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Math<\/strong><\/h2>\n\n\n\n<p>For each soldier j, count how many soldiers on his left has smaller ratings as left[j], count how many  soldiers his right side has larger ratings as right[j]<\/p>\n\n\n\n<p>ans = sum(left[j] * right[j] + (j &#8211; left[j]) * (n &#8211; j &#8211; 1 * right[j])<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 4 ms\nclass Solution {\npublic:\n  int numTeams(vector<int>& rating) {\n    int n = rating.size();\n    int ans = 0;\n    for (int j = 0; j < n; ++j) {\n      int l = 0;\n      int r = 0;\n      for (int i = 0; i < j; ++i)\n        if (rating[i] < rating[j]) ++l;\n      for (int k = j + 1; k < n; ++k)\n        if (rating[j] < rating[k]) ++r;\n      ans += (l * r) + (j - l) * (n - j - 1 - r);\n    }  \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>There are&nbsp;n&nbsp;soldiers standing in a line. Each soldier is assigned a&nbsp;unique&nbsp;rating&nbsp;value. You have to form a team of 3 soldiers&nbsp;amongst them under the following rules:&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,177,97],"class_list":["post-6549","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-medium","tag-prefix","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6549","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6549"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6549\/revisions"}],"predecessor-version":[{"id":6555,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6549\/revisions\/6555"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6549"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6549"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6549"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}