Closest Fair Trade Pair — Problem Statement & Solution Guide

Two PointersMediumTwo Pointers (Dual Arrays)

TimeO(n + m)

SpaceO(1)

Problem Description

You are given two non-decreasing integer arrays, arr1 and arr2, along with an integer limit. Your task is to identify a pair of indices (i, j) such that the sum of the elements arr1[i] + arr2[j] does not exceed limit. Among all valid pairs satisfying this condition, you must select the pair that minimizes the absolute difference |arr1[i] - arr2[j]|. In the event of a tie where multiple pairs yield the same minimum absolute difference, return the pair with the maximum sum arr1[i] + arr2[j]. If no such pair exists, return [-1, -1].

DSA Pattern Breakdown

"Closest Fair Trade Pair"

medium

WHY DOES IT MATTER?

Two‑pointer on sorted data is a cornerstone technique for reducing quadratic search spaces to linear time, essential for interview problems that involve pairwise constraints like sum limits or distance minimization.

OPTIMIZATION CHALLENGE

The key insight is that the sum constraint creates a monotonic boundary: moving one pointer in the direction that reduces the sum never invalidates previously examined pairs, allowing a single linear sweep.

REAL-WORLD CONNECTION

Think of matching buyers and sellers in a marketplace where price offers are sorted; you slide pointers to find the best trade that respects budget caps while minimizing price disparity, mirroring real‑time order‑book matching engines.

During the interview, write the pointer movement logic first on paper, then translate it directly to code; avoid nested loops and remember to update the best pair only when the sum condition holds.

COMPLEXITY AT A GLANCE

⏱ Time:O(n + m)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem leverages the two‑pointer paradigm on two sorted (non‑decreasing) arrays. Because each array is sorted, we can treat the pair (i, j) as a point in a 2‑D grid where moving right increases arr1[i] and moving down increases arr2[j]; this monotonicity lets us prune large swaths of the search space. A naïve double loop checks every O(n·m) combination, which quickly becomes infeasible for n, m up to 10^5. By initializing one pointer at the start of arr1 and the other at the end of arr2, we can adjust them based on the sum constraint: if arr1[i] + arr2[j] > limit we must decrease the sum by moving j left, otherwise we can consider the pair and try to improve the absolute difference by moving i right. This single pass visits each element at most once, yielding O(n+m) time while using O(1) extra space.

Interview Questions on This Problem

Q1How would you modify the algorithm if the arrays were sorted in descending order?

Start i at the end of arr1 and j at the beginning of arr2. If the sum exceeds the limit, move i left (decrease arr1[i]); otherwise, move j right (increase arr2[j]) while tracking the minimal absolute difference.

Q2Can you extend the solution to return all pairs that achieve the minimal |arr1[i]‑arr2[j]| under the limit?

Yes. After finding the optimal difference value, perform a second linear scan with the same two‑pointer logic, collecting every (i, j) whose sum ≤ limit and |arr1[i]‑arr2[j]| equals the recorded minimum.

Q3What is the impact on time complexity if the arrays contain up to 10^6 elements and you need to answer multiple queries with different limits?

Pre‑process each array into a prefix‑max structure or use binary search for each query, turning each query into O(log n + log m). The overall preprocessing is O(n+m), and each query runs in logarithmic time, which scales far better than re‑scanning the arrays for every limit.

Examples

Example 1

Input

arr1 = [1, 5, 10], arr2 = [2, 6, 12], limit = 15

Output

[1,12]

Explanation: Valid pairs (sum <= 15): (1,2) sum=3 diff=1; (1,6) sum=7 diff=5; (5,2) sum=7 diff=3; (5,6) sum=11 diff=1; (10,2) sum=12 diff=8. Minimum diff is 1. Ties at diff=1: (1,2) sum=3 and (5,6) sum=11. Max sum is 11, so return [5, 6].

Example 2

Input

arr1 = [3, 7, 9], arr2 = [1, 4, 8], limit = 10

Output

[9,1]

Explanation: Valid pairs (sum <= 10): (3,1) sum=4 diff=2; (3,4) sum=7 diff=1; (7,1) sum=8 diff=6. Minimum diff is 1. Only one pair has diff=1: (3,4). Return [3, 4].

