Coding Problems (Python)Interview questions and answers

Use a hash map to remember each value's index. For every new value, check if its complement (target - value) was already seen.

def twoSum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        d = target - n
        if d in seen:
            return [seen[d], i]
        seen[n] = i

Time O(n) | Space O(n)

Sort, then for each i, use two pointers to find pairs (l, r) with sum = -nums[i]. Skip duplicates.

def threeSum(nums):
    nums.sort()
    res = []
    n = len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        l, r = i + 1, n - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0: l += 1
            elif s > 0: r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l+1]: l += 1
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
    return res

Time O(n²) | Space O(1) extra

Sort and fix two indices i and j, then two-pointer on the remaining range. Skip duplicates at every level.

def fourSum(nums, target):
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i-1]: continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j-1]: continue
            l, r = j + 1, n - 1
            while l < r:
                s = nums[i] + nums[j] + nums[l] + nums[r]
                if s < target: l += 1
                elif s > target: r -= 1
                else:
                    res.append([nums[i], nums[j], nums[l], nums[r]])
                    while l < r and nums[l] == nums[l+1]: l += 1
                    while l < r and nums[r] == nums[r-1]: r -= 1
                    l += 1; r -= 1
    return res

Time O(n³) | Space O(1) extra

Sorted array means we can use two pointers — move l up when sum is too small, r down when too big.

def twoSum(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            return [l + 1, r + 1]
        if s < target: l += 1
        else: r -= 1

Time O(n) | Space O(1)

If converting to a set drops elements, there were duplicates.

def containsDuplicate(nums):
    return len(set(nums)) != len(nums)

Time O(n) | Space O(n)