Ph.D. Qual Study Assistant

Sum of Two Arrays Problem

1. The Problem

Given two arrays of integers, `A[1..n]` and `B[1..n]`, and a target number `X`, we need to determine if there exists a pair of elements, `A[i]` and `B[j]`, such that `A[i] + B[j] = X`. The algorithm must run in `O(n log n)` time.

2. The Idea: Sort and Search

A brute-force approach of checking every pair `(A[i], B[j])` would take O(n²) time, which is too slow. The `O(n log n)` requirement strongly suggests that a sorting-based approach is needed.

The core idea is to transform the problem. Instead of looking for two numbers, we can look for one. If we rearrange the equation `A[i] + B[j] = X`, we get `B[j] = X - A[i]`.

This means for each element `A[i]` in the first array, we can calculate the `complement` value it needs from the second array. If we can search for this complement in `B` very quickly, we can improve the overall runtime. By sorting array `B` first, we can use binary search to find the complement in `O(log n)` time.

3. The Algorithm

  1. Sort one of the arrays, for instance, `B`. This takes `O(n log n)` time.
  2. Iterate through each element `A[i]` in the unsorted array `A`. This is a loop that runs `n` times.
  3. For each `A[i]`, calculate the required complement: `complement = X - A[i]`.
  4. Perform a binary search for `complement` in the sorted array `B`. This search takes `O(log n)` time.
  5. If the binary search finds `complement` in `B`, then we have found a valid pair. The algorithm can terminate and return `true`.
  6. If the loop completes without finding any such pair, it means no solution exists. Return `false`.

4. Complexity Analysis

Time Complexity: O(n log n)
The algorithm has two main parts: sorting `B` (`O(n log n)`) and iterating through `A` while performing binary searches (`n` iterations * `O(log n)` per search = `O(n log n)`). The total time is `O(n log n) + O(n log n)`, which simplifies to `O(n log n)`.
Space Complexity: O(1) or O(n)
If the sorting algorithm used is in-place (like Heapsort), the space complexity is O(1). If it requires extra space (like Mergesort), it would be O(n).

Algorithm Visualization