Moving Stones Until Consecutive II LeetCode solution in Python

1
class Solution:
2
    """
3
    Test cases walk through
4
    Given 7, 4, 9 prove 1, 2                                                            6, 5, 4, 3, 10, prove 2, 3
5

6
    Sort stones -> 4, 7, 9                                                              3, 4, 5, 6, 10
7
    Stone length -> 3                                                                   5
8
    Move penultimate = 7 - 4 - 3 + 2 = 2                                                6-3-5+2 = 0
9
    Move final = 9 - 7 - 3 + 2 = 1                                                      10-4-5+2 = 3
10
    Neither is 0, so we cannot return for sure                                          Move penultimate is 0, so move final is assured
11
                                                                                        This means we can return [min(2, 3), 3] -> [2, 3]
12

13
    Max legal moves is 0                                                                For completeness, max legal moves is 0, max moves is 3
14
    starting index is 0                                                                 starting index is 0
15

16
    Enumeration                                                                         Enumeration
17
        index is 0, stone is 4                                                             index is 0, stone is 3
18
        stones[0] lte 4 - 3 ? No, skip while loop                                          stones[0] lte 3 - 5 ? No, skip while
19
        max legal moves is min of (max of self and 0 - 0 + 1, most moves)                  max legal moves is min of (max of self and 0 - 0 + 1), max moves -> max legal moves is 1
20
             -> max legal moves is 1
21

22
        index is 1, stone is 7                                                             index is 1, stone is 4
23
        stones[0] <= 7 - 3 ? Yes, enter while                                              stones[0] lte 4 - 5 ? No, skip while
24
            starting index is now 1                                                        max legal moves is min of (max of self and 1 - 0 + 1), max moves -> max legal moves is 2
25
        stones[1] <= 7 - 3 ? No, skip while
26
        max legal moves -> min(max of self and 1 - 1 + 1), max_moves
27
            -> max legal moves is 1                                                        index is 2, stone is 5
28
                                                                                           stones[0] lte 5 - 5 ? No skip while
29
        index is 2, stone is 9                                                             max legal moves is min of (max of self and 2 - 0 + 1), max_moves -> max legal moves is 3
30
        stones[1] <= 9 - 3 ? No, skip while
31
        max legal moves is min(max of self and 2-1 + 1), max_moves
32
             -> max legal moves is 2                                                       index is 3, stone is 6
33
    End enumeration                                                                        stones[0] lte 6 - 5 ? No skip while
34
                                                                                           max legal moves is min (max of self and 3 - 0 + 1), max_moves -> max legal moves is 3
35
    Return [3 - 2, 2] -> [1, 2] checks out
36
                                                                                           index is 4, stones is 10
37
                                                                                           stones[0] lte 10 - 5 ? Yes, enter while
38
                                                                                                starting index is 1
39
                                                                                           stones[1] lte 10 - 5 ? Yes, enter while
40
                                                                                                starting index is 2
41
                                                                                           stones[2] lte 10 - 5 ? Yes, enter while
42
                                                                                                starting index is 3
43
                                                                                           max legal moves is min (max of self and 4 - 3 + 1), max moves -> max legal moves is 3
44
                                                                                        End enumeration
45

46
                                                                                        Return [5 - 3, 3] -> [2, 3]
47
    """
48

49
    def numMovesStonesII(self, stones: List[int]) -> List[int]:
50
        # order does not need to be maintained, so sorting is optimal
51
        stones.sort()
52
        # want to work within stone physical space since 10^9 >> 10^4 (stone weight vs length)
53
        stone_length = len(stones)
54
        # what is the cost of moving the second to last stone and the 0th stone?
55
        move_penultimate = stones[-2] - stones[0] - stone_length + 2
56
        # what is the cost of moving the last stone and the 1st stone?
57
        move_final = stones[-1] - stones[1] - stone_length + 2
58
        # in both of these, the cost is the positional exchange in stones along the stone length + 2 for the two stones moving
59
        # our most moves possible are the max of these two
60
        most_moves = max(move_penultimate, move_final)
61
        # since the stones are unique, if either is 0, the one that we have must be max legal moves
62
        # if move penultimate is 0, that means that the second largest stone less the least stone less the length + 2 is 0
63
        # this means that the largest stone, which must be at least one larger than the largest, less the second to least stone which is at least one larger than the least stone  less the length + 2 is move final
64
        # our minimal length is 3
65
        # let a, b, c be stones in order
66
        # b - a - 3 + 2 = 0 -> b = a + 1 move penultimate
67
        # c - b - 3 + 2 = 0 -> b = c - 1 move final
68
        # c - 1 = a + 1 -> c = a + 2
69
        # all stones must be at least 1 to 10^9 and are unique
70
        # so at minimum a is 1, b is 2 and c is 3
71
        # in this case, move final is also 0 so we get 0, 0
72
        # if a = 4, b = 5, c = 7
73
        # 5 - 4 - 3 + 2 = 0 move penultimate is 0
74
        # 7 - 5 - 3 + 2 -> 1 move ultimate is 1
75
        # min legal moves is min of 2 and 1 -> min legal moves is 1 -> 1, 1 is returned
76
        # from this it can be seen that the movement of c relative to b impacts  the return here when one is 0, and that if either is 0 it does not preclude the other. However it does entail a relation to 2 as most that min could become
77
        # this is because if most moves is greater than 2, we could always do the move alternate that was 0 in two steps. This is what locks in to place the ability to use 2 here as the min argument.
78
        if move_penultimate == 0 or move_final == 0:
79
            min_legal_moves = min(2, most_moves)
80
            return [min_legal_moves, most_moves]
81
        # how many legal moves are there in sorted order?
82
        max_legal_moves = 0
83
        # starting from 0th index
84
        starting_index = 0
85
        # enumerate each stone and index
86
        for index, stone in enumerate(stones):
87
            # while the stone at starting index is lte this stone minus stone length (cost of a move)
88
            while stones[starting_index] <= stone - stone_length:
89
                # increment
90
                starting_index += 1
91
            # max legal moves is then set to maxima of self and indexed difference with 1 for 0 based indexing
92
            max_legal_moves = min(
93
                max(max_legal_moves, index - starting_index + 1), most_moves
94
            )
95
        # return length - max legal moves when in sorted order (your minimal move state) and most moves in sorted order
96
        return [stone_length - max_legal_moves, most_moves]