algoadvance

Leetcode 2475. Number of Unequal Triplets in Array

Problem Statement

You are given a 0-indexed integer array nums, and you are asked to return the total number of triplets (i, j, k) such that:

1. 0 <= i < j < k < nums.length
2. nums[i] != nums[j]
3. nums[j] != nums[k]
4. nums[i] != nums[k]

Clarifying Questions

1. Q: What is the range of the length of the array nums?
   • A: The length of nums can be up to 1000.
2. Q: What is the range of the elements in the array nums?
   • A: The elements of nums can be from 1 to 1000.
3. Q: Can there be duplicate elements in the array?
   • A: Yes, there can be duplicate elements in nums.

Strategy

• Brute Force Approach: We can iterate over all possible triplets (i, j, k) and check the conditions whether they are unequal. This approach would have a time complexity of (O(n^3)), where (n) is the length of the array.
• Optimized Approach: Since the brute force approach might be too slow for larger values of n, we need a more optimized approach:
  • Use nested loops to iterate through valid i, j, and k, and check the inequality conditions.

Code

public class UnequalTriplets {

    public static int unequalTriplets(int[] nums) {
        int n = nums.length;
        int count = 0;

        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k]) {
                        count++;
                    }
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 1};
        System.out.println(unequalTriplets(nums1)); // Output: 1

        int[] nums2 = {4, 4, 2, 4, 3};
        System.out.println(unequalTriplets(nums2)); // Output: 3

        int[] nums3 = {1, 1, 1, 1};
        System.out.println(unequalTriplets(nums3)); // Output: 0
    }
}

Time Complexity

• Time Complexity: (O(n^3)) - The solution consists of three nested loops iterating over the length of the array nums. Each loop decreases the range of traversal for the succeeding loop.
• Space Complexity: (O(1)) - We use a constant amount of extra space irrespective of the input size.

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?