Number of Pairs After Increment - Video Solutions

Problem Overview: You are given an array of integers and an operation that allows incrementing a value. The goal is to determine how many index pairs (i, j) can become valid after applying the allowed increment operation. A pair is counted when the values satisfy the required relationship after the increment.

Approach 1: Brute Force Pair Simulation (O(n²) time, O(1) space)

Check every pair (i, j) using two nested loops. For each pair, simulate the possible increment operation and verify whether the resulting values satisfy the condition. This approach is straightforward and useful for understanding the rule behind the increment operation. However, it becomes impractical for large arrays because every pair must be evaluated explicitly.

Approach 2: Sorting + Two Pointers (O(n log n) time, O(1) space)

Sort the array first so related values appear close together. After sorting, use a two-pointer scan to track potential matches between elements that could satisfy the pair condition after an increment. Since incrementing changes a value by exactly one unit, only nearby values need to be compared. Sorting drastically reduces unnecessary comparisons and allows efficient linear scanning using the two pointers technique.

Approach 3: Frequency Map Counting (O(n) time, O(n) space)

The key observation is that incrementing a number shifts it by exactly +1. Instead of comparing every pair, track how many times each value appears using a hash map. For each number x, check how many previously seen numbers could form a valid pair with either x or x-1. This converts pair validation into constant‑time hash lookups. The approach relies on a hash table to maintain counts while iterating through the array once.

Approach 4: Fenwick Tree / Coordinate Compression (O(n log n) time, O(n) space)

If the array values are large or the pairing rule involves range checks, a Fenwick Tree (Binary Indexed Tree) can track how many elements fall within specific value ranges. Compress the values first, then update the structure as you iterate. Queries return how many prior elements could become valid after increment. This technique is common in advanced counting problems involving order statistics and prefix frequencies.

Recommended for interviews: Start with the brute force explanation to show you understand the pair condition. Then transition to the frequency map solution. Interviewers typically expect the O(n) hash‑based approach because it replaces pair comparisons with constant‑time lookups while demonstrating knowledge of counting patterns used in array and hashing problems.