[Java/C++/Python] Sliding Window
Lower Bound\nAs I mentioned in my video last week,\nin case of n stones, \nwe need to find a consecutive n positions and move the stones in.\n\nThis idea led th
## Lower Bound\nAs I mentioned in my video last week,\nin case of `n` stones, \nwe need to find a consecutive `n` positions and move the stones in.\n\nThis idea led the solution with sliding windows.\n\nSlide a window of size `N`, and find how many stones are already in this window.\nWe want moves other stones into this window.\nFor each missing stone, we need at least one move.\n\nGenerally, the number of missing stones and the moves we need are the same.\nOnly one corner case in this problem, we need to move the endpoint to no endpoint.\n\n\nFor case `1,2,4,5,10`,\n1 move  needed from `10` to `3`.\n\nFor case `1,2,3,4,10`,\n2 move needed from `1` to `6`, then from `10` to `5`.\n<br>\n\n## Upper Bound\nWe try to move all stones to leftmost or rightmost.\nFor example of to rightmost.\nWe move the `A[0]` to `A[1] + 1`.\nThen each time, we pick the stone of left endpoint, move it to the next empty position.\nDuring this process, the position of leftmost stones increment 1 by 1 each time.\nUntil the leftmost is at `A[n - 1] - n + 1`.\n<br>\n\n## Complexity\nTime of quick sorting `O(NlogN)`\nTime of sliding window `O(N)`\nSpace `O(1)`\n<br>\n\n**Java:**\n```\n    public int[] numMovesStonesII(int[] A) {\n        Arrays.sort(A);\n        int i = 0, n = A.length, low = n;\n        int high = Math.max(A[n - 1] - n + 2 - A[1], A[n - 2] - A[0] - n + 2);\n        for (int j = 0; j < n; ++j) {\n            while (A[j] - A[i] >= n) ++i;\n            if (j - i + 1 == n - 1 && A[j] - A[i] == n - 2)\n                low = Math.min(low, 2);\n            else\n                low = Math.min(low, n - (j - i + 1));\n        }\n        return new int[] {low, high};\n    }\n```\n\n**C++:**\n```\n    vector<int> numMovesStonesII(vector<int>& A) {\n        sort(A.begin(), A.end());\n        int i = 0, n = A.size(), low = n;\n        int high = max(A[n - 1] - n + 2 - A[1], A[n - 2] - A[0] - n + 2);\n        for (int j = 0; j < n; ++j) {\n            while (A[j] - A[i] >= n) ++i;\n            if (j - i + 1 == n - 1 && A[j] - A[i] == n - 2)\n                low = min(low, 2);\n            else\n                low = min(low, n - (j - i + 1));\n        }\n        return {low, high};\n    }\n```\n\n**Python:**\n```\n    def numMovesStonesII(self, A):\n        A.sort()\n        i, n, low = 0, len(A), len(A)\n        high = max(A[-1] - n + 2 - A[1], A[-2] - A[0] - n + 2)\n        for j in range(n):\n            while A[j] - A[i] >= n: i += 1\n            if j - i + 1 == n - 1 and A[j] - A[i] == n - 2:\n                low = min(low, 2)\n            else:\n                low = min(low, n - (j - i + 1))\n        return [low, high]\n```\n
[]