LeetCode 2367 - Number of Arithmetic Triplets

LeetCode Problem 2367

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Two Pointers, Enumeration

Solution

Problem Understanding

The problem requires us to find the number of arithmetic triplets in a strictly increasing array of integers. An arithmetic triplet (i, j, k) satisfies the conditions i < j < k, nums[j] - nums[i] == diff, and nums[k] - nums[j] == diff. Essentially, we are looking for sequences of three elements in the array where the difference between consecutive elements is exactly diff.

The input is a strictly increasing array nums, which guarantees no repeated numbers and ensures that all differences are positive. The output is an integer representing the count of valid triplets. Constraints indicate that nums has at most 200 elements, values are between 0 and 200, and diff is between 1 and 50. Given these constraints, a simple solution that iterates over the array multiple times is feasible, but we can optimize further using hash sets for constant-time lookups.

Important edge cases include very small arrays where no triplets exist, cases where diff is larger than the maximum difference in the array, and arrays where multiple triplets share some elements.

Approaches

The brute-force approach involves three nested loops. We iterate over all possible triplets (i, j, k) and check if they satisfy the arithmetic conditions. This guarantees correctness but has a time complexity of O(n^3), which is unnecessary for n <= 200.

The optimal approach leverages a hash set for constant-time lookups. We iterate over each element num in the array and check if both num - diff and num - 2*diff exist in the set of previously seen numbers. If both exist, then num completes an arithmetic triplet. This reduces the time complexity to O(n) and requires O(n) extra space for the set.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Checks all possible triplets explicitly
Optimal	O(n)	O(n)	Uses a hash set to check differences in constant time

Algorithm Walkthrough

1. Initialize a set seen to keep track of all numbers we have already processed.
2. Initialize a counter count to zero to track the number of valid triplets.
3. Iterate over each number num in the array nums.
4. For the current num, check if both num - diff and num - 2*diff are present in seen.
5. If both numbers exist in seen, increment count by 1 because num completes a valid arithmetic triplet.
6. Add num to the seen set for future checks.
7. After processing all numbers, return the value of count.

Why it works: This algorithm works because for any number num to form a valid triplet, the two preceding numbers separated by diff must have already appeared. Using a set ensures that these lookups are constant-time, and since we only check for valid sequences once per element, we avoid double-counting.

Python Solution

from typing import List

class Solution:
    def arithmeticTriplets(self, nums: List[int], diff: int) -> int:
        seen = set()
        count = 0
        for num in nums:
            if (num - diff) in seen and (num - 2 * diff) in seen:
                count += 1
            seen.add(num)
        return count

The implementation iterates through nums while maintaining a set of previously seen numbers. For each num, it checks if both num - diff and num - 2*diff are in the set. If so, it increments the counter. The number is then added to seen for subsequent iterations. This corresponds directly to the algorithm walkthrough.

Go Solution

func arithmeticTriplets(nums []int, diff int) int {
    seen := make(map[int]bool)
    count := 0
    for _, num := range nums {
        if seen[num - diff] && seen[num - 2*diff] {
            count++
        }
        seen[num] = true
    }
    return count
}

In Go, we use a map of integers to booleans to simulate a set. The logic is identical to the Python version. The map tracks numbers that have been processed, and we increment the counter when both required differences are found in the map.

Worked Examples

Example 1: nums = [0,1,4,6,7,10], diff = 3

num	seen	num-2*diff in seen	num-diff in seen	count
0	{}	False	False	0
1	{0}	False	False	0
4	{0,1}	False	True	0
6	{0,1,4}	True	False	0
7	{0,1,4,6}	False	True	1
10	{0,1,4,6,7}	True	True	2

Result: 2 triplets.

Example 2: nums = [4,5,6,7,8,9], diff = 2

num	seen	num-2*diff in seen	num-diff in seen	count
4	{}	False	False	0
5	{4}	False	False	0
6	{4,5}	False	False	0
7	{4,5,6}	False	True	0
8	{4,5,6,7}	True	True	1
9	{4,5,6,7,8}	True	True	2

Result: 2 triplets.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through nums once and perform constant-time set lookups per element.
Space	O(n)	We maintain a set containing up to n elements.

Since n <= 200, this solution is extremely efficient and scalable within the given constraints.

Test Cases

# Provided examples
assert Solution().arithmeticTriplets([0,1,4,6,7,10], 3) == 2  # example 1
assert Solution().arithmeticTriplets([4,5,6,7,8,9], 2) == 2  # example 2

# Edge cases
assert Solution().arithmeticTriplets([1,2,3], 1) == 1  # minimum valid triplet
assert Solution().arithmeticTriplets([1,2,3], 2) == 0  # diff too large for triplet
assert Solution().arithmeticTriplets([0,5,10,15], 5) == 2  # non-consecutive indexes
assert Solution().arithmeticTriplets([0,1,2,3,4,5], 1) == 4  # multiple overlapping triplets
assert Solution().arithmeticTriplets([0,1,2], 1) == 1  # exact 3 elements
assert Solution().arithmeticTriplets([0,200], 100) == 0  # too few elements

Test	Why
[0,1,4,6,7,10], 3	Example from problem statement
[4,5,6,7,8,9], 2	Example from problem statement
[1,2,3], 1	Minimum size triplet possible
[1,2,3], 2	No valid triplet due to large diff
[0,5,10,15], 5	Triplets with non-consecutive indexes
[0,1,2,3,4,5], 1	Multiple overlapping triplets
[0,1,2], 1	Array of exact minimum length 3
[0,200], 100	Array too short to form any triplet

Edge Cases

One important edge case is the minimum array length of 3. Here, the algorithm correctly identifies whether a single triplet exists without unnecessary iterations. Another edge case is when diff is larger than any possible difference in the array. In this case, the algorithm naturally finds no triplets because the set lookups fail. A third edge case involves overlapping triplets, where the same numbers contribute to multiple triplets. The algorithm correctly handles this because it only checks relative differences in the set and counts each valid sequence exactly once. All other possible invalid sequences are automatically ignored due to the strict increasing property of nums.