Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Count Pairs in Two Arrays

Explore how to count pairs of indexes in two arrays where the sum in one array is greater than in the other. Understand how to optimize a brute force approach by using a difference array, sorting, and binary search to achieve O(n log n) time complexity. This lesson helps you apply sorting and search techniques to solve pair-counting problems efficiently.

We'll cover the following...

Statement

You are given two positive integer arrays, nums1 and nums2, both of length nn. Your task is to count and return the number of pairs of indexes (i,j)(i, j) where:

  • i<ji < j , and

  • nums1[i]+nums1[j]>nums2[i]+nums2[j]\text{nums1}[i] + \text{nums1}[j] > \text{nums2}[i] + \text{nums2}[j]

In simpler terms, the sum of two elements from nums1 must be greater than that of the corresponding elements from nums2.

Constraints:

  • n=n = nums1.length == nums2.length

  • 1≤n≤1031 \leq n \leq 10^3 ...