Jobs

Interviews

Discussions

3Sum Smaller

Medium

Amazon

1 view

Topics:

ArraysTwo Pointers

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.

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 = [3,1,0,-2], target = 4
Output: 3

Constraints:

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

Could you provide an algorithm to efficiently count the number of such triplets, considering the constraints and edge cases? How would you optimize your approach for larger input arrays?

3Sum Smaller

Medium

Amazon

1 view

Topics:

ArraysTwo Pointers

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.

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 = [3,1,0,-2], target = 4
Output: 3

Constraints:

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

Could you provide an algorithm to efficiently count the number of such triplets, considering the constraints and edge cases? How would you optimize your approach for larger input arrays?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the input array?
Can the input array be empty or null?
If no such triplets exist, should I return an empty list or a specific value like -1?
Are duplicate triplets allowed in the result, or should the result contain only unique triplets?
Is the order of triplets in the output important, and is the order of numbers within each triplet important?

Brute Force Solution

Approach

The brute force method for this problem is like trying every single possible combination of three numbers from the given set. We want to count how many of these combinations add up to a value less than the target number. It's a very basic approach.

Here's how the algorithm would work step-by-step:

Take the first number from the list.
Combine it with the second number.
Now, combine these first two numbers with the third number.
Add these three numbers together.
See if the total is less than the target number.
If it is, increase the count by one.
If not, do nothing and move on.
Now, try all other possible combinations of three numbers until you have checked all of them.
Once you've tried all combinations, the final count is your answer.

Code Implementation

def three_sum_smaller_brute_force(numbers, target):
    count_of_triplets = 0

    # Iterate through all possible first numbers.
    for first_number_index in range(len(numbers)):

        # Iterate through all possible second numbers.
        for second_number_index in range(first_number_index + 1, len(numbers)):

            # Iterate through all possible third numbers.
            for third_number_index in range(second_number_index + 1, len(numbers)):

                #Calculate the sum of the three numbers.
                current_sum = numbers[first_number_index] + numbers[second_number_index] + numbers[third_number_index]

                #Check if the sum is less than the target
                if current_sum < target:
                    # Increment the count if the sum is smaller
                    count_of_triplets += 1

    return count_of_triplets

Big(O) Analysis

Time Complexity

O(n^3) – The brute force approach iterates through all possible triplets in the input array. For each element in the array of size n, we have a nested loop to select the second element and then another nested loop to select the third element. This means we have three nested loops, each potentially iterating up to n times. Therefore, the time complexity is proportional to n * n * n, which simplifies to O(n^3).

Space Complexity

O(1) – The brute force solution iterates through the input array using indices. It does not create any auxiliary data structures like lists, hash maps, or trees. The algorithm only uses a few integer variables to keep track of the indices and the count, which consume constant space, irrespective of the input size N, where N is the number of elements in the input array. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The goal is to count combinations of three numbers in a list that add up to less than a target value. The efficient approach involves sorting the numbers first, then strategically moving through the list to find valid combinations, avoiding unnecessary checks.

Here's how the algorithm would work step-by-step:

First, put the numbers in order from smallest to largest. This helps us make decisions later.
Pick a number from the beginning of the ordered list.
Use two 'pointers'. One starts at the number right after the chosen number, and the other starts at the very end of the list.
Add the chosen number to the numbers at the two pointer locations. If the total is less than the target, you've found a valid combination, and all combinations between the two pointers are also valid. This is because the list is sorted, so any number between the two pointers would also result in a sum less than the target. Count these combinations.
If the total is less than the target, move the 'start' pointer towards the right to try a larger number, and therefore increase the sum.
If the total is not less than the target, move the 'end' pointer towards the left to try a smaller number, therefore decreasing the sum.
Repeat the two pointer process for the initially chosen number until the pointers meet. This ensures all valid combinations that include that number are found.
Move to the next number in the sorted list and repeat the pointer process.
Continue until you have checked every number as the first number in the combination.

Code Implementation

def three_sum_smaller(nums, target):
    nums.sort()
    length_of_nums = len(nums)
    count_of_combinations = 0

    for first_number_index in range(length_of_nums - 2):
        left_pointer = first_number_index + 1
        right_pointer = length_of_nums - 1

        # Use two pointers to find pairs that sum up to less than the target
        while left_pointer < right_pointer:
            current_sum = nums[first_number_index] + nums[left_pointer] + nums[right_pointer]

            if current_sum < target:
                # If the sum is less than the target, all combinations between the pointers are valid
                count_of_combinations += right_pointer - left_pointer

                left_pointer += 1

            # If the sum is not less than the target, move the right pointer to try a smaller number
            else:

                right_pointer -= 1

    return count_of_combinations

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first sorts the input array of size n, which takes O(n log n) time. The main part of the algorithm iterates through the sorted array using a single loop (O(n)). Inside this loop, a two-pointer technique is used, which in the worst case, iterates through the remaining portion of the array (O(n)). Therefore, the nested loop structure dominates the complexity. The outer loop runs n times and the inner while loop, on average, runs n/2 times, giving n * n/2 operations. Since sorting is O(n log n) and the rest of the algorithm is O(n^2), the overall time complexity is dominated by the O(n^2) term.

Space Complexity

