LeetCode Daily Problem P611: Number of Valid Triangles

---

Timeline

Timeline

2025-09-26

init

Multi-loop optimization

---

Problem:

P611 Number of Valid Triangles

https://leetcode.cn/problems/valid-triangle-number/description/?envType=daily-question&envId=2025-09-26

The fixed routine for this problem is to first fix the largest side, then use two pointers: one from front to back (representing the smallest side) and one from back to front (representing the second largest side). If the sum of the values pointed by the front pointer and the back pointer satisfies the triangle inequality condition, then the smallest side can be any value between the two pointers, and then we can decrease the second largest side to check if it still satisfies. If not, it means the smallest side is too small, so we increase the smallest side. Since it is the smallest side, its value cannot be greater than the second largest side. When the two pointers meet, it means we have traversed all cases where the largest side is the current fixed largest side. Then we decrease the largest side and restart the traversal with the smallest side and the second largest side.

#include <algorithm>
#include <vector>

using std::vector;

class Solution {
public:
  // Given an array nums of non-negative integers, return the number of triplets that can form the three sides of a triangle.
  // 1 <= nums.length <= 1000
  // 0 <= nums[i] <= 1000
  int triangleNumber(vector<int> &nums) {
    // The sum of any two sides of a triangle is greater than the third side.

    if (nums.size() < 3) {
      return 0;
    }
    vector<int> vec(nums);
    int n;
    int i, j, k;
    int res = 0;

    // Sort
    std::sort(nums.begin(), nums.end());
    // Deduplicate, need to sort before deduplication
    // vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

    n = vec.size();
    // First fix the largest side, k is the largest side in the triangle, then j is the second largest, i is the smallest.
    for (k = n - 1; k >= 2; k--) {
      i = 0;
      j = k - 1;
      while (i < j) {
        if (nums[i] + nums[j] > nums[k]) {
          // Because j traverses forward from k-1, and i traverses backward from 0.
          // So if nums[i] + nums[j] > nums[k]
          // All [i, j-1] can form a triangle with j and k
          res += (j - i);
          --j;
        } else {
          // Not satisfying the triangle condition means i is too small
          // Let i++ until i == j to exit the loop
          // Because at this point k and j are fixed, no i can satisfy the triangle condition
          // It means k is too large, let k--
          i++;
        }
      }
    }
    return res;
  }
};