Problem Description

The "Apples & Oranges" problem is a classic array manipulation challenge. Given two integer arrays, apples and oranges, and an integer target, your task is to determine whether there exists a pair of elements—one from apples and one from oranges—whose sum equals target.

• Each element in apples and oranges can be used only once in forming the pair.
• The solution should return true if such a pair exists, and false otherwise.
• There is no guarantee that the arrays are sorted or of the same length.
• Key constraints: Do not reuse elements, and you must find exactly one element from each array to form the sum.

Thought Process

At first glance, the most straightforward approach is to check every possible pair of elements from apples and oranges to see if their sum matches target. This brute-force method is easy to implement but can be slow for large arrays because it checks all combinations.

To optimize, we can look for ways to reduce the number of checks. One idea is to use a hash set to store values for fast lookup. By storing the required complement (the value that would sum with a given apple to reach the target) of each apple, we can quickly check if any orange matches that complement.

This shift from brute-force to using a hash set for lookups changes our approach from checking every pair to checking each orange against a set of possible values, greatly improving efficiency.

Solution Approach

Let's break down the optimized solution step-by-step:

1. Build a set of complements:
   • For each number a in apples, calculate target - a and store it in a hash set called needed.
   • This set represents all the values that, if found in oranges, would form a pair summing to target.
2. Check oranges for matches:
   • Iterate through each number o in oranges.
   • If o is found in the needed set, return true immediately, as a valid pair exists.
3. Return result:
   • If no such pair is found after checking all oranges, return false.

Why use a hash set? Because checking if a value exists in a set is typically O(1) time, making our solution much faster than checking every possible pair.

Example Walkthrough

Let's walk through an example:

• apples = [2, 4, 6]
• oranges = [5, 1, 3]
• target = 7

Step 1: Build the set of needed complements:

• For 2: 7 - 2 = 5
• For 4: 7 - 4 = 3
• For 6: 7 - 6 = 1

Step 2: Check each orange:

• 5 is in needed → return true

Time and Space Complexity

Brute-force approach:

• Time complexity: O(N * M), where N and M are the lengths of apples and oranges.
• Space complexity: O(1), since no extra data structures are used.

• Time complexity: O(N + M), since we loop through both arrays once each.
• Space complexity: O(N), for storing the complements from apples in the set.

The optimized approach is much faster for large arrays because it avoids the nested loops of the brute-force method.

Summary

In summary, the "Apples & Oranges" problem is about efficiently finding a pair of numbers from two different arrays that sum to a target. The key insight is to use a hash set to store needed complements, allowing for quick lookups and reducing the time complexity from O(N * M) to O(N + M). This approach is both simple and highly effective, making it a great example of using data structures to optimize search problems.

Code Implementation

def apples_and_oranges(apples, oranges, target):
    needed = set(target - a for a in apples)
    for o in oranges:
        if o in needed:
            return True
    return False
    

#include <vector>
#include <unordered_set>

bool applesAndOranges(const std::vector<int>& apples, const std::vector<int>& oranges, int target) {
    std::unordered_set<int> needed;
    for (int a : apples) {
        needed.insert(target - a);
    }
    for (int o : oranges) {
        if (needed.count(o)) {
            return true;
        }
    }
    return false;
}
    

import java.util.HashSet;

public class ApplesAndOranges {
    public boolean applesAndOranges(int[] apples, int[] oranges, int target) {
        HashSet<Integer> needed = new HashSet<>();
        for (int a : apples) {
            needed.add(target - a);
        }
        for (int o : oranges) {
            if (needed.contains(o)) {
                return true;
            }
        }
        return false;
    }
}
    

function applesAndOranges(apples, oranges, target) {
    const needed = new Set(apples.map(a => target - a));
    for (let o of oranges) {
        if (needed.has(o)) {
            return true;
        }
    }
    return false;
}