O(1) – The algorithm sorts the input array in place. Beyond the input array itself, it only uses a few integer variables: one to iterate through the array, and two pointers for the two-pointer technique. These variables consume a constant amount of memory regardless of the input size N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null input array	Check for null input and return an empty list or throw an IllegalArgumentException if null is not permitted.
Array with fewer than 3 elements	Return an empty list immediately, as a triplet cannot be formed.
Array with all identical elements	The algorithm should correctly count triplets even if all elements are the same; sort first, then use two pointers carefully managing duplicates.
Array with only positive numbers and a very small target	If all numbers are positive and target is small, few triplets will satisfy the condition; ensure the two-pointer approach converges correctly.
Array with only negative numbers and a very large target	If all numbers are negative and target is large, few triplets will satisfy the condition; the two-pointer approach should handle this efficiently after sorting.
Array contains duplicate triplets that sum to less than target	Increment left and right pointers appropriately to skip duplicate elements to avoid redundant counting after finding a valid triplet.
Integer overflow if sum of three integers exceeds the maximum integer value	Use long data type to store the sum of three numbers temporarily before comparing with the target to prevent overflow.
Large input array impacting time complexity	The O(n^2) time complexity of the two-pointer approach might become significant for extremely large arrays; consider if alternative approaches (though likely less efficient) might be needed for massive datasets.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the input array?
Can the input array be empty or null?
If no such triplets exist, should I return an empty list or a specific value like -1?
Are duplicate triplets allowed in the result, or should the result contain only unique triplets?
Is the order of triplets in the output important, and is the order of numbers within each triplet important?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number from the list.
Combine it with the second number.
Now, combine these first two numbers with the third number.
Add these three numbers together.
See if the total is less than the target number.
If it is, increase the count by one.
If not, do nothing and move on.
Now, try all other possible combinations of three numbers until you have checked all of them.
Once you've tried all combinations, the final count is your answer.

Code Implementation

def three_sum_smaller_brute_force(numbers, target):
    count_of_triplets = 0

    # Iterate through all possible first numbers.
    for first_number_index in range(len(numbers)):

        # Iterate through all possible second numbers.
        for second_number_index in range(first_number_index + 1, len(numbers)):

            # Iterate through all possible third numbers.
            for third_number_index in range(second_number_index + 1, len(numbers)):

                #Calculate the sum of the three numbers.
                current_sum = numbers[first_number_index] + numbers[second_number_index] + numbers[third_number_index]

                #Check if the sum is less than the target
                if current_sum < target:
                    # Increment the count if the sum is smaller
                    count_of_triplets += 1

    return count_of_triplets

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, put the numbers in order from smallest to largest. This helps us make decisions later.
Pick a number from the beginning of the ordered list.
Use two 'pointers'. One starts at the number right after the chosen number, and the other starts at the very end of the list.
Add the chosen number to the numbers at the two pointer locations. If the total is less than the target, you've found a valid combination, and all combinations between the two pointers are also valid. This is because the list is sorted, so any number between the two pointers would also result in a sum less than the target. Count these combinations.
If the total is less than the target, move the 'start' pointer towards the right to try a larger number, and therefore increase the sum.
If the total is not less than the target, move the 'end' pointer towards the left to try a smaller number, therefore decreasing the sum.
Repeat the two pointer process for the initially chosen number until the pointers meet. This ensures all valid combinations that include that number are found.
Move to the next number in the sorted list and repeat the pointer process.
Continue until you have checked every number as the first number in the combination.

Code Implementation

def three_sum_smaller(nums, target):
    nums.sort()
    length_of_nums = len(nums)
    count_of_combinations = 0

    for first_number_index in range(length_of_nums - 2):
        left_pointer = first_number_index + 1
        right_pointer = length_of_nums - 1

        # Use two pointers to find pairs that sum up to less than the target
        while left_pointer < right_pointer:
            current_sum = nums[first_number_index] + nums[left_pointer] + nums[right_pointer]

            if current_sum < target:
                # If the sum is less than the target, all combinations between the pointers are valid
                count_of_combinations += right_pointer - left_pointer

                left_pointer += 1

            # If the sum is not less than the target, move the right pointer to try a smaller number
            else:

                right_pointer -= 1

    return count_of_combinations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input array	Check for null input and return an empty list or throw an IllegalArgumentException if null is not permitted.
Array with fewer than 3 elements	Return an empty list immediately, as a triplet cannot be formed.
Array with all identical elements	The algorithm should correctly count triplets even if all elements are the same; sort first, then use two pointers carefully managing duplicates.
Array with only positive numbers and a very small target	If all numbers are positive and target is small, few triplets will satisfy the condition; ensure the two-pointer approach converges correctly.
Array with only negative numbers and a very large target	If all numbers are negative and target is large, few triplets will satisfy the condition; the two-pointer approach should handle this efficiently after sorting.
Array contains duplicate triplets that sum to less than target	Increment left and right pointers appropriately to skip duplicate elements to avoid redundant counting after finding a valid triplet.
Integer overflow if sum of three integers exceeds the maximum integer value	Use long data type to store the sum of three numbers temporarily before comparing with the target to prevent overflow.
Large input array impacting time complexity	The O(n^2) time complexity of the two-pointer approach might become significant for extremely large arrays; consider if alternative approaches (though likely less efficient) might be needed for massive datasets.