3Sum Smaller

Problem Statement

The task involves analyzing an array nums of n integers and an integer value target. The objective is to determine the number of triplets of distinct indices (i, j, k) where 0 <= i < j < k < n such that the sum of the elements at these indices (nums[i] + nums[j] + nums[k]) is less than the given target. This kind of problem falls under the category of array processing and can be typically solved using different algorithmic strategies depending on the constraints provided.

Examples

Example 1

Input:

nums = [-2,0,1,3], target = 2

Output:

2

Explanation:

Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

Example 2

Input:

nums = [], target = 0

Output:

0

Example 3

Input:

nums = [0], target = 0

Output:

0

Constraints

• n == nums.length
• 0 <= n <= 3500
• -100 <= nums[i] <= 100
• -100 <= target <= 100

Approach and Intuition

Understanding the approach to solve this problem involves dissecting the example data and aligning it with the constraints:

1. Review a straightforward brute-force solution:
   • Iterate through all possible triples in the array nums using three nested loops reflecting indices i, j, and k.
   • For each iteration, check whether the sum of the triplet is less than the specified target.
   • Count all such valid triplets.

Taking insights from the examples:

• Example 1:

  • Input: nums = [-2,0,1,3], target = 2
  • nums[i] + nums[j] + nums[k] comparisons are made for each possible triplet combination.
  • Several combinations are inspected such as [-2,0,1] and [-2,0,3]. Both qualify as their sums are less than the target.

• Example 2 & 3:

  • Immediately reveals a scenario where either n is very small, i.e., n=0 in Example 2 (empty array) or n=1 in Example 3 (impossible to form a triplet). Regular checks and constraints handling will swiftly output 0 in these cases.

Given the constraints allow for n to be as large as 3500, a brute-force solution might not be optimal due to potentially O(n^3) time complexity. Thus, specific optimization techniques or efficient algorithms like sorting combined with two-pointer technique should be considered to improve the performance. In essence, one sorts the array and traverses it using one index while using two pointers for the other two indices, adjusting positions based on the sum comparison to the target. This leverages the sorted nature of array elements to make effective leaps in indices, greatly reducing the possible triplet combinations to be tested.

Solutions

class Solution {
    public int countTriplets(int[] vals, int limit) {
        Arrays.sort(vals);
        int count = 0;
        for (int i = 0; i < vals.length - 2; i++) {
            count += helper(vals, i + 1, limit - vals[i]);
        }
        return count;
    }

    private int helper(int[] vals, int startIdx, int limit) {
        int accum = 0;
        int lo = startIdx;
        int hi = vals.length - 1;
        while (lo < hi) {
            if (vals[lo] + vals[hi] < limit) {
                accum += hi - lo;
                lo++;
            } else {
                hi--;
            }
        }
        return accum;
    }
}