Example 3

Input

arr1 = [10, 20], arr2 = [1, 2], limit = 5

Output

[]

Explanation: All possible sums: 10+1=11, 10+2=12, 20+1=21, 20+2=22. All exceed limit 5. No valid pair exists. Return [-1, -1].

Constraints

1 <= arr1.length, arr2.length <= 10^5
0 <= arr1[i], arr2[j] <= 10^9
0 <= limit <= 2 * 10^9
arr1 and arr2 are sorted in non-decreasing order

Optimal Approach & Strategy

Use two pointers: i starts at 0 in arr1, j starts at arr2.length‑1. Adjust pointers based on the sum constraint while tracking the minimal |arr1[i]‑arr2[j]|. This runs in linear time.

Brute Force Approach

Iterate over every i in arr1 and every j in arr2, check if arr1[i] + arr2[j] ≤ limit, and keep the pair with the smallest absolute difference. This requires O(n·m) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n + m)

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @param {number} limit
 * @return {number[]}
 */
var closestFairTradePair = function(arr1, arr2, limit) {
    let n = arr1.length;
    let m = arr2.length;
    let i = n - 1;
    let j = 0;
    let bestSum = -1;
    let result = [];
    
    while (i >= 0 && j < m) {
        let sum = arr1[i] + arr2[j];
        if (sum <= limit) {
            if (sum > bestSum) {
                bestSum = sum;
                result = [arr1[i], arr2[j]];
            }
            j++;
        } else {
            i--;
        }
    }
    
    return result;
};

class Solution {
public:
    vector<int> closestFairTradePair(vector<int>& arr1, vector<int>& arr2, int limit) {
        int n = arr1.size();
        int m = arr2.size();
        int i = n - 1;
        int j = 0;
        int bestSum = -1;
        vector<int> result;
        
        while (i >= 0 && j < m) {
            int sum = arr1[i] + arr2[j];
            if (sum <= limit) {
                if (sum > bestSum) {
                    bestSum = sum;
                    result = {arr1[i], arr2[j]};
                }
                j++;
            } else {
                i--;
            }
        }
        
        return result;
    }
};

class Solution {
    public int[] closestFairTradePair(int[] arr1, int[] arr2, int limit) {
        int n = arr1.length;
        int m = arr2.length;
        int i = n - 1;
        int j = 0;
        int bestSum = -1;
        int[] result = new int[2];
        
        while (i >= 0 && j < m) {
            int sum = arr1[i] + arr2[j];
            if (sum <= limit) {
                if (sum > bestSum) {
                    bestSum = sum;
                    result[0] = arr1[i];
                    result[1] = arr2[j];
                }
                j++;
            } else {
                i--;
            }
        }
        
        return result;
    }
}

class Solution:
    def closestFairTradePair(self, arr1: List[int], arr2: List[int], limit: int) -> List[int]:
        n = len(arr1)
        m = len(arr2)
        i = n - 1
        j = 0
        best_sum = -1
        result = []
        
        while i >= 0 and j < m:
            current_sum = arr1[i] + arr2[j]
            if current_sum <= limit:
                if current_sum > best_sum:
                    best_sum = current_sum
                    result = [arr1[i], arr2[j]]
                j += 1
            else:
                i -= 1
        
        return result

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @param {number} limit
 * @return {number[]}
 */
var closestFairTradePair = function(arr1, arr2, limit) {
    let n = arr1.length;
    let m = arr2.length;
    let i = n - 1;
    let j = 0;
    let bestSum = -1;
    let result = [];
    
    while (i >= 0 && j < m) {
        let sum = arr1[i] + arr2[j];
        if (sum <= limit) {
            if (sum > bestSum) {
                bestSum = sum;
                result = [arr1[i], arr2[j]];
            }
            j++;
        } else {
            i--;
        }
    }
    
    return result;
};

Asked in Top Tech Interviews

OracleTCS

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Closest Fair Trade Pair Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Two Pointers

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Closest Fair Trade Pair — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor