{"id":7364,"date":"2020-09-12T22:46:42","date_gmt":"2020-09-13T05:46:42","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7364"},"modified":"2020-09-12T23:10:54","modified_gmt":"2020-09-13T06:10:54","slug":"leetcode-1583-count-unhappy-friends","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1583-count-unhappy-friends\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1583. Count Unhappy Friends"},"content":{"rendered":"\n<p>You are given a list of&nbsp;<code>preferences<\/code>&nbsp;for&nbsp;<code>n<\/code>&nbsp;friends, where&nbsp;<code>n<\/code>&nbsp;is always&nbsp;<strong>even<\/strong>.<\/p>\n\n\n\n<p>For each person&nbsp;<code>i<\/code>,&nbsp;<code>preferences[i]<\/code>&nbsp;contains&nbsp;a list of friends&nbsp;<strong>sorted<\/strong>&nbsp;in the&nbsp;<strong>order of preference<\/strong>. In other words, a friend earlier in the list is more preferred than a friend later in the list.&nbsp;Friends in&nbsp;each list are&nbsp;denoted by integers from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>n-1<\/code>.<\/p>\n\n\n\n<p>All the friends are divided into pairs.&nbsp;The pairings are&nbsp;given in a list&nbsp;<code>pairs<\/code>,&nbsp;where&nbsp;<code>pairs[i] = [x<sub>i<\/sub>, y<sub>i<\/sub>]<\/code>&nbsp;denotes&nbsp;<code>x<sub>i<\/sub><\/code>&nbsp;is paired with&nbsp;<code>y<sub>i<\/sub><\/code>&nbsp;and&nbsp;<code>y<sub>i<\/sub><\/code>&nbsp;is paired with&nbsp;<code>x<sub>i<\/sub><\/code>.<\/p>\n\n\n\n<p>However, this pairing may cause some of the friends to be unhappy.&nbsp;A friend&nbsp;<code>x<\/code>&nbsp;is unhappy if&nbsp;<code>x<\/code>&nbsp;is paired with&nbsp;<code>y<\/code>&nbsp;and there exists a friend&nbsp;<code>u<\/code>&nbsp;who&nbsp;is paired with&nbsp;<code>v<\/code>&nbsp;but:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>x<\/code>&nbsp;prefers&nbsp;<code>u<\/code>&nbsp;over&nbsp;<code>y<\/code>,&nbsp;and<\/li><li><code>u<\/code>&nbsp;prefers&nbsp;<code>x<\/code>&nbsp;over&nbsp;<code>v<\/code>.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the number of unhappy friends<\/em>.<\/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> n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong>\nFriend 1 is unhappy because:\n- 1 is paired with 0 but prefers 3 over 0, and\n- 3 prefers 1 over 2.\nFriend 3 is unhappy because:\n- 3 is paired with 2 but prefers 1 over 2, and\n- 1 prefers 3 over 0.\nFriends 0 and 2 are happy.\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> n = 2, preferences = [[1], [0]], pairs = [[1, 0]]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> Both friends 0 and 1 are happy.\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> n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]\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>2 &lt;= n &lt;= 500<\/code><\/li><li><code>n<\/code>&nbsp;is even.<\/li><li><code>preferences.length&nbsp;== n<\/code><\/li><li><code>preferences[i].length&nbsp;== n - 1<\/code><\/li><li><code>0 &lt;= preferences[i][j] &lt;= n - 1<\/code><\/li><li><code>preferences[i]<\/code>&nbsp;does not contain&nbsp;<code>i<\/code>.<\/li><li>All values in&nbsp;<code>preferences[i]<\/code>&nbsp;are unique.<\/li><li><code>pairs.length&nbsp;== n\/2<\/code><\/li><li><code>pairs[i].length&nbsp;== 2<\/code><\/li><li><code>x<sub>i<\/sub>&nbsp;!= y<sub>i<\/sub><\/code><\/li><li><code>0 &lt;= x<sub>i<\/sub>, y<sub>i<\/sub>&nbsp;&lt;= n - 1<\/code><\/li><li>Each person is contained in&nbsp;<strong>exactly one<\/strong>&nbsp;pair.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: HashTable<\/strong><\/h2>\n\n\n\n<p>Put the order in a map {x -&gt; {y, order}}, since this is dense, we use can 2D array instead of hasthable which is much faster.<\/p>\n\n\n\n<p>Then for each pair, we just need to check every other pair and compare their orders.<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {\n    vector<int> p(n);\n    for (const auto& pair : pairs) {\n      p[pair[0]] = pair[1];\n      p[pair[1]] = pair[0];\n    }\n    vector<vector<int>> orders(n, vector<int>(n));\n    for (int x = 0; x < n; ++x)\n      for (int i = 0; i < preferences[x].size(); ++i)\n        orders[x][preferences[x][i]] = i;\n    int ans = 0;\n    for (int x = 0; x < n; ++x) {\n      const int y = p[x];      \n      bool found = false;      \n      for (int u = 0; u < n &#038;&#038; !found; ++u) {\n        if (u == x || u == y) continue;\n        const int v = p[u];\n        found |= orders[x][u] < orders[x][y] &#038;&#038; orders[u][x] < orders[u][v]; \n      }\n      if (found) ++ans;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a list of&nbsp;preferences&nbsp;for&nbsp;n&nbsp;friends, where&nbsp;n&nbsp;is always&nbsp;even. For each person&nbsp;i,&nbsp;preferences[i]&nbsp;contains&nbsp;a list of friends&nbsp;sorted&nbsp;in the&nbsp;order of preference. In other words, a friend earlier in the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[650,177],"class_list":["post-7364","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hasthable","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7364","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=7364"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7364\/revisions"}],"predecessor-version":[{"id":7366,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7364\/revisions\/7366"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7364"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7364"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7364"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}