Number of Arithmetic Triplets

EASY

Description

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.

Approaches

Checkout 3 different approaches to solve Number of Arithmetic Triplets. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Triple Nested Loops

The brute-force approach is the most straightforward solution. It involves iterating through every possible triplet of elements in the array and checking if they satisfy the conditions for an arithmetic triplet.

Algorithm

Initialize a counter count to 0.
Use three nested loops to iterate through all possible combinations of indices (i, j, k) such that i < j < k.
The outer loop for i runs from 0 to n-3.
The middle loop for j runs from i+1 to n-2.
The inner loop for k runs from j+1 to n-1.
Inside the innermost loop, check if nums[j] - nums[i] == diff and nums[k] - nums[j] == diff.
If both conditions are met, increment count.
After the loops complete, return count.

We can use three nested loops to generate all unique triplets of indices (i, j, k) where i < j < k. For each generated triplet, we access the corresponding numbers nums[i], nums[j], and nums[k]. We then check if they form an arithmetic progression with the given common difference diff. Specifically, we test if nums[j] - nums[i] == diff and nums[k] - nums[j] == diff. If both conditions hold true, we've found a valid arithmetic triplet and we increment a counter. After checking all possible triplets, the final value of the counter is the answer.

class Solution {
    public int arithmeticTriplets(int[] nums, int diff) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[j] - nums[i] == diff && nums[k] - nums[j] == diff) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n^3), where `n` is the number of elements in `nums`. The three nested loops result in a cubic time complexity as we check every possible triplet.Space Complexity: O(1), as it only uses a constant amount of extra space for loop variables and the counter.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space, aside from a few variables.

Cons:

Highly inefficient with a time complexity of O(n^3).
May be too slow for larger input sizes, though it passes for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Number of Arithmetic Triplets. Click on different languages to view the code.

class Solution {
public
  int arithmeticTriplets(int[] nums, int diff) {
    int ans = 0;
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        for (int k = j + 1; k < n; ++k) {
          if (nums[j] - nums[i] == diff && nums[k] - nums[j] == diff) {
            ++ans;
          }
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Number of Arithmetic Triplets

Patterns:

Two PointersEnumeration

Data Structures:

ArrayHash Table