Skip to content

2475. Number of Unequal Triplets in Array

SourceWeekly Contest 320 Q1DifficultyEasyRating1255

Description

You are given a 0-indexed array of positive integers nums. Find the number of triplets (i, j, k) that meet the following conditions:

  • 0 <= i < j < k < nums.length
  • nums[i], nums[j], and nums[k] are pairwise distinct.
    • In other words, nums[i] != nums[j], nums[i] != nums[k], and nums[j] != nums[k].

Return the number of triplets that meet the conditions.

 

Example 1:

Input: nums = [4,4,2,4,3]
Output: 3
Explanation: The following triplets meet the conditions:
- (0, 2, 4) because 4 != 2 != 3
- (1, 2, 4) because 4 != 2 != 3
- (2, 3, 4) because 2 != 4 != 3
Since there are 3 triplets, we return 3.
Note that (2, 0, 4) is not a valid triplet because 2 > 0.

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: No triplets meet the conditions so we return 0.

 

Constraints:

  • 3 <= nums.length <= 100
  • 1 <= nums[i] <= 1000

Solutions

Solution 1: Brute Force Enumeration

Thinking

With \(n\le 100\), ordered triples fit in a triple loop that tests pairwise inequality.

We can directly enumerate all triples \((i, j, k)\) and count all the ones that meet the conditions.

The time complexity is \(O(n^3)\), where \(n\) is the length of the array \(nums\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    ans += (
                        nums[i] != nums[j] and nums[j] != nums[k] and nums[i] != nums[k]
                    )
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int unequalTriplets(int[] nums) {
        int n = nums.length;
        int ans = 0;
        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[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k]) {
                        ++ans;
                    }
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int unequalTriplets(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        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[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k]) {
                        ++ans;
                    }
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func unequalTriplets(nums []int) (ans int) {
    n := len(nums)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            for k := j + 1; k < n; k++ {
                if nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k] {
                    ans++
                }
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function unequalTriplets(nums: number[]): number {
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] !== nums[j] && nums[j] !== nums[k] && nums[i] !== nums[k]) {
                    ans++;
                }
            }
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn unequal_triplets(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        for i in 0..n - 2 {
            for j in i + 1..n - 1 {
                for k in j + 1..n {
                    if nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k] {
                        ans += 1;
                    }
                }
            }
        }
        ans
    }
}

Thinking

Method 1 is \(O(n^3)\). After sorting, equals sit together. Fix the middle index \(j\); the product of how many values are strictly smaller on the left and strictly larger on the right is the contribution. Two binary searches find the borders.

We can also sort the array \(nums\) first.

Then traverse \(nums\), enumerate the middle element \(nums[j]\), and use binary search to find the nearest index \(i\) on the left side of \(nums[j]\) such that \(nums[i] < nums[j]\); find the nearest index \(k\) on the right side of \(nums[j]\) such that \(nums[k] > nums[j]\). Then the number of triples with \(nums[j]\) as the middle element and meeting the conditions is \((i + 1) \times (n - k)\), which is added to the answer.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array \(nums\).

