Stage I: Hard Questions

Arrays

Pattern: Two-Pointer Technique

These problems use two indices, often moving towards each other or at different speeds, to solve problems efficiently.

Pattern: Prefix/Suffix Calculation

These problems involve creating a result where result[i] depends on calculations over elements before or after it.

Pattern: Array as a Map (Cyclic Sort)

These problems use a clever trick where the array's indices are used to store information about its values.

Pattern: Matrix (2D Array) Traversal

This pattern extends the 1D array concept to two dimensions, requiring careful management of two sets of indices (row and column).

Time Complexity

Square Root Time Complexity: O(√n)

Problem: Analyze the time complexity of the optimized primality test.

Companies: Google, Amazon, Microsoft

def is_prime(n):
    if n <= 1:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

Analysis:

• Time Complexity: O(√n). The loop runs from 2 up to √n. This is a massive improvement over the naive O(n) approach.
• Space Complexity: O(1). It uses a fixed amount of memory.

Quadratic Time Complexity: O(n²)

Problem: Analyze the complexity of a function that checks for duplicates using a nested loop.

Concept Tested: Understanding how nested loops dramatically increase complexity.

LeetCode Link: Contains Duplicate (Note: This is the inefficient, brute-force solution).

Companies: Amazon, Apple, Facebook (Meta), Microsoft, Adobe

def has_duplicate_brute_force(numbers):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] == numbers[j]:
                return True
    return False

Analysis:

• Time Complexity: O(n²). The outer loop runs n times, and the inner loop runs roughly n times for each outer loop iteration.
• Space Complexity: O(1). No new data structure that scales with n is created.

Analyzing a Real Algorithm: Binary Search

Problem: Analyze the time and space complexity of Binary Search on a sorted array.

Concept Tested: Connecting the O(log n) analogy to its most famous implementation.

LeetCode Link: Binary Search

Companies: Amazon, Microsoft, Facebook (Meta), Google, Apple, Adobe

def binary_search(sorted_array, target):
    low = 0
    high = len(sorted_array) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_array[mid] == target:
            return mid
        elif sorted_array[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1 # Not found

Analysis:

• Time Complexity: O(log n). At each step, we discard half of the remaining search space.
• Space Complexity: O(1). This iterative version uses a fixed number of variables.

Recursive Space Complexity

Problem: Analyze the time and space complexity of a recursive function to calculate a sum.

Concept Tested: Understanding that the call stack contributes to space complexity.

def recursive_sum(numbers, index):
    # Base case: we've gone past the end of the array
    if index >= len(numbers):
        return 0
    # Recursive step
    return numbers[index] + recursive_sum(numbers, index + 1)

Analysis:

• Time Complexity: O(n). The function calls itself once for each of the n elements.
• Space Complexity: O(n). Each recursive call adds a new layer ("stack frame") to memory. For an array of size n, there will be n active calls on the stack at the deepest point.

Divide and conquer

🧠 Recursion Fundamentals

🔎 Binary Search and its Variants

🌊 Merge Sort and its Applications

⚡ Quick Sort and its Applications (Partitioning)