Jobs

Interviews

Discussions

Number of Arithmetic Triplets

Easy

Asked by:

69 views

Topics:

ArraysTwo Pointers

You are given a 0-indexed, strictly increasing integer array nums and a positive integer diff. A triplet (i, j, k) is an arithmetic triplet if the following conditions are met:

i < j < k,
nums[j] - nums[i] == diff, and
nums[k] - nums[j] == diff.

Return the number of unique arithmetic triplets.

Example 1:

Input: nums = [0,1,4,6,7,10], diff = 3
Output: 2
Explanation:
(1, 2, 4) is an arithmetic triplet because both 7 - 4 == 3 and 4 - 1 == 3.
(2, 4, 5) is an arithmetic triplet because both 10 - 7 == 3 and 7 - 4 == 3.

Example 2:

Input: nums = [4,5,6,7,8,9], diff = 2
Output: 2
Explanation:
(0, 2, 4) is an arithmetic triplet because both 8 - 6 == 2 and 6 - 4 == 2.
(1, 3, 5) is an arithmetic triplet because both 9 - 7 == 2 and 7 - 5 == 2.

Constraints:

3 <= nums.length <= 200
0 <= nums[i] <= 200
1 <= diff <= 50
nums is strictly increasing.

Try coding it in LeetCode

Number of Arithmetic Triplets

Easy

Asked by:

69 views

Topics:

ArraysTwo Pointers

You are given a 0-indexed, strictly increasing integer array nums and a positive integer diff. A triplet (i, j, k) is an arithmetic triplet if the following conditions are met:

i < j < k,
nums[j] - nums[i] == diff, and
nums[k] - nums[j] == diff.

Return the number of unique arithmetic triplets.

Example 1:

Input: nums = [0,1,4,6,7,10], diff = 3
Output: 2
Explanation:
(1, 2, 4) is an arithmetic triplet because both 7 - 4 == 3 and 4 - 1 == 3.
(2, 4, 5) is an arithmetic triplet because both 10 - 7 == 3 and 7 - 4 == 3.

Example 2:

Input: nums = [4,5,6,7,8,9], diff = 2
Output: 2
Explanation:
(0, 2, 4) is an arithmetic triplet because both 8 - 6 == 2 and 6 - 4 == 2.
(1, 3, 5) is an arithmetic triplet because both 9 - 7 == 2 and 7 - 5 == 2.

Constraints:

3 <= nums.length <= 200
0 <= nums[i] <= 200
1 <= diff <= 50
nums is strictly increasing.

Try coding it in LeetCode

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 expected range and data type of the numbers within the input array `nums`?
Can the input array `nums` be empty or null?
Is the input array `nums` guaranteed to be sorted in ascending order?
If no arithmetic triplets are found, what should the function return?
Are duplicate values allowed within the array `nums`, and if so, how should they be handled when identifying triplets?

Brute Force Solution

Approach

The brute force approach to finding arithmetic triplets involves checking every possible combination of three numbers from the list. We'll look at all possible groups of three numbers, one at a time, and see if they meet the requirement of forming an arithmetic sequence. If they do, we'll count them, and in the end, we'll have the total number of triplets.

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

Take the first number from the list.
Then, for that first number, pick a second number from the list that comes after it.
For each pair of the first and second numbers you've picked, pick a third number from the list that comes after the second number.
For each group of three numbers, check if they form an arithmetic sequence, meaning the difference between the first two is the same as the difference between the last two.
If the three numbers do form an arithmetic sequence, increase your count.
Repeat this process of picking three numbers and checking if they form an arithmetic sequence for all possible combinations of three numbers from the list.
Finally, report the total count of arithmetic triplets you found.

Code Implementation

def arithmetic_triplets(numbers, difference):
    count = 0

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

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

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

                # Checks if the current combination forms an arithmetic sequence.
                if numbers[second_number_index] - numbers[first_number_index] == difference:

                    # If the first condition is true, check the second
                    if numbers[third_number_index] - numbers[second_number_index] == difference:
                        count += 1

    return count

Big(O) Analysis

Time Complexity

