Count Index Pairs with a Sum Below the Target
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
# Count Index Pairs with a Sum Below the Target
You are given a 0-indexed integer array `nums` of length `n` and an integer `target`.
Return the number of index pairs `(i,j)` satisfying both `0 <= i < j < n` and `nums[i] + nums[j] < target`. The inequality is strict: a sum equal to the target does not qualify.
### Examples
**Example 1**
```text
Input: nums = [-3,2,2,4], target = 1
Output: 2
```
The pairs `(0,1)` and `(0,2)` each have sum `-1`, which is below `1`. Pair `(0,3)` has sum exactly `1` and is excluded; all remaining pairs have larger sums.
**Example 2**
```text
Input: nums = [0,0,0], target = 1
Output: 3
```
The index pairs `(0,1)`, `(0,2)`, and `(1,2)` all have sum zero. They are three different pairs even though their values are identical.
### Constraints
- `1 <= nums.length == n <= 50`.
- `-50 <= nums[i], target <= 50`.
### Clarifying Questions
- Does a sum equal to `target` count? No; it must be strictly smaller.
- Are pairs distinguished by indices or by values? By indices; equal values at different positions can participate in different pairs.
- Can an element pair with itself? No; `i < j` excludes that case.
- Are `(i,j)` and `(j,i)` both counted? No; only the order with `i < j` is eligible.
### C++ Interface
```cpp
class Solution {
public:
int countPairs(vector<int>& nums, int target) {
}
};
```
### Reasoning Checkpoints
- Preserve the strict comparison and the two-distinct-indices requirement.
- Account for repeated and negative values without merging index pairs.
- Use the given size bound when choosing how to inspect candidate pairs.
```hint Pair enumeration
How can you organize the two indices so that every eligible pair is inspected once and no element is paired with itself?
```
Overview: Count distinct index pairs whose sum is strictly below a target, retaining duplicate values as separate array positions.
