Maximize profitable pairs

You are given an array profits of n integers representing net profit per item and an integer threshold T. You may form disjoint pairs (i, j). What is the maximum number of pairs such that profits[i] + profits[j] >= T? Describe an O(n log n) algorithm using sorting and a left/right pointer strategy, prove correctness, analyze complexity, and discuss edge cases (odd n, negative values, very large or very small T). Provide pseudocode.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Maximize Profitable Pairs

You are given an array profits of n integers representing the net profit per item, and an integer threshold T. You may form disjoint pairs (i, j) (each index used in at most one pair). Return the maximum number of pairs you can form such that profits[i] + profits[j] >= T.

Use an O(n log n) approach: sort the array, then use a left/right two-pointer scan. If the smallest and largest available values already sum to at least T, pair them and move both pointers inward; otherwise the smallest value cannot reach T even with the largest partner, so discard it (advance the left pointer).

Example 1:

Input: profits = [1, 2, 3, 4, 5], T = 6
Output: 2

Explanation: Pair (5,1) -> sum 6, and pair (4,2) -> sum 6. The 3 is left unpaired. 2 pairs.

Example 2:

Input: profits = [1, 1, 1, 1], T = 10
Output: 0

Explanation: No two values sum to at least 10.

Example 3:

Input: profits = [10, -10, 3, 3], T = 0
Output: 2

Explanation: Pair (10,-10) -> 0, pair (3,3) -> 6. 2 pairs.

Constraints

• 0 <= n <= 10^5
• -10^9 <= profits[i] <= 10^9
• -10^9 <= T <= 10^9
• Each index may be used in at most one pair (pairs are disjoint).

Hints

1. Sort the array first. After sorting, the optimal strategy can be decided greedily from the two ends.
2. Use two pointers: left at the smallest value, right at the largest. If their sum >= T, this is a valid pair — count it and move both inward.
3. If profits[left] + profits[right] < T, then profits[left] cannot meet the threshold with ANY available partner (right is the largest left). Discard left (advance it) and try again.
4. Greedy exchange argument: pairing the current smallest unpairable-or-pairable value with the largest never loses an achievable pairing, so this maximizes the count.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

You are given an array profits of n integers representing net profit per item and an integer threshold T. You may form disjoint pairs (i, j). What is the maximum number of pairs such that profits[i] + profits[j] >= T? Describe an O(n log n) algorithm using sorting and a left/right pointer strategy, prove correctness, analyze complexity, and discuss edge cases (odd n, negative values, very large or very small T). Provide pseudocode.

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.