3623. Count Number of Trapezoids I
Approach
Group points by y; count all pairs of horizontal segments as potential parallel bases.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.
// Approach: Group points by y; count all pairs of horizontal segments as potential parallel bases.
// Time: O(n²) Space: O(n)
public class Solution
{
public int CountTrapezoids(int[][] points)
{
const int MOD = 1000000007;
var cnt = new Dictionary<int, int>();
foreach (var point in points)
{
int y = point[1];
if (!cnt.ContainsKey(y))
cnt[y] = 0;
cnt[y]++;
}
long result = 0, total = 0;
foreach (var c in cnt.Values)
{
long curr = ((long)c * (c - 1) / 2) % MOD;
result = (result + (total * curr) % MOD) % MOD;
total = (total + curr) % MOD;
}
return (int)result;
}
}