O(n^3) – The described brute force approach involves iterating through all possible triplets in the array. The outer loop iterates up to n times. The second nested loop then iterates up to n times for each of the outer loop's iterations. Finally, the innermost loop iterates up to n times for each of the second loop's iterations. Therefore, the total number of operations is proportional to n * n * n, which simplifies to O(n^3).

Space Complexity

O(1) – The brute force approach outlined in the plain English explanation iterates through the input list using nested loops to find triplets. It only uses a constant number of variables (loop counters and a count variable) to keep track of the indices and the number of arithmetic triplets found. The algorithm doesn't create any auxiliary data structures that scale with the input size N (the length of the input list). Therefore, the space complexity is constant.

Optimal Solution

Approach

The fastest way to find these special number groups is to check each number only once. We can use a tool that lets us quickly see if certain numbers exist, so we don't have to search through the whole list every time.

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

First, create a record of all the numbers that appear in the list. This record will let you quickly check if a number is present.
Go through the list one number at a time.
For each number, check if the number plus the difference is in the record, and if the number plus twice the difference is also in the record.
If both of those numbers are in the record, then you've found a special group of three numbers.
Keep a count of all the special groups you find.
Once you've gone through the whole list, the count will tell you how many special groups there are in total.

Code Implementation

def arithmeticTriplets(numbers, difference):
    numbers_set = set(numbers)

    arithmetic_triplets_count = 0

    for current_number in numbers:
        # Check if number + difference and number + 2*difference exist.

        if (current_number + difference) in numbers_set and \
           (current_number + 2 * difference) in numbers_set:
            arithmetic_triplets_count += 1

    return arithmetic_triplets_count

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input array nums of size n once. Inside the loop, it performs constant-time lookups using a hash set (the record of numbers). Checking for the presence of `num + diff` and `num + 2 * diff` in the hash set takes O(1) time each. Therefore, the dominant operation is the single iteration over the array, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm creates a record (likely a hash set or similar data structure) to store all the numbers from the input list. This record allows for quick lookups to check if specific numbers exist. The space required for this record grows linearly with the number of unique elements in the input list. Therefore, the auxiliary space used is proportional to N, where N is the number of elements in the input array.

Edge Cases

Case	How to Handle
Empty array or array with fewer than 3 elements	Return 0 immediately, as an arithmetic triplet requires at least 3 elements.
Array with all identical values and difference is 0	The number of triplets should be n choose 3, where n is the length of the array; handle combinations correctly.
Large array size that could cause performance issues (e.g., exceeding time limit)	Utilize an efficient algorithm (e.g., hash map or set lookup) to achieve O(n) or O(n log n) time complexity.
Large difference value potentially leading to integer overflow	Use a data type that can accommodate large values, such as `long` in Java or C++ or check that difference will not overflow.
Input array contains negative numbers	The algorithm should correctly handle negative numbers when calculating the differences and checking for the existence of elements.
Difference is zero	The algorithm should handle the special case where the common difference is zero, as this can lead to multiple triplets.
No arithmetic triplets exist in the array	The algorithm should correctly return 0 when no arithmetic triplets are found.
Array contains extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)	Be cautious of potential integer overflow when calculating the differences, consider using long.

Empty array or array with fewer than 3 elements

How to Handle:

Return 0 immediately, as an arithmetic triplet requires at least 3 elements.

Array with all identical values and difference is 0

How to Handle:

The number of triplets should be n choose 3, where n is the length of the array; handle combinations correctly.

Large array size that could cause performance issues (e.g., exceeding time limit)

How to Handle:

Utilize an efficient algorithm (e.g., hash map or set lookup) to achieve O(n) or O(n log n) time complexity.

Large difference value potentially leading to integer overflow

How to Handle:

Use a data type that can accommodate large values, such as `long` in Java or C++ or check that difference will not overflow.

Input array contains negative numbers

How to Handle:

The algorithm should correctly handle negative numbers when calculating the differences and checking for the existence of elements.

Difference is zero

How to Handle:

The algorithm should handle the special case where the common difference is zero, as this can lead to multiple triplets.

No arithmetic triplets exist in the array

How to Handle:

The algorithm should correctly return 0 when no arithmetic triplets are found.

Array contains extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)

