What is max move and what is min?
The question huanted me for a while is that what does it mean by max and min move?\nTake max first - how to make sure we move as many times as possible?\nThe an
The question huanted me for a while is that what does it mean by max and min move?\nTake max first - how to make sure we move as many times as possible?\nThe answer is to visit as many gaps as we can. Assume we have [7,4,9], after sort, it is [4,7,9], the number of visitable gaps between each pair of positions are 2 and 1, or specifically, position 5,6 and 8. So the max move means that we try to visit the gaps as many as possible. \nOne way is to move rightbound, we could move leftmost stone to 8 to have [7,8,9], then we are done with the count of move equals 1. \nThen we could try move leftbound - move 9 to 6 to have [4,6,7] and move 7 to 5 to have [4,5,6], so we have moved twice and the max_move = max(1,2) = 2.\nAnother example - [1,3,7,10], the gaps are 2,4,5,6,8,9, if we move rightbound, we could visit 4,5,6,8,9, while leftbound we could visit 2,4,5,6, so max_move = max(5,4) = 5.\nOk ... then what does it mean by min move? \nThe answer is try to keep as many stones as where they are, and move in every other outside stone.\nTo achieve this, we could setup a window of size >= N (N is the number of all stones), then we slide the windows from left to right, during which for each occurrance of such an window we count how many stones need to move in, the min of all those counts is the min_move.\n\n```\nvector<int> numMovesStonesII(vector<int>& stones) {\n        sort(stones.begin(), stones.end());\n        int min_move = (int)1e9;\n        int max_move = 0;\n        int gap_sum = 0;\n        int size = stones.size();\n        for (int i = 1; i < size; ++i) {\n            gap_sum += stones[i] - stones[i-1] - 1; // sum of all gaps\n        }\n\t\t// max_move = max(rightbound moves, leftbound moves)\n        max_move = max(gap_sum - stones[1] + stones[0] + 1, gap_sum - stones[size-1] + stones[size-2] + 1);\n        int st = 0;\n        int ed = 1; //[st, ed] is the sliding window\n        while (ed < size) {\n            int space = stones[ed] - stones[st] + 1;\n            if (space < size) ed += 1; // window too small, need to expand\n            else if (space == size) { // window size is N, borders are all in right place, only need to move in all outside stones.\n                min_move = min(min_move, st + size - ed - 1);\n                st += 1;\n            } else { // window size bigger than N, need to move one of the border inside the window in the end.\n                int not_included = st + size - ed - 1;\n\t\t\t\t// mind the case that there is no outside stone, moving is impossible, so skip.\n                if (not_included > 0) min_move = min(min_move, st + size - ed);\n                st += 1;\n            }\n        }\n        \n        return {min_move, max_move};\n    }\n```
[]