Solutions for Missing Positive Integer

    • @Geraldpof
    • @Charles, submitted in Python 3, achived 100% score
    def get_positive_subset(array):
        i = 0
        j = len(array) - 1
    
        while i < j:
            if array[i] > 0 and array[j] <= 0:
                array[i], array[j] = array[j], array[i]
                i += 1
                j -= 1
            elif array[i] > 0:
                j -= 1
            else:
                i += 1
    
        # print("i: {}, j: {}".format(i, j))
        # print("partitioned_array:", array)
        pivot = i if array[i] > 0 else i + 1
        return array[pivot:]
    
    
    def solve(array):
        if not array:
            return 1
    
        array = get_positive_subset(array)
        array_len = len(array)
        # print("array: {}".format(array))
    
        if not array:
            return 1
    
        if max(array) == len(array):
            return max(array) + 1
    
        for num in array:
            current_num = abs(num)
            if (current_num - 1) < array_len:
                array[current_num - 1] *= -1
        # print("mutated_array: {}".format(array))
    
        for i, num in enumerate(array):
            if num > 0:
                return i + 1