Triplets with Smaller Sum
Mahabharata — The Weight of Soldiers — Counting Battle Formations
लघवः सन्ति ये योधाः सीमातः न्यूनभारकाः। गणनीयाः समूहेन न तु एकैकशः सदा॥
*The soldiers who are light, whose combined weight is below the limit—count them as groups, not one by one.*
The Story
The war council was tense. Bhishma spread the map of Kurukshetra across the table, his weathered hands tracing potential routes.
"We must cross the Hiranvati River," he said gravely. "But the ancient bridge can hold only 15 bharas of weight at once. Any more, and it collapses."
Duryodhana frowned. "We have thousands of soldiers. How do we determine which triplets can cross together?"
"Not which triplets," Drona corrected. "How many triplets. We need to count all possible groups of three soldiers whose combined weight is strictly less than 15 bharas."
Shakuni, ever calculating, pulled out a list of soldier weights: [1, 2, 3, 4, 5, 6, 7, 8]. "Sorted by weight for easy reference."
Karna's first instinct was methodical: "I'll check every combination of three soldiers. 1+2+3=6, valid. 1+2+4=7, valid. 1+2+5=8, valid..." His scribes began enumerating.
"That's O(n³) operations," Drona interrupted. "For an army of thousands, we'll still be counting when Krishna's chariot reaches our gates. There must be a pattern to exploit."
Bhishma closed his eyes, remembering battles past. "The list is sorted. When I fix the lightest soldier, the heaviest valid partners are constrained. And here's the key insight: in a sorted array, if soldiers at positions `left` and `right` can form a valid triplet with the fixed soldier, then ALL soldiers between `left` and `right` can also form valid triplets with that same fixed soldier and `left` partner."
"Explain," demanded Duryodhana.
Bhishma demonstrated with the array [1, 2, 3, 4, 5], target < 10:
"Fix soldier 1 (weight 1). Now find pairs from [2, 3, 4, 5] such that 1 + pair < 10, meaning pair sum < 9."
"Left pointer at 2, right pointer at 5. Sum = 2 + 5 = 7 < 9. Valid!"
"Now the crucial insight: if 2 and 5 together (sum 7) are valid, then 2 paired with anything BETWEEN them is also valid. Why? Because 3 < 5 and 4 < 5, so 2+3 < 2+5 and 2+4 < 2+5."
"So the triplets (1,2,3), (1,2,4), (1,2,5) are ALL valid? That's 3 triplets found at once!"
"Exactly. The count from this single comparison is `right - left` = 5-1 = 3 triplets (positions, not values). Then we move left pointer right and continue."
Bhishma traced through: - Fixed: 1. Left at 2 (index 1), Right at 5 (index 4) - 2 + 5 = 7 < 9 → Valid! Add (right - left) = 3 triplets: (1,2,3), (1,2,4), (1,2,5) - Move left to 3 (index 2) - 3 + 5 = 8 < 9 → Valid! Add (right - left) = 2 triplets: (1,3,4), (1,3,5) - Move left to 4 (index 3) - 4 + 5 = 9, NOT < 9 → Invalid! Move right to 4 (index 3) - Left meets right, done with fixed element 1
"Total for fixed element 1: 3 + 2 = 5 triplets."
Drona's eyes widened. "You counted 5 triplets with only 3 comparisons!"
"Now repeat for fixed element 2," Bhishma continued. "And 3. But NOT 4 or beyond—if the fixed element is too heavy, even the two lightest remaining soldiers will exceed the limit."
The full count was computed efficiently. The army could plan its crossing—not soldier by soldier, but in optimized groups.
"Remember," Bhishma told his commanders, "when counting triplets below a threshold in a sorted array: fix one element, then for each valid pair (left, right), the COUNT of triplets is not 1 but (right - left). The sorted property transforms enumeration into arithmetic."
This is the Two Pointer technique for counting triplets with sum smaller than a target.
Karna's First Instinct
Enumerate every possible triplet and check if its sum is below the target. O(n³) time complexity.
public int countTripletsBruteForce(int[] arr, int sum) {
int count = 0;
int n = arr.length;
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 (arr[i] + arr[j] + arr[k] < sum) {
count++;
}
}
}
}
return count;
}Bhishma's Wisdom
public int countTriplets(int[] arr, int sum) {
Arrays.sort(arr);
int count = 0;
int n = arr.length;
// Fix the first element
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int tripletSum = arr[i] + arr[left] + arr[right];
if (tripletSum < sum) {
// ALL elements from left+1 to right form valid triplets
// with arr[i] and arr[left]
count += (right - left);
left++; // Try next left element
} else {
// Sum too large, reduce by moving right pointer
right--;
}
}
}
return count;
}
// Test with soldier weights
public static void main(String[] args) {
int[] weights = {-2, 0, 1, 3};
int maxWeight = 2;
int validTriplets = new Solution().countTriplets(weights, maxWeight);
System.out.println("Valid triplets: " + validTriplets);
// Output: Valid triplets: 2
// Triplets: (-2, 0, 1) and (-2, 0, 3) sum to -1 and 1, both < 2
}Step-by-Step Walkthrough
Array: [-2, 0, 1, 3], Target < 2
Sorted: [-2, 0, 1, 3]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0: Fix arr[0]=-2, find pairs with sum < 4
[-2, 0, 1, 3]
i L R
L=1, R=3: 0+3=3 < 4 → Valid!
Count += (3-1) = 2 triplets: (-2,0,1), (-2,0,3)
L++
L=2, R=3: 1+3=4, NOT < 4 → R--
L=2, R=2: L >= R, done with i=0
Subtotal: 2 triplets
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=1: Fix arr[1]=0, find pairs with sum < 2
[-2, 0, 1, 3]
i L R
L=2, R=3: 1+3=4, NOT < 2 → R--
L=2, R=2: L >= R, done with i=1
Subtotal: 0 triplets
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=2: Only 2 elements remain, cannot form triplet
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Total Count: 2 triplets
(-2, 0, 1): sum = -1 < 2 ✓
(-2, 0, 3): sum = 1 < 2 ✓Deep Insight
**Why does adding (right - left) work?**
When `arr[i] + arr[left] + arr[right] < target`: - We know `arr[left]` is fixed for this count - `arr[right]` is the largest valid partner - All elements between `left+1` and `right` are smaller than `arr[right]` (sorted array) - Therefore, `arr[i] + arr[left] + arr[k]` for any `left < k <= right` is also less than target
The count `(right - left)` captures: - (arr[i], arr[left], arr[left+1]) - (arr[i], arr[left], arr[left+2]) - ... - (arr[i], arr[left], arr[right])
**Why move left++ after counting?** We've counted ALL valid triplets with arr[i] and arr[left]. Moving left explores triplets with the next left element.
**Why move right-- when sum >= target?** The current right is too large. All pairs (left, right), (left+1, right), etc. would give sums >= target. Move right to a smaller value.
**Edge cases:** - All triplets valid: Count = C(n,3) = n(n-1)(n-2)/6 - No valid triplets: Count = 0 - Negative numbers: Algorithm handles them correctly
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n³) | O(1) | For n=1000: 166 million triplet checks |
| Optimal | O(n²) | O(1) | For n=1000: ~1 million comparisons |
Pattern Recognition
✅ Count (not find) triplets with sum below threshold ✅ Sorted array or sortable input ✅ "Smaller than" or "less than" constraint ✅ Count increases by more than 1 per valid pair **LeetCode Trigger Phrases:** → "count triplets with sum smaller than" → "number of triplets... sum less than X" → "how many groups of three... below limit"
Bhagavad Gita 14.20
गुणान् एतान् अतीत्य त्रीन् देही देहसमुद्भवान्। जन्ममृत्युजरादुःखैर्विमुक्तोऽमृतमश्नुते॥
When the embodied one transcends these three gunas (qualities) born of the body, he is freed from birth, death, old age, and sorrow, and attains immortality.
Connection: The algorithm transcends individual counting by recognizing the collective property: when one triplet is valid, many triplets sharing its structure are also valid. Rather than laboriously examining each combination, the wise algorithm perceives the underlying pattern and counts groups at once. This transcendence from individual to collective mirrors the spiritual journey from particular to universal understanding.