{"id":7191,"date":"2020-08-01T22:03:27","date_gmt":"2020-08-02T05:03:27","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7191"},"modified":"2020-08-01T22:04:22","modified_gmt":"2020-08-02T05:04:22","slug":"leetcode-1535-find-the-winner-of-an-array-game","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1535-find-the-winner-of-an-array-game\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1535. Find the Winner of an Array Game"},"content":{"rendered":"\n

Given an integer array arr<\/code> of distinct<\/strong> integers and an integer k<\/code>.<\/p>\n\n\n\n

A game will be played between the first two elements of the array (i.e. arr[0]<\/code> and arr[1]<\/code>). In each round of the game, we compare arr[0]<\/code> with arr[1]<\/code>, the larger integer wins and remains at position 0<\/code> and the smaller integer moves to the end of the array. The game ends when an integer wins k<\/code> consecutive rounds.<\/p>\n\n\n\n

Return the integer which will win the game<\/em>.<\/p>\n\n\n\n

It is guaranteed<\/strong> that there will be a winner of the game.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> arr = [2,1,3,5,4,6,7], k = 2\nOutput:<\/strong> 5\nExplanation:<\/strong> Let's see the rounds of the game:\nRound |       arr       | winner | win_count\n  1   | [2,1,3,5,4,6,7] | 2      | 1\n  2   | [2,3,5,4,6,7,1] | 3      | 1\n  3   | [3,5,4,6,7,1,2] | 5      | 1\n  4   | [5,4,6,7,1,2,3] | 5      | 2\nSo we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [3,2,1], k = 10\nOutput:<\/strong> 3\nExplanation:<\/strong> 3 will win the first 10 rounds consecutively.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [1,9,8,2,3,7,6,4,5], k = 7\nOutput:<\/strong> 9\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000\nOutput:<\/strong> 99\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 2 <= arr.length <= 10^5<\/code><\/li>
  • 1 <= arr[i] <= 10^6<\/code><\/li>
  • arr<\/code> contains distinct<\/strong> integers.<\/li>
  • 1 <= k <= 10^9<\/code><\/li><\/ul>\n\n\n\n
    Solution 1: Simulation with a List<\/strong><\/h2>\n\n\n\n
    Observation : if k >= n – 1, ans = max(arr) <\/p>\n\n\n\n
    Time complexity: O(n+k)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  int getWinner(vector& arr, int k) {\n    if (k >= arr.size()) return *max_element(begin(arr), end(arr));\n    int win = 0;    \n    list a(begin(arr), end(arr));\n    while (true) {\n      auto it0 = begin(a);\n      auto it1 = next(it0);\n      if (*it0 > *it1) {\n        a.splice(a.end(), a, it1);\n        ++win;\n      } else {\n        swap(it0, it1);\n        a.splice(a.end(), a, it1);\n        win = 1;\n      }\n      if (win == k) return *it0;\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: One pass<\/strong><\/h2>\n\n\n\n
    Since smaller numbers will be put to the end of the array, we must compare the rest of array before meeting those used numbers again. And the winner is monotonically increasing. So we can do it in one pass, just keep the largest number seen so far. If we reach to the end of the array, arr[0] will be max(arr) and it will always win no matter what k is.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  int getWinner(vector& arr, int k) {\n    int winner = arr[0];\n    int win = 0;\n    for (int i = 1; i < arr.size(); ++i) {\n      if (arr[i] > winner) {\n        winner = arr[i];\n        win = 0;\n      }\n      if (++win == k) break;\n    }\n    return winner;\n  }\n};\n<\/pre>\n\n<\/div>
    Java<\/h2>\n
    \n\n
    \nclass Solution {\n  public int getWinner(int[] arr, int k) {\n    int winner = arr[0];\n    int win = 0;\n    for (int i = 1; i < arr.length && win < k; ++i, ++win)\n      if (arr[i] > winner) {\n        winner = arr[i];\n        win = 0;\n      }\n    return winner;\n  }\n}\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \nclass Solution:\n  def getWinner(self, arr: List[int], k: int) -> int:\n    winner = arr[0]\n    win = 0\n    for x in arr[1:]:\n      if x > winner:\n        winner, win = x, 0\n      win += 1\n      if win == k: break\n    return winner\n<\/pre>\n<\/div><\/div>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    Given an integer array arr of distinct integers and an integer k. A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of…<\/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,179],"class_list":["post-7191","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-medium","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7191","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=7191"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7191\/revisions"}],"predecessor-version":[{"id":7193,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7191\/revisions\/7193"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7191"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7191"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7191"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}