algoadvance

Leetcode 2367. Number of Arithmetic Triplets

Problem Statement:

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
• nums[k] - nums[j] == diff

Return the number of unique arithmetic triplets.

Example:

Input: nums = [0,1,4,6,7,10], diff = 3
Output: 2
Explanation: 
There are 2 unique arithmetic triplets (1, 4, 7) and (4, 7, 10).

Clarifying Questions:

1. Q: Are there any constraints on the array length or elements? A: There generally will be constraints but for the sake of this problem, consider typical constraints, e.g., 1 <= nums.length <= 1000 and 0 <= nums[i] <= 2000.

2. Q: Can there be duplicate values in the array? A: No, the problem states that the array is strictly increasing, so there are no duplicates.

Strategy:

1. Initialization:
   • Create a counter to keep track of the number of valid triplets.
   • Use a HashSet to store elements of the array for quick look-up.
2. Iterate through the array:
   • For each number in the array, check if both (number - diff) and (number - 2*diff) exist in the set.
   • If both numbers are found, increment the counter as it forms a valid triplet.

Code:

import java.util.HashSet;

public class NumberOfArithmeticTriplets {
    public int arithmeticTriplets(int[] nums, int diff) {
        int count = 0;
        // Use a set to store the numbers for O(1) look-up.
        HashSet<Integer> set = new HashSet<>();
        
        for (int num : nums) {
            set.add(num);
        }
        
        // Check for each number if triplet conditions are satisfied.
        for (int num : nums) {
            if (set.contains(num - diff) && set.contains(num - 2 * diff)) {
                count++;
            }
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        NumberOfArithmeticTriplets solution = new NumberOfArithmeticTriplets();
        int[] nums = {0, 1, 4, 6, 7, 10};
        int diff = 3;
        System.out.println(solution.arithmeticTriplets(nums, diff)); // Output: 2
    }
}

Time Complexity:

• Time Complexity: O(n), where n is the length of the array. We iterate through the array twice (once to fill the set, once to find triplets), each operation being O(1) for set operations.

• Space Complexity: O(n), where n is the length of the array since we store all elements in a set.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?