## 259. 3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]


Follow up:
Could you solve it in O(n2) runtime?

b'
\n\n

## Solution

\n
\n

#### Approach #1 (Brute Force) [Time Limit Exceeded]

\n

The brute force approach is to find every possible triplets subjected to and test for the condition.

\n

Complexity analysis

\n
\n
• \n

Time complexity : .\nThe total number of such triplets is , which is . Therefore, the time complexity of the brute force approach is .

\n
• \n
• \n

Space complexity : .

\n
• \n
\n
\n

#### Approach #2 (Binary Search) [Accepted]

\n

Before we solve this problem, it is helpful to first solve this simpler twoSum version.

\n
\n

Given a array, find the number of index pairs , with that satisfy the condition \n

\n
\n

If we sort the array first, then we could apply binary search to find the largest index such that for each . Once we found that largest index , we know there must be pairs that satisfy the above condition with \'s value fixed.

\n

Finally, we can now apply the twoSum solution to threeSum directly by wrapping an outer for-loop around it.

\n
public int threeSumSmaller(int[] nums, int target) {\n    Arrays.sort(nums);\n    int sum = 0;\n    for (int i = 0; i < nums.length - 2; i++) {\n        sum += twoSumSmaller(nums, i + 1, target - nums[i]);\n    }\n    return sum;\n}\n\nprivate int twoSumSmaller(int[] nums, int startIndex, int target) {\n    int sum = 0;\n    for (int i = startIndex; i < nums.length - 1; i++) {\n        int j = binarySearch(nums, i, target - nums[i]);\n        sum += j - i;\n    }\n    return sum;\n}\n\nprivate int binarySearch(int[] nums, int startIndex, int target) {\n    int left = startIndex;\n    int right = nums.length - 1;\n    while (left < right) {\n        int mid = (left + right + 1) / 2;\n        if (nums[mid] < target) {\n            left = mid;\n        } else {\n            right = mid - 1;\n        }\n    }\n    return left;\n}\n
\n

Note that in the above binary search we choose the upper middle element instead of the lower middle element . The reason is due to the terminating condition when there are two elements left. If we chose the lower middle element and the condition evaluates to true, then the loop will never terminate. Choosing the upper middle element will guarantee termination.

\n

Complexity analysis

\n
\n
• \n

Time complexity : .\nThe binarySearch function takes time, therefore the twoSumSmaller takes time. The threeSumSmaller wraps with another for-loop, and therefore is time.

\n
• \n
• \n

Space complexity : .

\n
• \n
\n
\n

#### Approach #3 (Two Pointers) [Accepted]

\n

Let us try sorting the array first. For example, becomes .

\n

Let us look at an example , and .

\n
[1, 2, 3, 5, 8]\n \xe2\x86\x91           \xe2\x86\x91\nleft       right\n
\n

Let us initialize two indices, and pointing to the first and last element respectively.

\n

When we look at the sum of first and last element, it is , which is . That tells us no index pair will ever contain the index . So the next logical step is to move the right pointer one step to its left.

\n
[1, 2, 3, 5, 8]\n \xe2\x86\x91        \xe2\x86\x91\nleft    right\n
\n

Now the pair sum is , which is . How many pairs with one of the that satisfy the condition? You can tell by the difference between and which is , namely and . Therefore, we move one step to its right.

\n
public int threeSumSmaller(int[] nums, int target) {\n    Arrays.sort(nums);\n    int sum = 0;\n    for (int i = 0; i < nums.length - 2; i++) {\n        sum += twoSumSmaller(nums, i + 1, target - nums[i]);\n    }\n    return sum;\n}\n\nprivate int twoSumSmaller(int[] nums, int startIndex, int target) {\n    int sum = 0;\n    int left = startIndex;\n    int right = nums.length - 1;\n    while (left < right) {\n        if (nums[left] + nums[right] < target) {\n            sum += right - left;\n            left++;\n        } else {\n            right--;\n        }\n    }\n    return sum;\n}\n
\n

Complexity analysis

\n
\n
• \n

Time complexity : .\nThe twoSumSmaller function takes time because both left and right traverse at most n steps. Therefore, the overall time complexity is .

\n
• \n
• \n

Space complexity : .

\n
• \n
\n
'