How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at MathWorks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at MathWorks during technical interviews.

Maximize operations by removing target-sum pairs

Company: MathWorks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Given an integer array nums and an integer T, in one operation you may remove two elements whose sum equals T. Return the maximum number of operations you can perform. Provide an algorithm with O(n) expected time using a hash map or O(n log n) time using sorting and two pointers, prove correctness, and discuss edge cases (duplicates, negatives, large values).

Quick Answer: This question evaluates a candidate's ability to design and analyze efficient array algorithms and use appropriate data structures and techniques such as hash maps or sorting with two-pointer strategies, with attention to time and space complexity.

Given an integer array `nums` and an integer `T`, in one operation you may remove two elements whose sum equals `T`. Each element can be used in at most one operation. Return the maximum number of operations you can perform. The greedy claim is that pairing is unconstrained: any element equal to `x` can pair with any element equal to `T - x`, so for `x != T - x` the number of pairs is `min(count[x], count[T-x])`, and for `x == T - x` (i.e. `2x == T`) it is `count[x] // 2`. Aim for O(n) expected time with a hash map (or O(n log n) with sort + two pointers). Edge cases to consider: duplicates, negative values, large values, an empty array, and when `T` is even so `x` pairs with itself.

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9
-2*10^9 <= T <= 2*10^9
Each element may be used in at most one operation

Examples

Input: ([1, 2, 3, 4], 5)

Expected Output: 2

Explanation: Pair (1,4) and (2,3), both sum to 5 — 2 operations.

Input: ([3, 1, 3, 4, 3], 6)

Expected Output: 1

Explanation: Three 3's pair with each other: 3+3=6 gives floor(3/2)=1 op. The leftover 3, 1, and 4 cannot form another sum of 6.

Input: ([2, 2, 2, 2], 4)

Expected Output: 2

Explanation: x == T - x == 2, so floor(4/2) = 2 self-pairs.

Input: ([1, 1, 1], 2)

Expected Output: 1

Explanation: Three 1's, self-pairing with T=2: floor(3/2) = 1 op, one 1 left over.

Input: ([], 5)

Expected Output: 0

Explanation: Empty array — no operations possible.

Input: ([5], 5)

Expected Output: 0

Explanation: Single element cannot form a pair.

Input: ([-3, 3, -3, 3, 0], 0)

Expected Output: 2

Explanation: (-3) pairs with 3: min(2,2)=2 ops. The single 0 has no partner (only one 0).

Input: ([1, 2, 3], 100)

Expected Output: 0

Explanation: No two elements sum to 100.

Input: ([0, 0, 0, 0, 0], 0)

Expected Output: 2

Explanation: Self-pairing zeros with T=0: floor(5/2) = 2 ops.

Input: ([-1, -2, -3, -4, 5, 6], -3)

Expected Output: 1

Explanation: Only (-1)+(-2) = -3 forms a valid pair; no other pair sums to -3.

Hints

Reorder the array freely — only the multiset of values matters, not their positions, because any two elements summing to T may be paired.
Count the frequency of each value. For a value x, its partner is T - x.
If x != T - x, the pairs you can form are limited by the scarcer of the two counts: min(count[x], count[T-x]). Visit each unordered pair {x, T-x} once (e.g. only when x < T-x) to avoid double counting.
If x == T - x (this happens exactly when 2x == T), you pair the value with itself, giving count[x] // 2 pairs.
Watch the self-pairing case: zeros with T = 0, or any value v with T = 2v.

Quick Overview

This question evaluates a candidate's ability to design and analyze efficient array algorithms and use appropriate data structures and techniques such as hash maps or sorting with two-pointer strategies, with attention to time and space complexity.