1
2
3
4
5
6
7
8
9
class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        nums.sort()
        ans, n = 0, len(nums)
        for j in range(1, n - 1):
            i = bisect_left(nums, nums[j], hi=j) - 1
            k = bisect_right(nums, nums[j], lo=j + 1)
            ans += (i >= 0 and k < n) * (i + 1) * (n - k)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int unequalTriplets(int[] nums) {
        Arrays.sort(nums);
        int ans = 0, n = nums.length;
        for (int j = 1; j < n - 1; ++j) {
            int i = search(nums, nums[j], 0, j) - 1;
            int k = search(nums, nums[j] + 1, j + 1, n);
            if (i >= 0 && k < n) {
                ans += (i + 1) * (n - k);
            }
        }
        return ans;
    }

    private int search(int[] nums, int x, int left, int right) {
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int unequalTriplets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0, n = nums.size();
        for (int j = 1; j < n - 1; ++j) {
            int i = lower_bound(nums.begin(), nums.begin() + j, nums[j]) - nums.begin() - 1;
            int k = upper_bound(nums.begin() + j + 1, nums.end(), nums[j]) - nums.begin();
            if (i >= 0 && k < n) {
                ans += (i + 1) * (n - k);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func unequalTriplets(nums []int) (ans int) {
    sort.Ints(nums)
    n := len(nums)
    for j := 1; j < n-1; j++ {
        i := sort.Search(j, func(h int) bool { return nums[h] >= nums[j] }) - 1
        k := sort.Search(n, func(h int) bool { return h > j && nums[h] > nums[j] })
        if i >= 0 && k < n {
            ans += (i + 1) * (n - k)
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function unequalTriplets(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;
    const search = (x: number, left: number, right: number): number => {
        while (left < right) {
            const mid = (left + right) >> 1;
            if (nums[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
    for (let j = 1; j < n - 1; ++j) {
        const i = search(nums[j], 0, j) - 1;
        const k = search(nums[j] + 1, j + 1, n);
        if (i >= 0 && k < n) {
            ans += (i + 1) * (n - k);
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl Solution {
    pub fn unequal_triplets(mut nums: Vec<i32>) -> i32 {
        nums.sort_unstable();
        let n = nums.len();
        let mut ans = 0;
        for j in 1..n - 1 {
            let i = nums[..j].partition_point(|&x| x < nums[j]) as i32 - 1;
            let k = j + 1 + nums[j + 1..].partition_point(|&x| x <= nums[j]);
            if i >= 0 && k < n {
                ans += (i + 1) * (n - k) as i32;
            }
        }
        ans
    }
}

Solution 3: Hash Table

Thinking

Method 2 still sorts. Only distinct values matter, not indices, so count frequencies: for a middle count \(b\), with \(a\) already seen and \(c=n-a-b\), add \(a\cdot b\cdot c\). Linear.

We can also use a hash table \(cnt\) to count the number of each element in the array \(nums\).

Then traverse the hash table \(cnt\), enumerate the number of middle elements \(b\), and denote the number of elements on the left as \(a\). Then the number of elements on the right is \(c = n - a - b\). At this time, the number of triples that meet the conditions is \(a \times b \times c\), which is added to the answer. Then update \(a = a + b\) and continue to enumerate the number of middle elements \(b\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(nums\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        n = len(nums)
        ans = a = 0
        for b in cnt.values():
            c = n - a - b
            ans += a * b * c
            a += b
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int unequalTriplets(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int v : nums) {
            cnt.merge(v, 1, Integer::sum);
        }
        int ans = 0, a = 0;
        int n = nums.length;
        for (int b : cnt.values()) {
            int c = n - a - b;
            ans += a * b * c;
            a += b;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int unequalTriplets(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (int& v : nums) {
            ++cnt[v];
        }
        int ans = 0, a = 0;
        int n = nums.size();
        for (auto& [_, b] : cnt) {
            int c = n - a - b;
            ans += a * b * c;
            a += b;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func unequalTriplets(nums []int) (ans int) {
    cnt := map[int]int{}
    for _, v := range nums {
        cnt[v]++
    }
    a, n := 0, len(nums)
    for _, b := range cnt {
        c := n - a - b
        ans += a * b * c
        a += b
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
use std::collections::HashMap;

impl Solution {
    pub fn unequal_triplets(nums: Vec<i32>) -> i32 {
        let cnt = nums.iter().fold(HashMap::new(), |mut map, &n| {
            *map.entry(n).or_insert(0) += 1;
            map
        });

        let mut ans = 0;
        let n = nums.len();
        let mut a = 0;
        for &b in cnt.values() {
            let c = n - a - b;
            ans += a * b * c;
            a += b;
        }

        ans as i32
    }
}

Comments