Intermediate

Mock Exam 2: Arrays & Strings

A step up from the warm-up. One Easy problem to build momentum, then two Medium problems that test sliding window and prefix/suffix patterns. Target time: 60 minutes total.

Problem 1: Contains Duplicate (Easy)

Given an integer array nums, return True if any value appears at least twice in the array, and False if every element is distinct.

Examples

Input: nums = [1, 2, 3, 1]
Output: True

Input: nums = [1, 2, 3, 4]
Output: False

Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output: True

Constraints

• 1 ≤ nums.length ≤ 10⁵
• -10⁹ ≤ nums[i] ≤ 10⁹

Solution: Brute Force

def contains_duplicate_brute(nums):
    """Brute force: check every pair.

    Time: O(n^2) - nested loops
    Space: O(1)
    """
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Solution: Optimal (Hash Set)

def contains_duplicate(nums):
    """Optimal: hash set for O(1) lookup.

    Time: O(n) - single pass
    Space: O(n) - set stores up to n elements

    Add each number to a set. If we try to add
    a number already in the set, we found a duplicate.
    """
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

# One-liner alternative:
def contains_duplicate_short(nums):
    return len(nums) != len(set(nums))

# Test
print(contains_duplicate([1, 2, 3, 1]))  # True
print(contains_duplicate([1, 2, 3, 4]))  # False

Problem 2: Longest Substring Without Repeating Characters (Medium)

Given a string s, find the length of the longest substring without repeating characters.

Examples

Input: s = "abcabcbb"
Output: 3
Explanation: "abc" is the longest, length = 3

Input: s = "bbbbb"
Output: 1
Explanation: "b" is the longest, length = 1

Input: s = "pwwkew"
Output: 3
Explanation: "wke" is the longest, length = 3

Constraints

• 0 ≤ s.length ≤ 5 × 10⁴
• s consists of English letters, digits, symbols, and spaces

Solution: Brute Force

def length_of_longest_brute(s):
    """Brute force: check all substrings.

    Time: O(n^3) - O(n^2) substrings, O(n) uniqueness check
    Space: O(n) - set for each substring

    Generate every substring and check if all
    characters are unique. Track the maximum length.
    """
    max_len = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            substring = s[i:j]
            if len(substring) == len(set(substring)):
                max_len = max(max_len, len(substring))
    return max_len

Solution: Optimal (Sliding Window)

def length_of_longest_substring(s):
    """Optimal: sliding window with hash set.

    Time: O(n) - each character visited at most twice
    Space: O(min(n, m)) where m = charset size

    Expand right pointer to grow the window. When a
    duplicate is found, shrink from the left until
    the duplicate is removed. Track max window size.
    """
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        # Shrink window until no duplicate
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

# Even faster: use hash map to jump left pointer
def length_of_longest_optimized(s):
    """Optimized sliding window with hash map.

    Time: O(n) - single pass, left pointer only moves forward
    Space: O(min(n, m))

    Store last seen index of each character.
    Jump left pointer directly past the duplicate.
    """
    last_seen = {}
    left = 0
    max_len = 0

    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1
        last_seen[char] = right
        max_len = max(max_len, right - left + 1)

    return max_len

# Test
print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("bbbbb"))      # 1
print(length_of_longest_substring("pwwkew"))     # 3

Problem 3: Product of Array Except Self (Medium)

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. You must solve it in O(n) time and without using division.

Examples

Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]

Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]

Constraints

• 2 ≤ nums.length ≤ 10⁵
• -30 ≤ nums[i] ≤ 30
• The product of any prefix or suffix fits in a 32-bit integer
• You must not use division

Solution: Brute Force

def product_except_self_brute(nums):
    """Brute force: compute each product separately.

    Time: O(n^2) - for each element, multiply all others
    Space: O(1) - excluding output array

    For each index, iterate through all other indices
    and multiply. Simple but too slow.
    """
    n = len(nums)
    result = []
    for i in range(n):
        product = 1
        for j in range(n):
            if i != j:
                product *= nums[j]
        result.append(product)
    return result

Solution: Optimal (Prefix/Suffix)

def product_except_self(nums):
    """Optimal: prefix and suffix products.

    Time: O(n) - two passes through the array
    Space: O(1) - output array not counted as extra space

    Key insight: product_except_self[i] =
        (product of all elements to the left of i) *
        (product of all elements to the right of i)

    Pass 1 (left to right): compute prefix products
    Pass 2 (right to left): multiply by suffix products
    """
    n = len(nums)
    result = [1] * n

    # Pass 1: prefix products
    # result[i] = product of nums[0..i-1]
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # Pass 2: suffix products
    # multiply result[i] by product of nums[i+1..n-1]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

# Trace for [1, 2, 3, 4]:
# After prefix pass: [1, 1, 2, 6]
#   result[0] = 1 (nothing to left)
#   result[1] = 1 (product of [1])
#   result[2] = 2 (product of [1,2])
#   result[3] = 6 (product of [1,2,3])
# After suffix pass: [24, 12, 8, 6]
#   result[3] *= 1 = 6  (nothing to right)
#   result[2] *= 4 = 8  (product of [4])
#   result[1] *= 12 = 12 (product of [3,4])
#   result[0] *= 24 = 24 (product of [2,3,4])

# Test
print(product_except_self([1, 2, 3, 4]))       # [24, 12, 8, 6]
print(product_except_self([-1, 1, 0, -3, 3]))  # [0, 0, 9, 0, 0]

Score Your Performance

Result	Score	Next Step
All 3 solved optimally in < 60 min	⭐ Excellent	Move to Mock Exam 3
All 3 solved (any approach) in < 60 min	👍 Good	Review sliding window pattern, then Mock Exam 3
2 solved in 60 min	🔄 Developing	Practice more sliding window problems
1 or 0 solved	📚 Study More	Study sliding window and prefix patterns, retry in 2 days