You are given a set \(\mathbb{T}\) of sides, with size \(N\). Return the number of such triplets chosen from \(\mathbb{T}\) that can make up triangles, if we take them as lengths of the side.
Constraints:
\(1\)\(\;\leq\;\)\(N\)\(\;\leq\;\)\(1\)\(0\)\(0\)\(0\)\(;\,\)
\(0\)\(\;\leq\;\)\(\mathbb{T} \vphantom{ \mathbb{T}}_{\left[n\right]}\)\(\;\leq\;\)\(1\)\(0\)\(0\)\(0\)\(,\,\)\(\;\mathtt{for}\;\)\(n\)\(\;=\;\)\(1\)\(,\,\)\(\,\dotsc\,\)\(,\,\)\(N\)\(;\,\)
We want to find \(f\)\(\left[\vphantom{\mathbb{T}}\right.\)\(\mathbb{T}\)\(\left.\vphantom{\mathbb{T}}\right]\), the number of valid triples of triangle number. To slightly abuse notation, we may consider \(\mathbb{T}\) ordered in any fixed manner. The brute-force approach would be exhausting all triplets in \(\mathbb{T}\), with complexity \(\mathscr{O}\)\(\left[\vphantom{N \vphantom{ N}^{3}}\right.\)\(N \vphantom{ N}^{3}\)\(\left.\vphantom{N \vphantom{ N}^{3}}\right]\).
How can we do better? Let \(\mathbb{T}\) be sorted, which takes \(\mathscr{O}\)\(\left[\vphantom{N \,\mathrm{log}\, N}\right.\)\(N\)\(\,\mathrm{log}\,\)\(N\)\(\left.\vphantom{N \,\mathrm{log}\, N}\right]\) . Without loss of generality, let the triplet be \(\left\langle\vphantom{x ,\, y ,\, z}\right.\)\(x\)\(,\,\)\(y\)\(,\,\)\(z\)\(\left.\vphantom{x ,\, y ,\, z}\right\rangle\) with \(x\)\(\;\leq\;\)\(y\)\(\;\leq\;\)\(z\). We only have to check:
\(x\)\(\,+\,\)\(y\)\(\;>\;\)\(z\)\(;\,\)
Split cases of whether the biggest component \(z\)\(\;\in\;\)\(\mathbb{T}\) is chosen. Call \(\mathbb{S}\)\(\;\equiv\;\)\(\mathbb{T}\)\(\,\backslash\,\)\(\left\{\vphantom{z}\right.\)\(z\)\(\left.\vphantom{z}\right\}\). If \(g\)\(\left[\vphantom{z ,\, \mathbb{S}}\right.\)\(z\)\(,\,\)\(\mathbb{S}\)\(\left.\vphantom{z ,\, \mathbb{S}}\right]\) is the number of valid triples, in which \(z\) must be chosen, then:
\(f\)\(\left[\vphantom{\mathbb{T}}\right.\)\(\mathbb{T}\)\(\left.\vphantom{\mathbb{T}}\right]\)\(\;=\;\)\(g\)\(\left[\vphantom{z ,\, \mathbb{S}}\right.\)\(z\)\(,\,\)\(\mathbb{S}\)\(\left.\vphantom{z ,\, \mathbb{S}}\right]\)\(\,+\,\)\(f\)\(\left[\vphantom{\mathbb{S}}\right.\)\(\mathbb{S}\)\(\left.\vphantom{\mathbb{S}}\right]\)\(;\,\)
We see that \(g\)\(\left[\vphantom{z ,\, \mathbb{S}}\right.\)\(z\)\(,\,\)\(\mathbb{S}\)\(\left.\vphantom{z ,\, \mathbb{S}}\right]\) has complexity \(\mathscr{O}\)\(\left[\vphantom{N}\right.\)\(N\)\(\left.\vphantom{N}\right]\) . Indeed, fix \(z\), for any \(x\), we have \(y\)\(\;>\;\)\(z\)\(\,-\,\)\(x\). Here \(r\)\(\left[\vphantom{z \,-\, x}\right.\)\(z\)\(\,-\,\)\(x\)\(\left.\vphantom{z \,-\, x}\right]\), the number of such \(y\), may be found with a table, filled before the recursion. Hence, \(g\)\(\left[\vphantom{z ,\, \mathbb{S}}\right.\)\(z\)\(,\,\)\(\mathbb{S}\)\(\left.\vphantom{z ,\, \mathbb{S}}\right]\) may be so defined:
\(g\)\(\left[\vphantom{z ,\, \mathbb{S}}\right.\)\(z\)\(,\,\)\(\mathbb{S}\)\(\left.\vphantom{z ,\, \mathbb{S}}\right]\)\(\;=\;\)\( \displaystyle\sum\limits_{\bar{x} \;\in\; \mathbb{T}}\)\(r\)\(\left[\vphantom{z \,-\, \bar{x}}\right.\)\(z\)\(\,-\,\)\(\bar{x}\)\(\left.\vphantom{z \,-\, \bar{x}}\right]\)\(;\,\)
The complexity of calling \(g\) is \(\mathscr{O}\)\(\left[\vphantom{N}\right.\)\(N\)\(\left.\vphantom{N}\right]\), and the complexity of exhausting \(x\) is also \(\mathscr{O}\)\(\left[\vphantom{N}\right.\)\(N\)\(\left.\vphantom{N}\right]\). The complexity of recursively calling \(g\) is \(\mathscr{O}\)\(\left[\vphantom{N \vphantom{ N}^{2}}\right.\)\(N \vphantom{ N}^{2}\)\(\left.\vphantom{N \vphantom{ N}^{2}}\right]\), which overwhelms the complexity of sorting. The overall complexity is therefore \(\mathscr{O}\)\(\left[\vphantom{N \vphantom{ N}^{2}}\right.\)\(N \vphantom{ N}^{2}\)\(\left.\vphantom{N \vphantom{ N}^{2}}\right]\).
# 611. Valid Triangle Number [medium]
#! /usr/bin/env python3
import typing as TYPE
def main():
choice = [2, 2, 3, 4]
solution = Solution()
count = solution.count_triangle_number(
print("There are", count, "valid triplets.")
# "3"
# # [2,3,4], [2,3,4], [2,2,3]
class Solution:
def count_triangle_number(self, choice: TYPE.List[int]) -> int:
choice = [value for value in choice if value != 0]
if not choice: return 0
choice.sort()
record = dict()
for head in range(max(choice) * 2 + 1):
record[head] = sum([1 for value in choice if value <= head])
record[-1] = 0
distinct = list(set(choice))
distinct.sort()
number = self.count_various(record, distinct)
return number
def count_various(self, record: TYPE.Dict[int, int], distinct: TYPE.List[int]) -> int:
if not distinct: return 0
small = distinct[0]
partial = distinct[1:]
number_fixed = self.count_fixed(record, small, partial)
number_partial = self.count_various(record, partial)
number = number_fixed + number_partial
return int(number)
def count_fixed(self, record: TYPE.Dict[int, int], small: int, distinct: TYPE.List[int]) -> int:
number = 0
novel_small = record[small] - record[small - 1]
number += self.pick_three(novel_small)
if not distinct: return number
number += (record[small * 2 - 1] - record[small]) * self.pick_two(novel_small)
for value in distinct:
bound = value + small - 1
novel_medium = record[value] - record[value - 1]
if (novel_medium == 0): continue
total_above = record[bound] - record[value]
add_distinct = total_above * novel_medium
add_pair_medium = self.pick_two(novel_medium)
number += novel_small * (add_distinct + add_pair_medium)
return int(number)
def pick_two(self, number: int) -> int:
if (number < 2): return 0
return number * (number - 1) / 2
def pick_three(self, number: int) -> int:
if (number < 3): return 0
return number * (number - 1) * (number - 2) / 6
# # # # # # # # # # # # # # # #
main()
❧ July 19, 2021