Problem Description

You are given two integer arrays nums1 and nums2, both of length n. Your task is to count the number of pairs of indices (i, j) that satisfy the following conditions:

1. i < j (the first index must be strictly less than the second index)
2. nums1[i] + nums1[j] > nums2[i] + nums2[j] (the sum of elements from nums1 at positions i and j must be greater than the sum of elements from nums2 at the same positions)

The key insight is that we need to find pairs where the sum from the first array exceeds the sum from the second array at the same index positions.

For example, if we have:

• nums1 = [2, 1, 2, 1]
• nums2 = [1, 2, 1, 2]

We would check all pairs (i, j) where i < j:

• For pair (0, 1): Check if 2 + 1 > 1 + 2 (which is 3 > 3, false)
• For pair (0, 2): Check if 2 + 2 > 1 + 1 (which is 4 > 2, true)
• And so on...

The solution transforms this problem by rearranging the inequality to (nums1[i] - nums2[i]) + (nums1[j] - nums2[j]) > 0. This allows us to create a new array where each element is the difference between corresponding elements of nums1 and nums2, then find pairs in this new array whose sum is positive. The sorting and two-pointer technique efficiently counts all valid pairs without checking every possible combination.

Intuition

The original condition nums1[i] + nums1[j] > nums2[i] + nums2[j] involves comparing sums from two different arrays, which makes it complex to work with directly. Let's rearrange this inequality to see if we can simplify it.

By moving terms around, we get: nums1[i] + nums1[j] > nums2[i] + nums2[j] → nums1[i] - nums2[i] + nums1[j] - nums2[j] > 0

This rearrangement reveals something important: we can think of this as the sum of two differences being positive. If we define a new array nums where nums[k] = nums1[k] - nums2[k], then our condition becomes simply nums[i] + nums[j] > 0.

Now we've transformed the problem into finding pairs in a single array whose sum is positive. This is a classic two-sum variant problem.

Why does sorting help? Once we sort the array, we can use the two-pointer technique efficiently. Consider the sorted array with pointers at both ends:

• If the smallest element (left) plus the largest element (right) is positive, then the smallest element paired with ANY element from its right up to the largest will also give a positive sum
• If their sum is not positive, we know the smallest element cannot form a valid pair with the current right element (or any smaller element to its left), so we need to move to a larger left element

This way, instead of checking all O(n²) pairs, we can count valid pairs in O(n log n) time (sorting) plus O(n) time (two-pointer traversal). The key insight is recognizing that the problem can be transformed into a simpler form where established algorithms apply directly.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The implementation follows these key steps:

Step 1: Transform the Array

nums = [a - b for a, b in zip(nums1, nums2)]

We create a new array nums where each element is the difference between corresponding elements of nums1 and nums2. This transforms our problem from finding pairs where nums1[i] + nums1[j] > nums2[i] + nums2[j] to finding pairs where nums[i] + nums[j] > 0.

Step 2: Sort the Array

nums.sort()

Sorting enables us to use the two-pointer technique efficiently. After sorting, smaller values are on the left and larger values are on the right.

Step 3: Initialize Two Pointers

l, r = 0, len(nums) - 1
ans = 0

We set up two pointers: l starting at the beginning (smallest element) and r at the end (largest element). The variable ans keeps track of our count.

Step 4: Two-Pointer Traversal

while l < r:
    while l < r and nums[l] + nums[r] <= 0:
        l += 1
    ans += r - l
    r -= 1

The outer loop continues while l < r. For each position of the right pointer r:

• Inner while loop: We move the left pointer l to the right as long as nums[l] + nums[r] <= 0. This finds the first position where nums[l] + nums[r] > 0.

• Count valid pairs: Once we find a valid l, all indices from l to r-1 paired with index r form valid pairs. That's r - l pairs total. We add this count to our answer.

• Move right pointer: We then decrement r to check pairs with the next largest element.

Why this works:

• If nums[l] + nums[r] > 0, then nums[k] + nums[r] > 0 for all l ≤ k < r (since the array is sorted and nums[k] ≥ nums[l])
• By fixing r and finding the smallest valid l, we can count all valid pairs with right endpoint r in constant time
• Moving r leftward ensures we count each pair exactly once

Time Complexity: O(n log n) for sorting + O(n) for the two-pointer traversal = O(n log n)

Space Complexity: O(n) for the transformed array nums

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• nums1 = [3, 1, 4, 2]
• nums2 = [2, 3, 1, 1]

Step 1: Transform the Array

Create the difference array:

• nums[0] = 3 - 2 = 1
• nums[1] = 1 - 3 = -2
• nums[2] = 4 - 1 = 3
• nums[3] = 2 - 1 = 1

So nums = [1, -2, 3, 1]

Step 2: Sort the Array

After sorting: nums = [-2, 1, 1, 3]

Step 3: Two-Pointer Traversal

Initialize: l = 0, r = 3, ans = 0