How to Handle:

Be cautious of potential integer overflow when calculating the differences, consider using long.

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 expected range and data type of the numbers within the input array `nums`?
Can the input array `nums` be empty or null?
Is the input array `nums` guaranteed to be sorted in ascending order?
If no arithmetic triplets are found, what should the function return?
Are duplicate values allowed within the array `nums`, and if so, how should they be handled when identifying triplets?

Brute Force Solution

Approach

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

Take the first number from the list.
Then, for that first number, pick a second number from the list that comes after it.
For each pair of the first and second numbers you've picked, pick a third number from the list that comes after the second number.
For each group of three numbers, check if they form an arithmetic sequence, meaning the difference between the first two is the same as the difference between the last two.
If the three numbers do form an arithmetic sequence, increase your count.
Repeat this process of picking three numbers and checking if they form an arithmetic sequence for all possible combinations of three numbers from the list.
Finally, report the total count of arithmetic triplets you found.

Code Implementation

def arithmetic_triplets(numbers, difference):
    count = 0

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

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

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

                # Checks if the current combination forms an arithmetic sequence.
                if numbers[second_number_index] - numbers[first_number_index] == difference:

                    # If the first condition is true, check the second
                    if numbers[third_number_index] - numbers[second_number_index] == difference:
                        count += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, create a record of all the numbers that appear in the list. This record will let you quickly check if a number is present.
Go through the list one number at a time.
For each number, check if the number plus the difference is in the record, and if the number plus twice the difference is also in the record.
If both of those numbers are in the record, then you've found a special group of three numbers.
Keep a count of all the special groups you find.
Once you've gone through the whole list, the count will tell you how many special groups there are in total.

Code Implementation

def arithmeticTriplets(numbers, difference):
    numbers_set = set(numbers)

    arithmetic_triplets_count = 0

    for current_number in numbers:
        # Check if number + difference and number + 2*difference exist.

        if (current_number + difference) in numbers_set and \
           (current_number + 2 * difference) in numbers_set:
            arithmetic_triplets_count += 1

    return arithmetic_triplets_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array or array with fewer than 3 elements	Return 0 immediately, as an arithmetic triplet requires at least 3 elements.
Array with all identical values and difference is 0	The number of triplets should be n choose 3, where n is the length of the array; handle combinations correctly.
Large array size that could cause performance issues (e.g., exceeding time limit)	Utilize an efficient algorithm (e.g., hash map or set lookup) to achieve O(n) or O(n log n) time complexity.
Large difference value potentially leading to integer overflow	Use a data type that can accommodate large values, such as `long` in Java or C++ or check that difference will not overflow.
Input array contains negative numbers	The algorithm should correctly handle negative numbers when calculating the differences and checking for the existence of elements.
Difference is zero	The algorithm should handle the special case where the common difference is zero, as this can lead to multiple triplets.
No arithmetic triplets exist in the array	The algorithm should correctly return 0 when no arithmetic triplets are found.
Array contains extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)	Be cautious of potential integer overflow when calculating the differences, consider using long.

Empty array or array with fewer than 3 elements

How to Handle:

Return 0 immediately, as an arithmetic triplet requires at least 3 elements.

Array with all identical values and difference is 0

How to Handle:

The number of triplets should be n choose 3, where n is the length of the array; handle combinations correctly.

Large array size that could cause performance issues (e.g., exceeding time limit)

How to Handle:

Utilize an efficient algorithm (e.g., hash map or set lookup) to achieve O(n) or O(n log n) time complexity.

Large difference value potentially leading to integer overflow

How to Handle:

Use a data type that can accommodate large values, such as `long` in Java or C++ or check that difference will not overflow.

Input array contains negative numbers

How to Handle:

The algorithm should correctly handle negative numbers when calculating the differences and checking for the existence of elements.

Difference is zero

How to Handle:

The algorithm should handle the special case where the common difference is zero, as this can lead to multiple triplets.

No arithmetic triplets exist in the array

How to Handle:

The algorithm should correctly return 0 when no arithmetic triplets are found.

Array contains extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)

How to Handle:

Be cautious of potential integer overflow when calculating the differences, consider using long.