Coding Daily

Problem Description

Given an array of integers and a target value, count the number of pairs in the array whose sum is strictly less than the target.

Example:

Input: arr[] = [7, 2, 5, 3], target = 8
Output: 2
Explanation: The pairs (2, 5) and (2, 3) have sums less than 8.

Solution Code

import java.util.Arrays;

class Solution {
    int countPairs(int arr[], int target) {
        Arrays.sort(arr); // Sort the array to use the two-pointer approach
        int left = 0; // Pointer to the start of the array
        int right = arr.length - 1; // Pointer to the end of the array
        int count = 0; // To store the count of valid pairs

        while (left < right) {
            int sum = arr[left] + arr[right]; // Calculate the current sum

            if (sum < target) {
                // If the sum is less than the target, all pairs between left and right are valid
                count += right - left;
                left++; // Move the left pointer to the right
            } else {
                right--; // Move the right pointer to the left
            }
        }

        return count;
    }
}

Hint

Sort the array and use a two-pointer approach to efficiently count the number of pairs whose sum is less than the target.

Approach Name

Two-Pointer Technique with Sorting

Intuition

By sorting the array, we can use two pointers to traverse the array from both ends. This allows us to efficiently count the number of pairs whose sum is less than the target. If the sum of the elements at the current pointers is less than the target, all pairs between the left and right pointers are valid.

Algorithm

Sort the array in ascending order.
Initialize two pointers, left at the start and right at the end of the array.
Use a variable count to keep track of the number of valid pairs.
While left < right:
- Calculate the sum of the elements at left and right.
- If the sum is less than the target, increment the count by right - left (all pairs between left and right are valid) and move the left pointer to the right.
- If the sum is greater than or equal to the target, move the right pointer to the left.
Return the count of valid pairs.

Test Input

7 2 5 3, 8

Complexity Analysis

Time Complexity: O(n log n), where n is the number of elements in the array. Sorting takes O(n log n), and the two-pointer traversal takes O(n).
Space Complexity: O(1), as we are using a constant amount of extra space.

This solution efficiently counts the number of pairs whose sum is less than the target using sorting and a two-pointer approach, ensuring optimal performance for the given constraints.

Count Pairs whose sum is less than target