Consistency before intensity

Welcome back,

Let’s remember the problem…

Problem: 2824. Count Pairs Whose Sum is Less than Target

The most important thing when reading a problem is to identify its keywords. In this case, pairs and target are the keywords to know it’s a Two-Pointers problem. 

One of the “must have” to make this algorithm work is to have a sorted vector, therefore our first step is to sort our data structure. 

Just like we’ve learned in the past two problems: 

Initialize your pointers and counter: 

L= 0 

R= array.size()-1 

countPairs=0; 

The left pointer can only move to the right, and the right pointer can only move to the left. 

The loop condition is while (L < R). When this condition is not true, it means the pointers have crossed each other or are pointing to the same element, indicating no more elements to check.

At every step of this algorithm, evaluate whether the condition has been met. Otherwise, move one of the two-pointers. Whether to move the left or the right pointer will depend on the following conditions:

• If (array[L] + array[R]) < target, since our array is sorted, it means that (array[L] + array[R-1]) < target is also true.

  If we fix the left pointer to L, then all indices between [L + 1, R] are valid candidates to be paired with L.

  Using this logic we can update our counter to be countPairs+=R-L.

  Move our left pointer to the right by doing L++,  

  we already found all the pairs that satisfy our condition. 

• Else, we need a smaller number, move our pointer to

  the left by doing R—; 

Let’s dig in with an example…

Solution

This solution combines sorting (O(N log N)) with a single array iteration (O(N)), resulting in a time complexity of O(N log N).

Let’s add it to our LeetCode tracker…

Cheers to day 3,

Denisse