Solution 1 - Brute Force

Iterate through every pair of numbers using two nested loops. For each pair, check if they sum to the target. Return the indices when a match is found.

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.1 - Solution 1 - Brute Force Approach """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Brute Force using `enumerate()`

Same brute force logic, but uses Python's enumerate() for cleaner index tracking instead of range(len(...)).

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.1 - Solution 1 - Using Enumerate """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for key1, num1 in enumerate(nums):
            for key2, num2 in enumerate(nums[key1 + 1 :], key1 + 1):
	              # enumerate(iterable, start=1) -> start value determines starting index
                # Printing value and key will output 1 i , 2 j, 3 k, 4 l 
                if num1 + num2 == target:
                    return [key1, key2]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 1 - Linear Scan

Iterate through the array while tracking how many positive integers are missing. For each positive integer starting from 1, check if it exists in the array. If it doesn't, decrement k. When k reaches 0, return the current number.

TimeComplexity: O(n + k)

SpaceComplexity: O(1)

""" 1539.1 - Kth Missing Positive Number - Solution 1 - Linear Scan """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findKthPositive(self, arr: List[int], k: int) -> int:
        """Kth Missing Positive Number Function"""
        i = 0
        current = 0
        while k > 0:
            current += 1
            if i < len(arr) and arr[i] == current:
                i += 1
            else:
                k -= 1
        return current


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findKthPositive([2, 3, 4, 7, 11], 5))  # Expected: 9
    print(Solution().findKthPositive([1, 2, 3, 4], 2))       # Expected: 6
    print(Solution().findKthPositive([5, 6, 7], 3))           # Expected: 3


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Binary Search

Use binary search to find the position where the kth missing number falls. At any index i, the number of missing positives before arr[i] is arr[i] - (i + 1). Binary search for the smallest index where the missing count is >= k, then compute the answer.

TimeComplexity: O(\log n)

SpaceComplexity: O(1)

""" 1539.2 - Kth Missing Positive Number - Solution 2 - Binary Search """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findKthPositive(self, arr: List[int], k: int) -> int:
        """Kth Missing Positive Number Function"""
        left, right = 0, len(arr) - 1

        while left <= right:
            mid = (left + right) // 2
            # Number of missing positives before arr[mid]
            missing = arr[mid] - (mid + 1)
            if missing < k:
                left = mid + 1
            else:
                right = mid - 1

        # At this point, left is the index where the kth missing number falls
        # The answer is left + k
        return left + k


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findKthPositive([2, 3, 4, 7, 11], 5))  # Expected: 9
    print(Solution().findKthPositive([1, 2, 3, 4], 2))       # Expected: 6
    print(Solution().findKthPositive([5, 6, 7], 3))           # Expected: 3


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

1539 - Kth Missing Positive Number

Solution 1 - Brute Force

Solution 2 - Brute Force using enumerate()

Solution 1 - Linear Scan

Solution 2 - Binary Search

Solution 2 - Brute Force using `enumerate()`