Chopsticks

Problem Summary

You have N sticks, where the i-th stick has length L[i]. You want to form pairs of sticks to be used as chopsticks.

Rules:

• A pair is usable if the absolute difference in lengths of the two sticks is at most D.

• Each stick can be used in at most one pair.

Goal: Find the maximum number of valid pairs you can form.

Input:

• First line: two integers N and D.

• Next N lines: one integer per line, L[i] — length of the i-th stick.

Output:

• One integer: maximum number of usable chopstick pairs.

Constraints:

• 1 <= N <= 105

• 0 <= D <= 109

• 1 <= L[i] <= 109

Examples Explanation

Input:

5 2

1

3

3

9

4

Output:

2

Sticks lengths: [1, 3, 3, 9, 4], maximum allowed difference D = 2.

• The stick of length 9 is too far from all others (differences > 2), so it will remain unused.

• Remaining sticks: 1, 3, 3, 4. One possible optimal pairing:

• (1, 3) → difference 2 (valid)

• (3, 4) → difference 1 (valid)
  Total pairs: 2. You cannot form 3 pairs since each pair uses 2 sticks and there are only 4 usable sticks.

Approach

Pattern:

This is a classic greedy + sorting + two-pointer / linear scan problem.

Naive Idea:

Try all possible pairs (i, j) and check if |L[i] - L[j]| <= D, then pick some disjoint subset of these pairs to maximize count.

• Brute force pair checking: O(N2) pairs.

• Then selecting a maximum set of non-overlapping pairs: another non-trivial step.

• With N <= 105 , O(N2) is impossible.

Optimal Greedy Approach

High-level idea:

• Sort the stick lengths.

• Adjacent sticks in the sorted order are the closest in length.

• If two adjacent sticks differ by at most D, we should pair them immediately (greedy choice).

• Once we pair them, we skip past both; otherwise, we move forward.

Why sorting helps:

• After sorting, for any stick at position i, the best candidate to pair it with (to minimize length difference) is one of its neighbors, most naturally i+1.

• If even L[i+1] - L[i] > D, pairing L[i] with any further stick j > i+1 will only increase the difference; hence no valid pair exists for L[i] starting from i+1. It’s safe to move on.

Greedy steps:

1. Sort array L in non-decreasing order.

2. Initialize:

• i = 0 (index in sorted list; 0-based).

• pairs = 0.

3. While i < N - 1:

• If L[i+1] - L[i] <= D:

• Form a pair from L[i] and L[i+1].

• pairs++.

• Move i += 2 (both sticks are used).

• Else:

• L[i] can't pair with L[i+1] or any future stick, so skip it: i += 1.

4. Return pairs.

Key observations:

• We always pair two nearest possible sticks (in length) when they fit the condition. This cannot reduce the maximum possible number of pairs later.

• Each stick participates in at most one pair by construction.

Edge cases:

• N = 1: cannot form any pair → answer 0.

• D = 0: Only sticks of exactly same length can be paired. Greedy still works.

• All sticks too far apart: answer 0.

Pseudo-code:

Complexity Analysis:

Let N be the number of sticks.

• Sorting the array: O(NlogN).

• Single linear scan to form pairs: O(N).

Time Complexity: O(NlogN)

Space Complexity:

• Sorting in-place: O(1) extra (or O(N) depending on language’s sort).

• No additional significant data structures.

Java code

C code

C++ code

Python code

JavaScript code