Using a Hash Table to Find A Number and Its Triple in a List

Given a list of integers nums, return whether there’s two numbers such that one is a triple of another.

Constraints
n ≤ 100,000 where n is the length of nums.
Example 1
Input
nums = [2, 3, 10, 7, 6]
Output
True
Explanation
6 is a triple of 2

Example 2
Input
nums = [3, 4, 5]
Output
False
Explanation
There’s no 9, 12, or 15.

Example 3
Input
nums = [0, 2, 0]
Output
True
Explanation
0 is a triple of 0

Finding the Triple in a List

Zero is a special case, that its triple is also zero, thus when the number is zero, we have to check if another zero (or more) exists in the list. First, we compute the frequencies of each number, we can do this in a hash map or simply using the Counter class in Python.

Then, if we simply check if the triple exists in the original list. And if it zero, we have to check the occurences of the zero is more than one.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def findTriple(self, nums):
        data = Counter(nums)
        for i in nums:
            if i == 0:
                if data[0] > 1:
                    return True
            elif data[i * 3]:
                return True
        return False

class Solution:
    def findTriple(self, nums):
        data = Counter(nums)
        for i in nums:
            if i == 0:
                if data[0] > 1:
                    return True
            elif data[i * 3]:
                return True
        return False

In C++, we can use the unordered_multiset to count the elements with duplicates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

bool findTriple(vector<int>& nums) {
    unordered_multiset<int> data(begin(nums), end(nums));
    for (auto &n: nums) {
        if (n == 0) {
            if (data.count(0) > 1) {
                return true;
            }
        } else {
            if (data.count(n * 3)) {
                return true;
            }
        }
    }
    return false;
}

bool findTriple(vector<int>& nums) {
    unordered_multiset<int> data(begin(nums), end(nums));
    for (auto &n: nums) {
        if (n == 0) {
            if (data.count(0) > 1) {
                return true;
            }
        } else {
            if (data.count(n * 3)) {
                return true;
            }
        }
    }
    return false;
}

–EOF (The Ultimate Computing & Technology Blog) —