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:

Return the number of unique arithmetic triplets.

Example 1:

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

Example 2:

Input: nums = [4,5,6,7,8,9], diff = 2
Output: 2
Explanation: The triplets are (0, 2, 4) and (1, 3, 5).

Clarifying Questions

  1. Q: What is the maximum size of the nums array?
    • A: The size of nums can be up to (10^4).
  2. Q: What is the range of values for the elements in the nums array?
    • A: The elements in nums are integers within the range ([0, 200]).
  3. Q: Will there be duplicates in nums?
    • A: No, nums is strictly increasing, so no duplicates will be present.
  4. Q: What if there are no valid triplets?
    • A: Return 0 in that case.

Strategy

  1. Initial Observation:
    • For a triplet (i, j, k) to be valid, the differences between the elements must satisfy:
      • nums[j] - nums[i] == diff
      • nums[k] - nums[j] == diff
    • This can be reformulated as:
      • nums[j] == nums[i] + diff
      • nums[k] == nums[j] + diff
  2. Approach:
    • We can leverage a hash set to track elements as we iterate through nums.
    • For each element nums[k]:
      • We check if both nums[k] - diff and nums[k] - 2 * diff are present in the previously encountered elements.
    • This approach ensures that we only need to make O(n) checks using hash set operations which are average O(1).
  3. Steps:
    • Iterate over the array and insert elements into a hash set.
    • For each element, check if the required preceding elements to form the triplet exist in the set.

Time Complexity:

Code

Here is the implementation based on the above strategy:

#include <vector>
#include <unordered_set>

class Solution {
public:
    int arithmeticTriplets(std::vector<int>& nums, int diff) {
        std::unordered_set<int> seen;
        int count = 0;

        for (int num : nums) {
            if (seen.count(num - diff) && seen.count(num - 2 * diff)) {
                count++;
            }
            seen.insert(num);
        }

        return count;
    }
};

This code uses an unordered set to store the encountered numbers and checks for the presence of required numbers to form valid triplets in O(1) average time. The final count of such triplets is returned.

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