Iteration 1: r = 3 (element value: 3)

• Check if nums[0] + nums[3] = -2 + 3 = 1 > 0 ✓ Yes!
• All indices from l to r-1 paired with r are valid
• Count = r - l = 3 - 0 = 3 valid pairs
  • Pairs: (0,3), (1,3), (2,3) with sums: 1, 4, 4
• Update: ans = 0 + 3 = 3
• Move: r = 2

Iteration 2: r = 2 (element value: 1)

• Check if nums[0] + nums[2] = -2 + 1 = -1 > 0 ✗ No
• Move l right: l = 1
• Check if nums[1] + nums[2] = 1 + 1 = 2 > 0 ✓ Yes!
• Count = r - l = 2 - 1 = 1 valid pair
  • Pair: (1,2) with sum: 2
• Update: ans = 3 + 1 = 4
• Move: r = 1

Iteration 3: r = 1 (element value: 1)

• Now l = 1 and r = 1, so l < r is false
• Loop terminates

Final Answer: 4

Verification with Original Arrays: The 4 valid pairs in terms of original indices are:

1. Indices (1,2): 1 + 4 > 3 + 1 → 5 > 4 ✓
2. Indices (0,2): 3 + 4 > 2 + 1 → 7 > 3 ✓
3. Indices (0,3): 3 + 2 > 2 + 1 → 5 > 3 ✓
4. Indices (2,3): 4 + 2 > 1 + 1 → 6 > 2 ✓

The transformation and sorting allowed us to efficiently count these pairs without checking all possible combinations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The dominant operation in this algorithm is the sorting of the nums array, which takes O(n × log n) time where n is the length of the input arrays. The list comprehension to create the nums array takes O(n) time. The two-pointer traversal in the while loop also takes O(n) time in total, as each element is visited at most twice (once by each pointer). Therefore, the overall time complexity is O(n × log n).

Space Complexity: O(n)

The algorithm creates a new array nums of size n to store the differences between corresponding elements of nums1 and nums2. This is the primary space consumption. The sorting operation may use additional space depending on the implementation (Python's Timsort uses up to O(n) auxiliary space in the worst case), but this doesn't change the overall space complexity. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Index Order Constraint

A critical pitfall is misunderstanding how the sorting transformation affects the original index constraint i < j. When we sort the difference array, we lose the original index information, which might seem problematic since the problem requires i < j.

Why this seems like a problem:

• Original constraint: We need pairs (i, j) where i < j
• After sorting, the elements are reordered, so we might think we're counting invalid pairs

Why it's actually not a problem: The key insight is that we're counting unordered pairs from the sorted array, and each unordered pair corresponds to exactly one valid ordered pair in the original array. When we find indices left < right in the sorted array that satisfy diff[left] + diff[right] > 0, this represents some pair of original indices (i, j) that would satisfy our condition - we just don't know which specific i and j they are, but we know such a pair exists.

2. Incorrect Counting Logic

Pitfall Code:

while left < right:
    if diff[left] + diff[right] > 0:
        count += 1  # Wrong! Only counts one pair
        left += 1
        right -= 1

Why it's wrong: When diff[left] + diff[right] > 0, due to the sorted nature of the array, ALL elements from left to right - 1 can pair with right to form valid pairs. The above code only counts one pair instead of right - left pairs.

Correct approach:

while left < right:
    while left < right and diff[left] + diff[right] <= 0:
        left += 1
    count += right - left  # Count all valid pairs with current right
    right -= 1

3. Inefficient Inner Loop Implementation

Pitfall Code:

while left < right:
    if diff[left] + diff[right] > 0:
        # Count all valid pairs with current right
        for k in range(left, right):
            count += 1
        right -= 1
    else:
        left += 1

Why it's inefficient: Using a for loop to count adds unnecessary time complexity. Since we know there are exactly right - left valid pairs, we can add them directly.

4. Off-by-One Errors in Counting

Common mistakes:

• Adding right - left + 1 instead of right - left (this would incorrectly count the pair (right, right))
• Not properly handling the boundary when left reaches right

Correct boundary handling:

while left < right:  # Stops when left == right (can't form a pair with itself)
    # ... rest of the logic
    count += right - left  # Correct count: includes left but excludes right itself

5. Missing Edge Cases

Pitfall: Not considering arrays where all differences are non-positive or all are positive.

Solution: The two-pointer approach naturally handles these cases:

• If all differences ≤ 0: The inner while loop will advance left until it meets right, and count remains 0
• If all differences > 0: Every pair is valid, and the algorithm correctly counts them all

Test with edge cases:

# All negative differences
nums1 = [1, 1, 1]
nums2 = [2, 2, 2]
# diff = [-1, -1, -1], result should be 0

# All positive differences
nums1 = [3, 3, 3]
nums2 = [1, 1, 1]
# diff = [2, 2, 2], result should be 3 (all possible pairs)